• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5"""Classify a set of points into two farthest clusters
6
7  - get_two_farthest_clusters(): Classify the points into two farthest clusters
8
9  - get_radii_of_two_minimal_enclosing_circles(): Get the radii of the
10        two minimal enclosing circles
11
12"""
13
14
15from .minicircle import minicircle
16
17
18def get_two_farthest_points(points):
19    """Calculate two farthest points from the list of given points.
20
21    Use a dumb brute force search for now since there are only a few points
22    in our use cases.
23    """
24    if len(points) <= 1:
25        return points
26
27    max_dist = float('-infinity')
28    for p1 in points:
29        for p2 in points:
30            dist = p1.distance(p2)
31            if dist > max_dist:
32                two_farthest_points = (p1, p2)
33                max_dist = dist
34
35    return two_farthest_points
36
37
38def get_two_farthest_clusters(points):
39    """Classify the points into two farthest clusters.
40
41    Steps:
42    (1) Calculate two points that are farthest from each other. These
43        two points represent the two farthest clusters.
44    (2) Classify every point to one of the two clusters based on which
45        cluster the point is nearer.
46
47    @param points: a list of points of Point type
48    """
49    if len(points) <= 1:
50        return (points, [])
51
52    fp1, fp2 = get_two_farthest_points(points)
53
54    # Classify every point to the two clusters represented by the two
55    # farthest points above.
56    cluster1 = []
57    cluster2 = []
58    for p in points:
59        (cluster1 if p.distance(fp1) <= p.distance(fp2) else cluster2).append(p)
60
61    return (cluster1, cluster2)
62
63
64def get_radii_of_two_minimal_enclosing_circles(points):
65    """Get the radii of the two minimal enclosing circles from points.
66
67    Return: [radius_of_circle1, radius_of_circle2]
68            where circle1, circle2 are the two minimal enclosing circles
69            of the two clusters derived from the two farthest points
70            found in the argument points.
71    """
72    return [minicircle(cluster).radius
73            for cluster in get_two_farthest_clusters(points) if cluster]
74