Enclosing Circle Algorithm (Rework)
|Enclosing Circle Algorithm (Rework)|
|Has title||Enclosing Circle Algorithm (Rework)|
|Has owner||Abhijit Brahme|
|Has start date|
|Has deadline date|
|Has project status||Active|
|Does subsume||Enclosing Circle Algorithm, Enclosing Circle Algorithm (Plotting)|
|Has sponsor||McNair Center|
|Has project output||Tool|
|Copyright © 2019 edegan.com. All Rights Reserved.|
K-Means Based Algorithm
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)
The algorithm relies on an object-oriented implementation of a "cluster".
Each "cluster" has the following associated with it:
1. area of minimum circle enclosing points in the cluster 2. points associated with the cluster 3. minimum circle associated with the cluster (x-coord,y-coord,radius) 4. "parent" cluster 5. "children" cluster(s)
1. n, the minimum number of points to include in a circle 2. k, the amount of clusters to split the points into 3. valid_nodes, an empty list to store the possible clusters to explore 4. explored_nodes, an empty list to store the explored clusters 5. cur_node, initialized to an object with all values set to none 6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
1. Calculate the area of the minimum circle enclosing the total set of points 2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm 3. construct minimum circles of "k" clusters and compute their total area 4. if this area <= area of the area of the first circle 5. Add all "k" clusters to "valid_nodes" 6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points 7. run this algorithm again, change k = 2 8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in explored_node as the cur_node 9. if all the valid_nodes are in explored_nodes, return end_nodes 10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points.
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with the number of iterations at 100.
Further improvements could implement an early-stopping method to converge to a local optimum.
The K-Means based algorithm returns the optimal solution (left), and faster.
Is faster than both Brute Force and Logical Enclosing Circle.
Is more accurate than Logical Enclosing Circle.
Can plot to google maps.
Will return a tab delim text file of the following fields: city, year, total area
Good for a large number of points
Is not the optimal solution as number of points increases, but an approximation
Logical Enclosing Circle
The python script is located in :
The rationale is to take the furthest point, draw a circle with its nearest n-1 points.
Take the furthest point from the initial point, draw a circle with its nearest n-1 points.
Repeat until all points are enclosed.
Can plot to google maps
Is faster than brute force
Returns city, circles, year to a tab delimited text file
Really slow for large number of points
Offers an approximate solution that is worse than the Clustering based version
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
1) Find all combinations of two points in the total data set.
2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.
3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.
4) Iterate through the valid schemes and calculate the areas of the schemes.
5) Return the scheme with the minimum area.
Always gives you the correct answer.
For a small number of points (i.e., <7), this is OKAY to use.
However, it becomes extremely slow as the number of points increases.
The Julia/Python code does not have the capability to plot to google maps but will plot to a normal figure.
(will work on adding this implementation, if the need arises)