201
edits
Changes
Jump to navigation
Jump to search
Enclosing Circle Algorithm (Rework) (view source)
Revision as of 11:00, 31 October 2017
, 11:00, 31 October 2017no edit summary
{{McNair Projects
|Has title=Enclosing Circle Algorithm (Rework)
|Has keywords=Tool
|Has project status=Subsume
}}
=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]]
== Step By Step Use==
1. The file "vc_circles.py" contains the main script, "master_circles", which takes in the following
a. "textfile", which is the filepath of the text data to read in. It must have fields "lattitudelatitude',"longitude","city","datefirstinv"
b. "n", which is the number of points to include in each circle
c. "iterations", the number of iterations to try and find a local optimum. Large numbers will slow the run timeruntime. d. "basefn", the base file path of where to store the circles and points for each city,year pair <br>
an example: "C:\\Users\\Name\\Documents" <br>
the function will add on the city,year to this base file name and save it to this file directory <br>
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>
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]]
