RRTfin.mov
rrtjoints.mov
fold.mov
Screen-2023-04-03-214456.mp4
- Run make command to generate executable
- Run executable
- Draw boundaries of shape with left-mouse clicks
- press 's' to then enter the guard drawing mode
- click anywhere to add guards
- press 'r' to let guards move
- toggle 'v' to show/unshow visibility zones for each of the guards
- 'q' to quit!
shortestPathGeom.mp4
- Run make command to generate executable
- Run executable
- Draw boundaries of shape with left-mouse clicks
- Press 'n' to add new boundary (can create as many boundaries as desired)
- press 's' to then enter the start drawing mode
- After adding the start, press 'e' to add the end node
- Press 'r' to run!
- press 'q' to quit
Screen.Recording.2023-04-15.at.7.42.35.PM.mov
- run "make" command to build project
- execute the excecutable with an integer value corresponding to the number of points to generate a hull around!
- Use x, y, and z to rotate around those respective axes
- Use q to quit
- use a to animate the generation process
- use t to turn on/off geometry around the hull
- run "make" command to build project
- execute the excecutable with an integer value corresponding to the number of sections to divide the mondrian-style painting into!
On a given set of points, will generate a 2d hull around them, following the Graham's scan algorithm
- run "make" command to build project
- execute the viewPoints excecutable with an integer value corresponding to the number of points to generate
- press i to cycle through different shapes, and be amazed as 2d hulls are generated!
- First split grid with k divisions, where k is either the number inputted by the user for number of grid divisions, or is the square root of n, as this should be the optimal number of grid divisions given that the points are randomly distributed, as in this case the number of grid boxes is equal to the number of points.
- Now, after having decided on the number of grid divisions, we inserted each of the randomly generated points into a 2d array of vectors, where each vector represents the points in one of the k^2 grid boxes.
- After having inserted the points into the 2d array, we now call our gridding function to determine which pair of points is the closest.
- Then, for each point in p, we check the distances from that point to all other points in its grid box. After doing so, we check the distance from that point to other points in adjacent boxes that are within the current minimum distance away from the point, where the current minimum distance is the global minimum distance thus far between two points.
- If there are no points in a given grid box, we simply skip to the next one.
- As an added optimization, our gridding approach terminated after a pair of points are found that are a distance one away from eachother, as this is the minimum distance possible in the graph.
- Given n points, we determined that the optimal grid division (value for k) on average was the square root of n, as this would give n total grid boxes, so the relationship between the number of points and the number of grid boxes is one-to-one, which gives the fastest runtime on average.
| n | Naive | Gridding |
|---|---|---|
| 5 | 0.000012 | 0.000004 |
| 10 | 0.000016 | 0.000005 |
| 50 | 0.000088 | 0.000015 |
| 100 | 0.000320 | 0.000021 |
| 500 | 0.007676 | 0.000075 |
| 1000 | 0.030955 | 0.000193 |
| 5000 | 0.693969 | 0.000043 |
| 10000 | 2.643573 | 0.000006 |
| 50000 | 65.636965 | 0.000008 |
| 100000 | 143.382738 | 0.000010 |