7,612
edits
Changes
Jump to navigation
Jump to search
== 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 "lattitude',"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 time.
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>
"C:\\Users\\Name\\Documents\\CityYear.txt"
e. "outputfn", the full file path of where to output the area of the circles for a given city,year <br>
2. To plot the circles,points for a given year onto google maps, use the function "googleplotter.py"
a. This function takes in the filename used in 1d <br>
an example: "C:\\Users\\Name\\Documents\\CityYearAreas.txt"
3. To plot just the circles do the following:
a. go to command prompt and type in cd /d E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)
b. type in python plot_wrapper2.py
c. follow the prompts
d. file should pop up in the same directory
*the data must have column headers 'latitude' and 'longitude'*
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]]
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>
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]]
