| # 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. |
| |
| """This module contains unit tests for geometry module.""" |
| |
| |
| import random |
| import unittest |
| |
| import common_unittest_utils |
| |
| from math import sqrt |
| from sets import Set |
| |
| from geometry.elements import Circle, Point |
| from geometry.minicircle import minicircle |
| from geometry.two_farthest_clusters import get_two_farthest_clusters |
| |
| |
| class MinicircleTest(unittest.TestCase): |
| """A class for FirwareSummary unit tests.""" |
| |
| def test_minicircle(self): |
| # a list of points: [center, radius] |
| tests = [ |
| # a right triagnle |
| ([(0, 0), (3, 0), (0, 4)], [(1.5, 2), 2.5]), |
| |
| # an obtuse triagnle |
| ([(1, 1), (3, 0), (0, 4)], [(1.5, 2), 2.5]), |
| |
| # a right triagnle with one point inside |
| ([(0, 0), (1, 1), (3, 0), (0, 4)], [(1.5, 2), 2.5]), |
| |
| # three points at the same coordinates |
| ([(5, 3), (5, 3), (5, 3)], [(5, 3), 0]), |
| |
| # two points at the same coordinates, a diagonal line |
| ([(0, 0), (0, 0), (4, 4)], [(2, 2), 2 * sqrt(2)]), |
| |
| # two points at the same coordinates, a vertical line |
| ([(0, 2), (0, 2), (0, 12)], [(0, 7), 5]), |
| |
| # two points at the same coordinates, a vertical line, one outlier |
| ([(0, 2), (0, 2), (1, 5), (0, 12)], [(0, 7), 5]), |
| |
| # an equilateral triangle |
| ([(0, 0), (10, 0), (5, 5 * sqrt(3))], |
| [(5, 5 * sqrt(3) / 3), 5 * sqrt(3) * 2 / 3]), |
| |
| # an equilateral triangle with a few points inside |
| ([(0, 0), (10, 0), (5, 5 * sqrt(3)), (4, 1), (6, 2), (4.5, 3), |
| (5.2, 2.99), (4.33, 1.78), (5.65, 3.1)], |
| [(5, 5 * sqrt(3) / 3), 5 * sqrt(3) * 2 / 3]), |
| |
| # a list of random points: |
| # Verify with octave geometry package: |
| # > points = [1,1; 1,0; 2,1; 2,2; 12,22; 11,21; 30,30; 31,30; |
| # 30,31; 31,31; 5,35] |
| # > enclosingCircle(points) |
| ([(1, 1), (1, 0), (2, 1), (2, 2), (12, 22), (11, 21), (30, 30), |
| (31, 30), (30, 31), (31, 31), (5, 35)], |
| [(15.39740821, 16.08315335), 21.58594878]), |
| |
| # another list of random points: |
| # Verify with octave geometry package: |
| # > points = [11,11; 11,15; 12,11; 12.5,21.25; 12.77,22.84; 11,21; |
| # 13.3,31; 13.7,33; 14.9,29; 15,10.9; 12.5,13.55] |
| # > enclosingCircle(points) |
| ([(11, 11), (11, 15), (12, 11), (12.5, 21.25), (12.77, 22.84), |
| (11, 21), (13.3, 31), (13.7, 33), (14.9, 29), (15, 10.9), |
| (12.5, 13.55)], |
| [(13.27341679, 21.88667158), 11.12151257]), |
| ] |
| for points, circle_values in tests: |
| center_values, radius = circle_values |
| expected_circle = Circle(Point(*center_values), radius) |
| actual_circle = minicircle(points) |
| self.assertTrue(actual_circle == expected_circle) |
| |
| def test_get_two_farthest_clusters(self): |
| tests = [ |
| # Each row is a tuple of two separated clusters. |
| # two empty lists |
| ([], []), |
| |
| # one point only |
| ([(3.5, 7.886612)], []), |
| |
| # two points only |
| ([(3.5, 7.886612)], [(3.4, 7.02)]), |
| |
| ([(1.2, 0), (2.3, 0), (0, 2.2)], |
| [(10, 5), (11.87, 3.45), (10.55, 7.6)]), |
| |
| ([(100, 3.1), (101.1, 2.9), (99.8, 4.2)], |
| [(1.1, 55.3), (11.87, 73.45), (3.58, 67.7)]), |
| |
| ([(101, 5.5), (102.1, 2.9), (89.8, 4.2), (65.2, 3.3)], |
| [(1.5, 5.3), (1.87, 3.5), (23.8, 14.9), (3.8, 2.7)]), |
| ] |
| |
| # Shuffle the two clusters, and then test the get_two_farthest_clusters |
| # function. It should return cluster1 and cluster2. |
| # Since every point is unique in the tests, we could simply use Set |
| # to compare the clusters. |
| for expected_cluster1, expected_cluster2 in tests: |
| points = [Point(*p) for p in expected_cluster1 + expected_cluster2] |
| # A fixed seed is used so that it gets the same shuffles every time. |
| random.shuffle(points, lambda: 0.1234) |
| actual_cluster1, actual_cluster2 = get_two_farthest_clusters(points) |
| |
| # The set of the expected sets should be equal to the set of |
| # the actual sets. |
| expected_set1 = Set([Point(*p) for p in expected_cluster1]) |
| expected_set2 = Set([Point(*p) for p in expected_cluster2]) |
| actual_set1 = Set(actual_cluster1) |
| actual_set2 = Set(actual_cluster2) |
| self.assertTrue(Set([expected_set1, expected_set2]) == |
| Set([actual_set1, actual_set2])) |
| |
| |
| if __name__ == '__main__': |
| unittest.main() |