7,612
edits
Changes
Jump to navigation
Jump to search
Parallel Enclosing Circle Algorithm (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 ProjectsCenter
|Has title=Parallel Enclosing Circle Algorithm
|Has owner=Oliver Chang,
A thin-wrapper around [[Enclosing_Circle_Algorithm_(Rework)|the enclosing circle algorithm]] which allows for instance-level parallelization.
This project consists of the python files in <code>E:\McNair\Projects\OliverLovesCircles\src\python</code>. There is another version of the project with plotting functionality that uses a slightly different approach (removes duplicate points and uses their counts before running the algorithm) in <code>E:\McNair\Projects\KyranLovesCircles\src\python</code>.
Parallelization is implemented via Python2's [https://docs.python.org/2/library/subprocess.html#subprocess.Popen <code>subprocess.open()</code>] which is non-blocking and available in the standard library.
=== Example Usage ===
==== Splitting a master file and running ====
<nowiki>
$ python vc_circles.py --infile E:/McNair/Projects/OliverLovesCircles/CoLevelForCirclesNotRunGTE200.txt</nowiki>
<code>placestate, place, statecode, year, latitude, longitude, coname, datefirstinv, placens, geoid, city</code>
This command will populate (and overwrite) any files in <code>data/</code>, <code>out/</code>, and <code>reports/</code>. ==== Running on already split files ==== <nowiki>$ python vc_circles.py</nowiki> This command will populate (and overwrite) any files in <code>out/</code> and <code>reports/</code>.
== Bugs/Issues ==
This image shows a rendering of the results of running St. Louis. There are four circles (the centers of circles are green dots), but two have radii of 0.0.
=== Progress on the bug ===
# Removing duplicate points from the data actually removes all of the errors, but this doesn't give you the solution with the smallest area.
# I tried removing duplicates but keeping track of a "count."
# I narrowed down the bug to the constrained_kmeans method in ckmeans.py [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2000-65.pdf (paper here)]
## For some reason, this returns clusters with smaller numbers of points than n
## [http://adared.ch/constrained-k-means-implementation-in-python/ This is a good overview of the algorithm]
# I wrote a plotter, the plot method in circles.py
== Related Pages ==
