You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
105 lines
3.0 KiB
105 lines
3.0 KiB
from .math import Math |
|
from .points import Point, PointSet |
|
|
|
|
|
class CentroidGrouping: |
|
""" |
|
A storage class used because Points are not hashable (since the x and y |
|
can change). This allows us to do better than just dumping the grouping |
|
into a dictionary with a long tuple pointing at an array. |
|
""" |
|
def __init__(self, centroid, points=None): |
|
if not isinstance(centroid, Point): |
|
ValueError("Centroid must be a Point.") |
|
|
|
if not isinstance(points, list): |
|
ValueError("Points must be in a list.") |
|
|
|
self.__centroid = centroid |
|
|
|
if points is None: |
|
self.__points = [] |
|
else: |
|
self.__points = points |
|
|
|
@property |
|
def centroid(self): |
|
return self.__centroid |
|
|
|
@property |
|
def points(self): |
|
return self.__points |
|
|
|
def add_point(self, point): |
|
""" |
|
Adds a point. |
|
|
|
@param point The point. |
|
""" |
|
if not isinstance(point, Point): |
|
raise ValueError("Point must be of type Point.") |
|
|
|
self.__points.append(point) |
|
|
|
def __repr__(self): |
|
s = f"CENTROID: {self.__centroid}\n" |
|
s += f"POINTS: {self.__points}" |
|
|
|
return s |
|
|
|
def __eq__(self, other): |
|
return (self.__centroid == other.centroid and |
|
self.__points == other.points) |
|
|
|
|
|
class Algorithms: |
|
""" |
|
A static class for handling and containing various computational |
|
geometry algorithms. |
|
""" |
|
|
|
@staticmethod |
|
def euclidean_grouping(centroids, point_set): |
|
""" |
|
Given a point set that EXCLUDES the centroids specified |
|
it returns a map from centroid to array of points, where the array |
|
of points contains the points with the smallest euclidean distance |
|
from that point. |
|
|
|
@param centroids The centroids to use. |
|
@param point_set The set of points from the UI excluding centroids. |
|
""" |
|
if not isinstance(point_set, PointSet): |
|
raise ValueError("Euclidean grouping can only be calculated on " + |
|
"PointSet types.") |
|
|
|
if not isinstance(centroids, list): |
|
raise ValueError("Centroids must be of type list.") |
|
|
|
if not centroids: |
|
raise ValueError("No centroids specified.") |
|
|
|
groups = [] |
|
|
|
for centroid in centroids: |
|
groups.append(CentroidGrouping(centroid)) |
|
|
|
for point in point_set.points: |
|
nearest_distance = float("inf") |
|
nearest_group = None |
|
|
|
for current_group in groups: |
|
current_distance = ( |
|
Math.euclidean_distance(current_group.centroid, point)) |
|
|
|
if current_distance < nearest_distance: |
|
nearest_group = current_group |
|
nearest_distance = current_distance |
|
|
|
if nearest_group is None: |
|
raise ValueError("Failed to find centroid nearest " + |
|
f"to point {point}") |
|
|
|
nearest_group.add_point(point) |
|
|
|
return groups
|
|
|