Welcome to an exploration of various computational geometry concepts!

Will include demos of different geometrical algorithms in 2d and 3d space.

---

Usage Instructions below Examples

RRT-Multi-Joint-Path-Planning

Examples

Single Joint!

RRTfin.mov

Multi-Joint!

rrtjoints.mov

My Personal Favorite!

fold.mov

Main Flow

Begin by drawing a polygonal obstacle, counter-clockwise

Press n to save current polygon, and begin drawing next

Once finished drawing obstacles, press n and then s to start drawing robot

press s to draw a new section of the robot

press e to choose the goal location

press r to run RRT

press p to show path

press g to go

q to quit!

---

OTHER

t: hide/show tree structure

c: show all possible conditions

---

Parameters (Set in CPP file)

epsilon: controls distance between nodes

entropyThreshhold: controls the amount the robot can rotate between nodes

MovementSpeed: speed to animate robot

SizeRRT: upper limit for amount of nodes in RRT tree

---

---

Art-Gallery-Guarding

Examples!

Screen-2023-04-03-214456.mp4

Usage

1. Run make command to generate executable
2. Run executable
3. Draw boundaries of shape with left-mouse clicks
4. press 's' to then enter the guard drawing mode
5. click anywhere to add guards
6. press 'r' to let guards move
7. toggle 'v' to show/unshow visibility zones for each of the guards
8. 'q' to quit!

---

---

Find-Visibility-Graph

Examples!

shortestPathGeom.mp4

Usage

1. Run make command to generate executable
2. Run executable
3. Draw boundaries of shape with left-mouse clicks
4. Press 'n' to add new boundary (can create as many boundaries as desired)
5. press 's' to then enter the start drawing mode
6. After adding the start, press 'e' to add the end node
7. Press 'r' to run!
8. press 'q' to quit

---

---

3D-Hull-Generation

Examples!

Screen.Recording.2023-04-15.at.7.42.35.PM.mov

Usage

1. run "make" command to build project
2. execute the excecutable with an integer value corresponding to the number of points to generate a hull around!
3. Use x, y, and z to rotate around those respective axes
4. Use q to quit
5. use a to animate the generation process
6. use t to turn on/off geometry around the hull

---

---

KD-Tree-Mondrian-Generation

Examples!

Usage

1. run "make" command to build project
2. execute the excecutable with an integer value corresponding to the number of sections to divide the mondrian-style painting into!

---

---

2D Hull Generation

On a given set of points, will generate a 2d hull around them, following the Graham's scan algorithm

Examples:

Usage

1. run "make" command to build project
2. execute the viewPoints excecutable with an integer value corresponding to the number of points to generate
3. press i to cycle through different shapes, and be amazed as 2d hulls are generated!

---

Find-Closest-Pair

To find the closest pair, we used the following approach:

1. 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.
2. 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.
3. After having inserted the points into the 2d array, we now call our gridding function to determine which pair of points is the closest.
4. 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.
5. If there are no points in a given grid box, we simply skip to the next one.
6. 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.

To chose the optimal grid size, we did the following:

• 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.

Table of our algorithm's runtimes:

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