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 8 import random 9 import unittest 10 11 import common_unittest_utils 12 13 from math import sqrt 14 from sets import Set 15 16 from geometry.elements import Circle, Point 17 from geometry.minicircle import minicircle 18 from geometry.two_farthest_clusters import get_two_farthest_clusters 19 20 21 class 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 124 if __name__ == '__main__': 125 unittest.main() 126
