7,612
edits
Changes
Jump to navigation
Jump to search
|Is billed to=|Has notes=|Has project status=ActiveSubsume|Is dependent on=|Depends upon itHas Image=Red-circle.jpg
Enclosing Circle Algorithm (view source)
Revision as of 13:47, 21 September 2020
, 13:47, 21 September 2020no edit summary
{{McNair ProjectsProject|Has project output=Tool|Has Imagesponsor=Red-circle.jpgMcNair Center
|Has title=Enclosing Circle Algorithm
|Has owner=Christy Warden, Peter Jalbert,|Has start date=201701January 2017|Has deadline=201704April 2017
|Has keywords=Tool
}}
The objective of this project is come up with a fast, reliable algorithm that finds the smallest circle area that can drawn around N Cartesian points such that each circle contains at least M<N points. This algorithm will be used in an academic paper on [[Urban Start-up Agglomeration]], where the points will represent venture capital backed firms within cities.
8) Choose the scheme that resulted in the smallest total area.
=K-Means Based Algorithm=
==Location==
The script is located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)\enclosing_circle_new_implement.py
==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". <br>
Each "cluster" has the following associated with it: <br>
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)
'''Inputs:'''
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
'''Algorithm:'''
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
'''Runtime:'''
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. <br>
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. <br>
Further improvements could implement an early-stopping method to converge to a local optima. <br>
==Visualization ==
The K-Means based algorithm returns the optimal solution, albeit slower <br>
[[File:kmeans comparison.png]] [[File:kmeans random.png]] [[File:houston.png]]
=Brute Force=
The script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
==Explanation==
Update: Did not incur any speed up by implementing changes the the calculation for center or distance. Reading about python threads https://pymotw.com/2/threading/
Update: Implemented a thread version of the program and am running that in addition to the non-threaded version to see how the timing compares. EnclosingCircleRemake2.py.
How the threading works:
1) Split the pointset into all its initial possible schemes (one split).
2) Divide these schemes amongst four threads.
3) Have each thread compute the best outcome of each of those schemes and put them into a global array.
4) Join all the threads.
5) Have the main function iterate through the schemes returned by the threads and choose the best one.
6) Create circles for the schemes and return them.
On preliminary examples, the code works correctly. It actually runs slower than the original algorithm on small examples but I suspect that is the overhead of creating the threads and that they will be useful to the large examples.
=== Use PostGIS ===
If the point of the project is to solve an application, the Not-Invented-Here approach is doomed to fail. Instead, I suggest an approach where
# Load reverse geolocated into a PostGIS PostgreSQL table
# Use [https://postgis.net/docs/ST_MinimumBoundingRadius.html ST_MinimumBoundingRadius] which is an implementation of a linear (read: very fast) minimum bounding circle algorithm. See https://github.com/postgis/postgis/blob/svn-trunk/liblwgeom/lwboundingcircle.c for implementation details.
# Run queries against DB
==Runtime==
