7,612
edits
Changes
Jump to navigation
Jump to search
== Step By Step Use==
1. Open up the file "googleplotter"
2. where it says with open("C:\....") replace the filepath in the parentheses with your filepath enclosed in quotes.
3. Press ctrl+s to save the file
4. open up the command line
5. type: python googleplotter.py
6. your resulting text file and html google plots will be outputted to:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)
Enclosing Circle Algorithm (Rework) (view source)
Revision as of 13:47, 21 September 2020
, 13:47, 21 September 2020no edit summary
{{Project
|Has project output=Tool
|Has sponsor=McNair Center
|Has title=Enclosing Circle Algorithm (Rework)
|Has owner=Abhijit Brahme,
|Has keywords=Tool
|Has project status=Active
|Does subsume=Enclosing Circle Algorithm, Enclosing Circle Algorithm (Plotting),
}}
=K-Means Based Algorithm=
==Location==
==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
'''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, with the number of iterations at 100. <br>Further improvements could implement an early-stopping method to converge to a local optimaoptimum. <br> [[File:runtime.png]]
==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. <br>
[[File:houstonk.png]] [[File:houstonp.png]]
== Benefits ==
Is more accurate than Logical Enclosing Circle. <br>
Can plot to google maps. <br>
Will return a tab delim text file of the following fields: city,year,total area <br>
Good for a large number of points <br>
==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation
=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. <br>
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. <br>
Repeat until all points are enclosed. <br>
==Benefits==
Can plot to google maps <br>
Is faster than brute force <br>
Returns city, circles, year to a tab delimited text file <br>
==Drawbacks==
Really slow for large number of points <br>
Offers an approximate solution that is worse than the Clustering based version <br>
=Brute Force=
For a small number of points (i.e., <7), this is OKAY to use. <br>
However, it becomes extremely slow as the number of points increases. <br>
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. <br>(will work on adding this implementation, if the need arises) [[Category:Internal]]
