# # Smallest enclosing circle - Test suite (Python) # # Copyright (c) 2017 Project Nayuki # https://www.nayuki.io/page/smallest-enclosing-circle # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU Lesser General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU Lesser General Public License for more details. # # You should have received a copy of the GNU Lesser General Public License # along with this program (see COPYING.txt and COPYING.LESSER.txt). # If not, see . # import random, unittest import smallestenclosingcircle # ---- Test suite functions ---- class SmallestEnclosingCircleTest(unittest.TestCase): def test_matching_naive_algorithm(self): TRIALS = 1000 for _ in range(TRIALS): points = _make_random_points(random.randint(1, 30)) reference = _smallest_enclosing_circle_naive(points) actual = smallestenclosingcircle.make_circle(points) self.assertAlmostEqual(actual[0], reference[0], delta=_EPSILON) self.assertAlmostEqual(actual[1], reference[1], delta=_EPSILON) self.assertAlmostEqual(actual[2], reference[2], delta=_EPSILON) def test_translation(self): TRIALS = 100 CHECKS = 10 for _ in range(TRIALS): points = _make_random_points(random.randint(1, 300)) reference = smallestenclosingcircle.make_circle(points) for _ in range(CHECKS): dx = random.gauss(0, 1) dy = random.gauss(0, 1) newpoints = [(x + dx, y + dy) for (x, y) in points] translated = smallestenclosingcircle.make_circle(newpoints) self.assertAlmostEqual(translated[0], reference[0] + dx, delta=_EPSILON) self.assertAlmostEqual(translated[1], reference[1] + dy, delta=_EPSILON) self.assertAlmostEqual(translated[2], reference[2] , delta=_EPSILON) def test_scaling(self): TRIALS = 100 CHECKS = 10 for _ in range(TRIALS): points = _make_random_points(random.randint(1, 300)) reference = smallestenclosingcircle.make_circle(points) for _ in range(CHECKS): scale = random.gauss(0, 1) newpoints = [(x * scale, y * scale) for (x, y) in points] scaled = smallestenclosingcircle.make_circle(newpoints) self.assertAlmostEqual(scaled[0], reference[0] * scale , delta=_EPSILON) self.assertAlmostEqual(scaled[1], reference[1] * scale , delta=_EPSILON) self.assertAlmostEqual(scaled[2], reference[2] * abs(scale), delta=_EPSILON) # ---- Helper functions ---- def _make_random_points(n): if random.random() < 0.2: # Discrete lattice (to have a chance of duplicated points) return [(random.randrange(10), random.randrange(10)) for _ in range(n)] else: # Gaussian distribution return [(random.gauss(0, 1), random.gauss(0, 1)) for _ in range(n)] # Returns the smallest enclosing circle in O(n^4) time using the naive algorithm. def _smallest_enclosing_circle_naive(points): # Degenerate cases if len(points) == 0: return None elif len(points) == 1: return (points[0][0], points[0][1], 0) # Try all unique pairs result = None for i in range(len(points)): p = points[i] for j in range(i + 1, len(points)): q = points[j] c = smallestenclosingcircle.make_diameter(p, q) if (result is None or c[2] < result[2]) and \ all(smallestenclosingcircle.is_in_circle(c, r) for r in points): result = c if result is not None: return result # This optimization is not mathematically proven # Try all unique triples for i in range(len(points)): p = points[i] for j in range(i + 1, len(points)): q = points[j] for k in range(j + 1, len(points)): r = points[k] c = smallestenclosingcircle.make_circumcircle(p, q, r) if c is not None and (result is None or c[2] < result[2]) and \ all(smallestenclosingcircle.is_in_circle(c, s) for s in points): result = c if result is None: raise AssertionError() return result _EPSILON = 1e-12 # ---- Main runner ---- if __name__ == "__main__": unittest.main()