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"""This module contains unit tests for geometry module."""
6
7
8import random
9import unittest
10
11import common_unittest_utils
12
13from math import sqrt
14from sets import Set
15
16from geometry.elements import Circle, Point
17from geometry.minicircle import minicircle
18from geometry.two_farthest_clusters import get_two_farthest_clusters
19
20
21class MinicircleTest(unittest.TestCase):
22    """A class for FirwareSummary unit tests."""
23
24    def test_minicircle(self):
25        # a list of points: [center, radius]
26        tests = [
27            # a right triagnle
28            ([(0, 0), (3, 0), (0, 4)], [(1.5, 2), 2.5]),
29
30            # an obtuse triagnle
31            ([(1, 1), (3, 0), (0, 4)], [(1.5, 2), 2.5]),
32
33            # a right triagnle with one point inside
34            ([(0, 0), (1, 1), (3, 0), (0, 4)], [(1.5, 2), 2.5]),
35
36            # three points at the same coordinates
37            ([(5, 3), (5, 3), (5, 3)], [(5, 3), 0]),
38
39            # two points at the same coordinates, a diagonal line
40            ([(0, 0), (0, 0), (4, 4)], [(2, 2), 2 * sqrt(2)]),
41
42            # two points at the same coordinates, a vertical line
43            ([(0, 2), (0, 2), (0, 12)], [(0, 7), 5]),
44
45            # two points at the same coordinates, a vertical line, one outlier
46            ([(0, 2), (0, 2), (1, 5), (0, 12)], [(0, 7), 5]),
47
48            # an equilateral triangle
49            ([(0, 0), (10, 0), (5, 5 * sqrt(3))],
50                    [(5, 5 * sqrt(3) / 3), 5 * sqrt(3) * 2 / 3]),
51
52            # an equilateral triangle with a few points inside
53            ([(0, 0), (10, 0), (5, 5 * sqrt(3)), (4, 1), (6, 2), (4.5, 3),
54              (5.2, 2.99), (4.33, 1.78), (5.65, 3.1)],
55                    [(5, 5 * sqrt(3) / 3), 5 * sqrt(3) * 2 / 3]),
56
57            # a list of random points:
58            #   Verify with octave geometry package:
59            #   > points = [1,1; 1,0; 2,1; 2,2;  12,22; 11,21; 30,30; 31,30;
60            #               30,31; 31,31; 5,35]
61            #   > enclosingCircle(points)
62            ([(1, 1), (1, 0), (2, 1), (2, 2), (12, 22), (11, 21), (30, 30),
63              (31, 30), (30, 31), (31, 31), (5, 35)],
64                    [(15.39740821, 16.08315335), 21.58594878]),
65
66            # another list of random points:
67            #   Verify with octave geometry package:
68            #   > points = [11,11; 11,15; 12,11; 12.5,21.25; 12.77,22.84; 11,21;
69            #               13.3,31; 13.7,33; 14.9,29; 15,10.9; 12.5,13.55]
70            #   > enclosingCircle(points)
71            ([(11, 11), (11, 15), (12, 11), (12.5, 21.25), (12.77, 22.84),
72              (11, 21), (13.3, 31), (13.7, 33), (14.9, 29), (15, 10.9),
73              (12.5, 13.55)],
74                    [(13.27341679, 21.88667158), 11.12151257]),
75        ]
76        for points, circle_values in tests:
77            center_values, radius = circle_values
78            expected_circle = Circle(Point(*center_values), radius)
79            actual_circle = minicircle(points)
80            self.assertTrue(actual_circle == expected_circle)
81
82    def test_get_two_farthest_clusters(self):
83        tests = [
84            # Each row is a tuple of two separated clusters.
85            # two empty lists
86            ([], []),
87
88            # one point only
89            ([(3.5, 7.886612)], []),
90
91            # two points only
92            ([(3.5, 7.886612)], [(3.4, 7.02)]),
93
94            ([(1.2, 0), (2.3, 0), (0, 2.2)],
95             [(10, 5), (11.87, 3.45), (10.55, 7.6)]),
96
97            ([(100, 3.1), (101.1, 2.9), (99.8, 4.2)],
98             [(1.1, 55.3), (11.87, 73.45), (3.58, 67.7)]),
99
100            ([(101, 5.5), (102.1, 2.9), (89.8, 4.2), (65.2, 3.3)],
101             [(1.5, 5.3), (1.87, 3.5), (23.8, 14.9), (3.8, 2.7)]),
102        ]
103
104        # Shuffle the two clusters, and then test the get_two_farthest_clusters
105        # function. It should return cluster1 and cluster2.
106        # Since every point is unique in the tests, we could simply use Set
107        # to compare the clusters.
108        for expected_cluster1, expected_cluster2 in tests:
109            points = [Point(*p) for p in expected_cluster1 + expected_cluster2]
110            # A fixed seed is used so that it gets the same shuffles every time.
111            random.shuffle(points, lambda: 0.1234)
112            actual_cluster1, actual_cluster2 = get_two_farthest_clusters(points)
113
114            # The set of the expected sets should be equal to the set of
115            # the actual sets.
116            expected_set1 = Set([Point(*p) for p in expected_cluster1])
117            expected_set2 = Set([Point(*p) for p in expected_cluster2])
118            actual_set1 = Set(actual_cluster1)
119            actual_set2 = Set(actual_cluster2)
120            self.assertTrue(Set([expected_set1, expected_set2]) ==
121                            Set([actual_set1, actual_set2]))
122
123
124if __name__ == '__main__':
125  unittest.main()
126