272
edits
Changes
Jump to navigation
Jump to search
no edit summary
The original script is located in:
E:\McNair\Software\CodeBase\EnclosingCircle.py
==Explanation==
Inputs: A set of points, a minimum number of points to include in each circle.
1) Find a point on the outside of the set of points by choosing the rightmost point in the set.
2) If the quantity of points in the input is less than twice the minimum number of points to include in the circle, return a circle containing all of the points. This is because there is no way to split up the points without having a circle containing less than n points.
3) Sort the points by their distance from starting point (using distance formula).
4) Create a list of points called "Core." The core should contain starting point and the n - 1 points that are closest to it. This is the smallest circle that contains starting point.
5) Run the same algorithm on the rest of the points that are not contained in core and store the area of the core + the area of the result on the remaining points.
6) Add one point (the next closest one to starting point) to the core and then repeat step 5.
7) Repeat step 6 until there aren't enough points outside of the core to constitute a valid circle.
8) Choose the scheme that resulted in the smallest total area.
