Introduction
Introduction
Our goal is to find the shortest path between two points on a plane containing an arbitrary amount of non-overlapping, non-tangent disks. The start and end points are outside of all disks. A typical application is for a robot that is trying to navigate through some place where there are circular obstacles. The shortest path between two points is a line, and in this case, because disks are involved, these lines are tangents. Once on a disk, the shortest path becomes an arc. Because of this, the shortest path through a field of disks is then composed of arcs and tangents in an alternating fashion. The path will always start and end with a tangent, because of the points' placement. The points of tangency are either between two disks or a disk and a point. We can now create a weighted undirected graph with vertices being the points, and edges being the tangents or arcs between them, weighted by their distance. We will use Mathematica's shortest path function on the graph.
Algorithm
Algorithm
We chose to consider all disks as stepping stones, as we didn't find a way to discard any of the disks. However, we don't consider all tangents as edges, we exclude the ones which pass through any disk. In order to carry out this selection process we create the function clearOfDisks.
We make use of the RegionIntersection function to check what type of intersection a disk and line are forming. RegionIntersection will return Line (for an intersection), Point (in the case of a tangent), or EmptyRegion. We make sure the intersection isn't a line in all cases:
clearOfDisks[pt1_List,pt2_List,disks_List]:=Module[{line},line=Line[{pt1,pt2}];AllTrue[disks,Not[Head@RegionIntersection[line,Disk[#[[1]],#[[2]]]]===Line]&]]
Our process is as follows: first we find the tangent points which are allowed when connected to the start or end point. Next we find the allowed tangent points between any two disks. Once we have all the tangent lines, we find arcs/edges between all tangent points on a disk. Finally we create a graph on which we apply a shortest path algorithm. Dijkstra's algorithm runtime is of the order E + V log V, where E is the amount of edges and V is the amount of vertices. In order to maximize our run time there would need to be work put towards limiting the edges and vertices. This could be done by ignoring some of the disks.
Tangents From a Point
Tangents From a Point
From the start and end point we must find the tangents they have with a disk as two of these points will be used in the shortest path, and all have the potential to be used.
Using the formulas below, we calculate both tangency points on a disk:
tangentPointsFromPoint[pt_List,disk_List]:=Module[{x1,y1,x2,y2,centerx,centery,radius,pointx,pointy},centerx=disk[[1]][[1]];centery=disk[[1]][[2]];radius=disk[[2]];pointx=pt[[1]];pointy=pt[[2]];x1=(((radius^2*(pointx-centerx)+radius*(pointy-centery)*Sqrt[(pointx-centerx)^2+(pointy-centery)^2-radius^2])/((pointx-centerx)^2+(pointy-centery)^2)))+centerx;x2=(((radius^2*(pointx-centerx)-radius*(pointy-centery)*Sqrt[(pointx-centerx)^2+(pointy-centery)^2-radius^2])/((pointx-centerx)^2+(pointy-centery)^2)))+centerx;y1=(((radius^2*(pointy-centery)-radius*(pointx-centerx)*Sqrt[(pointx-centerx)^2+(pointy-centery)^2-radius^2])/((pointx-centerx)^2+(pointy-centery)^2)))+centery;y2=(((radius^2*(pointy-centery)+radius*(pointx-centerx)*Sqrt[(pointx-centerx)^2+(pointy-centery)^2-radius^2])/((pointx-centerx)^2+(pointy-centery)^2)))+centery;{{x1,y1},{x2,y2}}]
Whenever we find a tangent point on a disk, we must verify that it doesn't pass through any of the disks. To do this we will use the clearOfDisks function mentioned earlier.
Because tangentPointsFromPoint takes one point and only one disk, we must write another function that calls tangentPointsFromPoint for all disks, that way we can construct all the starts and ends for possible paths. We can also utilize clearOfDisks to verify that these points are allowed. We need to know the points on a disk so that we can construct arcs/edges between them later.
Dijkstra's shortest path algorithm needs to be called with edges and their respective weight, which in this case is their length. While looping through the tangent points on a disk we will begin constructing a list of edges and a list of edge weights. Additionally we also construct an association between a disk and a list of tangent points that lie on that disks circumference. We will return edges, edgeWeights, and an association of points on a disk. We will loop through all disks and check if the line from the point to the disk passes through any disks. Then we will loop through the allowed points and append them to the list of edges:
tangentEdgeFinder[pt_List,discs_List]:=Module[{tangentPointsToCircle,goodTangentPts,edges,edgeWeights,pointsOnDisks,pair},edges={};edgeWeights={};pointsOnDisks=<||>;Table[{pair=tangentPointsFromPoint[pt,d];goodTangentPts=Select[pair,clearOfDisks[pt,#,discs]&];Table[{AppendTo[edges,ptp];AppendTo[edgeWeights,ptpEuclideanDistance[pt,p]];},{p,goodTangentPts}];goodTangentPts;If[Length[goodTangentPts]≠0,AssociateTo[pointsOnDisks,dgoodTangentPts],Nothing];},{d,discs}];{edges,edgeWeights,pointsOnDisks}]
Tangents Shared By Two Disks
Tangents Shared By Two Disks
Two non-tangent, non-overlapping disks generate four tangent lines, or edges, between them. They can be categorized as either outer or inner tangents.The formulas used to find the four coordinates of where the outer tangents intersect with either disk first calculate the coordinates of the point where they intersect. However this formula runs into issues when the two circle are of equal radii. In this case the formula to find the outer tangency points is a little different, and the formula for inner tangency points remains the same. There are also other cases in which the formulas don't work, such as when the two circle have equal radii and equal x or y coordinates. In these scenarios the formulas are simpler.
The formulas distinguish between the large and small circle. When we call this function we expect the points attributed to the correct disk. Because of this, we define a variable flipped so that we know if we flipped the order of the disks. The function outputs the pairs of points which lie on the same tangent line. Every pair of points starts on the first disk, and ends on the second disk. We will utilize this later when calling this function for all pairs of disks:
While debugging it was useful to visualize our output:
Similarly to before, we need another function to call tangentPointsToTwoCircles for all possible pairs of disks, and return the edges, their weights, and the disk the points lie on. This function will also use clearOfDisks to ensure that the edge passing through the pair of points is allowed.
This function returns the same lists and associations as tangentEdgeFinder. First we loop through each pair of disks, and then we select the pairs of points that don't pass through any other disks. Next we loop through the allowed pairs of points and construct two lists, one of edges and one of edge weights. Finally we make the association of pointsOnDisks. We utilize merge when doing this so that we can have a list of points that lies on a disk. Similar to tangentEdgeFinder, this function will return edges, edge weights, and pointsOnDisks. First we loop through pairs of disks and select the allowed pairs of points, then we will add these pairs to edges:
Arcs
Arcs
The arcs that will be potentially used in the shortest path exist between two tangent points on the same disk. Because of this, we can't add these edges until we have merged both of associations pointsOnDisks created in tangentEdgeFinder and tangentEdgeFinderForDisks. Once we have all of the points on a disk, we can find all of the pairs and them to the list of edges, and their length to edgeWeights. In order to find their weight we must create a function that finds the arc length between two points given the radius of the circle they lie on.
Finding the arc length is very simple if the angle, θ, between the two points is known. In order to find this we solve for the angle using ArcSin. Finally we multiply this value by the radius to find the arc length:
(Note that arcLength is called without an epsilon here):
Because using two arcs is shorter by a difference of 10^-16 we add a small epsilon to each arc length in order to ensure that the algorithm will treat the right side of the graphic as desirable. Through running the function on different fields of disks I identified 1.000001 as the best option for epsilon.
Putting Everything Together
Putting Everything Together
Now we have a way to find all edges, their weight, and an association of what points lie on a disk. As mentioned before this still excludes arcs, but now that we can create two associations of the points on a disk, we can create edges of all possible arcs that exist on a circle.
This function is the final step in outputting the shortest path. First we call tangentEdgeFinder for the start and end point, and we also call tangentEdgeFinderForDisks. Each one of these calls will produce a list of three things: edges, edge weights, and an association of points on a disk. We merge all three of these separately. Next, for each disk, we will create all pairs of points on a disk, appending each one to edges, and appending their assigned weight to edgeWeights. Now that all possible edges for the shortest path are in a list, we create an undirected graph with weights. Next, we will apply Dijkstra's shortest path algorithm to this graph. Finally we convert the path into a visualization, where arcs and tangent lines are color coded:
Random Disk Generation
Random Disk Generation
In order to produce test cases for the above function a random disk generator was created.
We plot n disks with an integer y-value between ymin and ymax, an integer x-value between xmin and xmax, and an integer radius between rmin and rmax. The disks are non-overlapping and non-tangent. The final mapping is used to convert dlist to the proper format that main accepts:
Summary of Results
Summary of Results
We were able to output a visualization of the shortest path, an undirected graph with the shortest path highlighted, and the length of the path. In the future, improvements can be made in narrowing down how many disks are considered. This would significantly decrease the amount of edges and vertices, increasing runtime.
Example Outputs
Example Outputs
Acknowledgements
Acknowledgements
I want to thank my mentor, Jesse Dohmann, for helping me work through my project, and answering my questions, and also everyone who helped make the 2020 Wolfram Summer Camp possible.
References
References
Keywords
Keywords
◼
Shortest path
◼
Field of disks
◼
Obstacles
◼
Disks