146
edits
Changes
Jump to navigation
Jump to search
Enclosing Circle Algorithm (Rework) (view source)
Revision as of 16:22, 19 June 2017
, 16:22, 19 June 2017Created page with "=K-Means Based Algorithm= ==Location== The script is located in: E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)\enclosin..."
=K-Means Based Algorithm=
==Location==
The script is located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)\enclosing_circle_new_implement.py
==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
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''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. <br>
Further improvements could implement an early-stopping method to converge to a local optima. <br>
==Visualization ==
The K-Means based algorithm returns the optimal solution, albeit slower <br>
[[File:kmeans comparison.png]] [[File:kmeans random.png]] [[File:houston.png]]
=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
==Explanation==
1) Find all combinations of two points in the total data set.
2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.
3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.
4) Iterate through the valid schemes and calculate the areas of the schemes.
5) Return the scheme with the minimum area.
==Location==
The script is located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)\enclosing_circle_new_implement.py
==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
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''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. <br>
Further improvements could implement an early-stopping method to converge to a local optima. <br>
==Visualization ==
The K-Means based algorithm returns the optimal solution, albeit slower <br>
[[File:kmeans comparison.png]] [[File:kmeans random.png]] [[File:houston.png]]
=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
==Explanation==
1) Find all combinations of two points in the total data set.
2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.
3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.
4) Iterate through the valid schemes and calculate the areas of the schemes.
5) Return the scheme with the minimum area.
