Home | History | Annotate | Download | only in geometry 
      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 
     15 from .minicircle import minicircle
     16 
     17 
     18 def 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 
     38 def 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 
     64 def 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