client/site_tests/firmware_TouchMTB/geometry/two_farthest_clusters.py

# 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.

    Steps:
    (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]