cos / mirrors / cros / chromiumos / third_party / autotest / refs/heads/stabilize-R33-4982.B / . / client / site_tests / firmware_TouchMTB / geometry / minicircle.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. | |

"""minicircle: calculating the minimal enclosing circle given a set of points | |

Reference: | |

[1] Emo Welzl. Smallest enclosing disks (balls and ellipsoids). | |

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1450 | |

[2] Circumscribed circle. http://en.wikipedia.org/wiki/Circumscribed_circle | |

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

""" | |

import copy | |

from sets import Set | |

from elements import Point, Circle | |

def _mini_circle_2_points(p1, p2): | |

"""Derive the mini circle with p1 and p2 composing the diameter. | |

This also handles the special case when p1 and p2 are located at | |

the same coordinate. | |

""" | |

center = Point((p1.x + p2.x) * 0.5, (p1.y + p2.y) * 0.5) | |

radius = center.distance(p1) | |

return Circle(center, radius) | |

def _mini_circle_3_points(A, B, C): | |

"""Derive the mini circle enclosing arbitrary three points, A, B, C. | |

@param A: a point (possibly a vertex of a triangle) | |

@param B: a point (possibly a vertex of a triangle) | |

@param C: a point (possibly a vertex of a triangle) | |

""" | |

# Check if this is an obtuse triangle or a right triangle, | |

# including the special cases | |

# (1) the 3 points are on the same line | |

# (2) any 2 points are located at the same coordinate | |

# (3) all 3 points are located at the same coordinate | |

a = B.distance(C) | |

b = C.distance(A) | |

c = A.distance(B) | |

if (a ** 2 >= b ** 2 + c ** 2): | |

return _mini_circle_2_points(B, C) | |

elif (b ** 2 >= c ** 2 + a ** 2): | |

return _mini_circle_2_points(C, A) | |

elif (c ** 2 >= a ** 2 + b ** 2): | |

return _mini_circle_2_points(A, B) | |

# It is an acute triangle. Refer to Reference [2]. | |

D = 2 * (A.x * (B.y - C.y) + B.x *(C.y - A.y) + C.x * (A.y - B.y)) | |

x = ((A.x ** 2 + A.y ** 2) * (B.y - C.y) + | |

(B.x ** 2 + B.y ** 2) * (C.y - A.y) + | |

(C.x ** 2 + C.y ** 2) * (A.y - B.y)) / D | |

y = ((A.x ** 2 + A.y ** 2) * (C.x - B.x) + | |

(B.x ** 2 + B.y ** 2) * (A.x - C.x) + | |

(C.x ** 2 + C.y ** 2) * (B.x - A.x)) / D | |

center = Point(x, y) | |

radius = center.distance(A) | |

return Circle(center, radius) | |

def _b_minicircle0(R): | |

"""build minicircle0: build the mini circle with an empty P and has R | |

on the boundary. | |

@param R: boundary points, a set of points which should be on the boundary | |

of the circle to be built | |

""" | |

if len(R) == 0: | |

return Circle(None, None) | |

if len(R) == 1: | |

return Circle(R.pop(), 0) | |

elif len(R) == 2: | |

p1 = R.pop() | |

p2 = R.pop() | |

return _mini_circle_2_points(p1, p2) | |

else: | |

return _mini_circle_3_points(*list(R)) | |

def _b_minicircle(P, R): | |

"""build minicircle: build the mini circle enclosing P and has R on the | |

boundary. | |

@param P: a set of points that should be enclosed in the circle to be built | |

@param R: boundary points, a set of points which should be on the boundary | |

of the circle to be built | |

""" | |

P = copy.deepcopy(P) | |

R = copy.deepcopy(R) | |

if len(P) == 0 or len(R) == 3: | |

D = _b_minicircle0(R) | |

else: | |

p = P.pop() | |

D = _b_minicircle(P, R) | |

if (not D) or (p not in D): | |

R.add(p) | |

D = _b_minicircle(P, R) | |

return D | |

def _make_Set_of_Points(points): | |

"""Convert the points to a set of Point objects. | |

@param points: could be a list/set of pairs_of_ints/Point_objects. | |

""" | |

return Set([p if isinstance(p, Point) else Point(*p) for p in points]) | |

def minicircle(points): | |

"""Get the minimal enclosing circle of the points. | |

@param points: a list of points which should be enclosed in the circle to be | |

built | |

""" | |

P = _make_Set_of_Points(points) | |

return _b_minicircle(P, Set()) if P else None |