blob: 12eab089693c2e7920ea0e02bafa7dd968d5708e [file] [log] [blame]
# Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
"""Classify a set of points into two farthest clusters
- get_two_farthest_clusters(): Classify the points into two farthest clusters
- get_radii_of_two_minimal_enclosing_circles(): Get the radii of the
two minimal enclosing circles
from .minicircle import minicircle
def get_two_farthest_points(points):
"""Calculate two farthest points from the list of given points.
Use a dumb brute force search for now since there are only a few points
in our use cases.
if len(points) <= 1:
return points
max_dist = float('-infinity')
for p1 in points:
for p2 in points:
dist = p1.distance(p2)
if dist > max_dist:
two_farthest_points = (p1, p2)
max_dist = dist
return two_farthest_points
def get_two_farthest_clusters(points):
"""Classify the points into two farthest clusters.
(1) Calculate two points that are farthest from each other. These
two points represent the two farthest clusters.
(2) Classify every point to one of the two clusters based on which
cluster the point is nearer.
@param points: a list of points of Point type
if len(points) <= 1:
return (points, [])
fp1, fp2 = get_two_farthest_points(points)
# Classify every point to the two clusters represented by the two
# farthest points above.
cluster1 = []
cluster2 = []
for p in points:
(cluster1 if p.distance(fp1) <= p.distance(fp2) else cluster2).append(p)
return (cluster1, cluster2)
def get_radii_of_two_minimal_enclosing_circles(points):
"""Get the radii of the two minimal enclosing circles from points.
Return: [radius_of_circle1, radius_of_circle2]
where circle1, circle2 are the two minimal enclosing circles
of the two clusters derived from the two farthest points
found in the argument points.
return [minicircle(cluster).radius
for cluster in get_two_farthest_clusters(points) if cluster]