#987

Build # #987

Build Type

push

travis-ci

Committed by GitHub

Commit Message

build(deps): bump decode-uri-component in /waves/javascript_demo

Run Details

910 of 910 relevant lines covered (100.0%)

1.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/hyperbolic_tessellation/geometry.py

"""Euclidean geometry functions related to hyperbolic geometry."""

import math
from collections import namedtuple


EPSILON = 1e-8


def are_close(points1, points2):
    for p1, p2 in zip(sorted(points1), sorted(points2)):
        if (p1 - p2).norm() > EPSILON:
            return False
    return True


class Point(namedtuple('Point', ['x', 'y'])):
    """A point class which doubles as a vector class."""

    def norm(self):
        return math.sqrt(inner_product(self, self))

    def normalized(self):
        norm = self.norm()
        return Point(self.x / norm, self.y / norm)

    def project(self, w):
        """Project self onto the input vector w."""
        normalized_w = w.normalized()
        signedLength = inner_product(self, normalized_w)

        return Point(
            normalized_w.x * signedLength,
            normalized_w.y * signedLength)

    def __add__(self, other):
        x, y = other
        return Point(self.x + x, self.y + y)

    def __mul__(self, scalar):
        return Point(scalar * self.x, scalar * self.y)

    def __sub__(self, other):
        x, y = other
        return Point(self.x - x, self.y - y)

    def is_zero(self):
        return math.sqrt(inner_product(self, self)) < EPSILON

    def is_close_to(self, other):
        return (self - other).is_zero()

    def __str__(self):
        return 'Point(x={:.2f}, y={:.2f})'.format(self.x, self.y)

    def __repr__(self):
        return str(self)


def inner_product(v, w):
    return v.x * w.x + v.y * w.y


class Line:
    def __init__(self, point, slope):
        self.point = point
        self.slope = slope

    @staticmethod
    def through(p1, p2):
        """Return a Line through the two given points."""
        if abs(p1.x - p2.x) < EPSILON:
            return VerticalLine.at_point(p1)
        return Line(p1, (p2.y - p1.y) / (p2.x - p1.x))

    def intersect_with(self, line):
        """Compute the intersection of two lines.

        Raise an exception if they do not intersect in a single point.
        """
        if isinstance(line, VerticalLine):
            return line.intersect_with(self)

        if self == line:
            raise ValueError("Can't intersect two identical lines; "
                             "solution is not a single point.")

        if abs(self.slope) < EPSILON and abs(line.slope) < EPSILON:
            raise ValueError("Can't intersect two horizontal lines.")

        x1, y1, slope1 = self.point.x, self.point.y, self.slope
        x2, y2, slope2 = line.point.x, line.point.y, line.slope

        intersection_x = ((slope1 * x1 - slope2 * x2 + y2 - y1)
                          / (slope1 - slope2))
        intersection_y = y1 + slope1 * (intersection_x - x1)

        return Point(intersection_x, intersection_y)

    def y_value(self, x_value):
        """Compute the y value of the point on this line that has the given x
        value.
        """
        return self.slope * (x_value - self.point.x) + self.point.y

    def contains(self, point):
        x, y = point
        return abs(self.y_value(x) - y) < EPSILON

    def reflect(self, point):
        """Reflect a point across this line."""
        translated_to_origin = point - self.point
        projection = translated_to_origin.project(Point(1, self.slope))
        reflection_vector = translated_to_origin - projection
        return projection - reflection_vector + self.point

    def __eq__(self, other):
        if not isinstance(other, Line):
            return False

        if isinstance(other, VerticalLine):
            return other.__eq__(self)

        return (
            abs(self.slope - other.slope) < EPSILON
            and self.contains(other.point)
        )

    def __ne__(self, other):
        return not self.__eq__(other)

    def __str__(self):
        return "Line(point={}, slope={})".format(
            self.point, self.slope)

    def __repr__(self):
        return str(self)


class VerticalLine(Line):
    @staticmethod
    def at_point(point):
        """Return a VerticalLine instance based at the given point."""
        return VerticalLine(Point(point.x, 0), "vertical")

    def y_value(self, x_value):
        raise TypeError("VerticalLine does not support y_value")

    def reflect(self, point):
        """Reflect a point across this line."""
        return Point(2 * self.point.x - point.x, point.y)

    def intersect_with(self, line):
        """Compute the point of intersection of this vertical line with another
        line.

        Raise an exception if they do not intersect or if they are the same line.
        """
        if isinstance(line, VerticalLine):
            raise ValueError("Can't intersect two vertical lines; "
                             "solution is either empty or not a point.")

        return Point(self.point.x, line.y_value(self.point.x))

    def __eq__(self, other):
        return (
            isinstance(other, VerticalLine)
            and abs(self.point.x - other.point.x) < EPSILON
        )


class Circle(namedtuple('Circle', ['center', 'radius'])):
    def contains(self, point):
        """Compute whether a point is on a Euclidean circle."""
        center, radius = (self.center, self.radius)
        return abs(
            (point.x - center.x) ** 2
            + (point.y - center.y) ** 2
            - radius ** 2
        ) < EPSILON

    def tangent_at(self, point):
        """Compute the tangent line to a circle at a point.

        Raise an ValueError if the point is not on the circle.
        """
        if not self.contains(point):
            raise ValueError("Point is not on circle")

        if abs(point.y - self.center.y) < EPSILON:
            return VerticalLine.at_point(point)

        slope = -(point.x - self.center.x) / (point.y - self.center.y)
        return Line(point, slope)

    def invert_point(self, point):
        """Compute the inverse of a point with respect to a self.

        Raises a ValueError if the point to be inverted is the center
        of the circle.
        """
        x, y = point
        center, radius = (self.center, self.radius)
        square_norm = (x - center.x) ** 2 + (y - center.y) ** 2

        if math.sqrt(square_norm) < EPSILON:
            raise ValueError(
                "Can't invert the center of a circle in that same circle.")

        x_inverted = center.x + radius ** 2 * (x - center.x) / square_norm
        y_inverted = center.y + radius ** 2 * (y - center.y) / square_norm
        return Point(x_inverted, y_inverted)

    def intersect_with_line(self, line):
        """Return a possibly empty set containing the points of intersection
        of the context circle and the given line.
        """
        m = line.slope
        x, y = line.point.x, line.point.y
        c_x, c_y, r = self.center.x, self.center.y, self.radius
        if isinstance(line, VerticalLine):
            discriminant = r ** 2 - (x - c_x)**2
            if abs(discriminant) < EPSILON:
                discriminant = 0

            if discriminant < 0:
                return set()

            sqrt_disc = math.sqrt(discriminant)
            return set([
                Point(x, c_y + sqrt_disc),
                Point(x, c_y - sqrt_disc),
            ])
        else:
            A = m ** 2 + 1
            B = 2 * (m * y - m * c_y - c_x - m ** 2 * x)
            C = (
                c_x ** 2 + (m * x) ** 2 + (y - c_y) ** 2
                - 2 * m * x * y + 2 * m * x * c_y - r ** 2
            )
            discriminant = B * B - 4 * A * C
            if abs(discriminant) < EPSILON:
                discriminant = 0

            if discriminant < 0:
                return set()

            sqrt_disc = math.sqrt(discriminant)
            x_values = set([
                (-B + sqrt_disc) / (2 * A),
                (-B - sqrt_disc) / (2 * A),
            ])
            return set(
                Point(x, line.y_value(x)) for x in x_values
            )


def distance(p1, p2):
    """Compute the usual Euclidean plane distance between two points."""
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] + p2[1]) ** 2)


def det3(A):
    """Compute the determinant of a 3x3 matrix"""
    if not (len(A) == 3 and len(A[0]) == 3):
        raise ValueError("Bad matrix dims")

    return (
        A[0][0] * (A[1][1] * A[2][2] - A[1][2] * A[2][1])
        - A[0][1] * (A[1][0] * A[2][2] - A[1][2] * A[2][0])
        + A[0][2] * (A[1][0] * A[2][1] - A[1][1] * A[2][0])
    )


def remove_column(A, removed_col_index):
    return [
        [entry for j, entry in enumerate(row) if j != removed_col_index]
        for row in A
    ]


def orientation(a, b, c):
    """Compute the orientation of three points visited in sequence, either
    'clockwise', 'counterclockwise', or 'collinear'.
    """
    a_x, a_y = a
    b_x, b_y = b
    c_x, c_y = c
    value = (b_x - a_x) * (c_y - a_y) - (c_x - a_x) * (b_y - a_y)

    if (value > EPSILON):
        return 'counterclockwise'
    elif (value < -EPSILON):
        return 'clockwise'
    else:
        return 'collinear'


def circle_through_points_perpendicular_to_circle(point1, point2, circle):
    """Return a Circle that passes through the two given points and
    intersects the given circle at a perpendicular angle.

    A hyperbolic line between two points is computed as the circle arc
    perpendicular to the boundary circle that passes between those points.
    This can be constructed by first inverting one of the points in the
    circle, then constructing the circle passing through all three points.

    There are two cases when this may fail:

    (1) If the two points and the center of the input circle lie on a common
    line, then the hyperbolic line is a diameter of the circle. This function
    raises a ValueError in this case.

    (2) If the input points lie on the circle, then the inversion is a no-op.
    In this case we can compute the center of the desired circle as the point
    of intersection of the two tangent lines of the points.
    """
    if circle.contains(point1):
        if circle.contains(point2):
            circle_center = intersection_of_common_tangents(
                circle, point1, point2)
            radius = distance(circle_center, point1)
            return Circle(circle_center, radius)

        point3 = circle.invert_point(point2)
    else:
        point3 = circle.invert_point(point1)

    def row(point):
        (x, y) = point
        return [x ** 2 + y ** 2, x, y, 1]

    """The equation for the center of the circle passing through three points
    is given by the ratios of determinants of a cleverly chosen matrix. This
    corresponds to solving a system of three equations and three unknowns of
    the following form, where the unknowns are x0, y0, and r and the values x,
    y are set to the three points we wish the circle to pass through.

        (x - x0)^2 + (y - y0)^2 = r^2
    """
    M = [
        row(point1),
        row(point2),
        row(point3),
    ]

    detminor_1_1 = det3(remove_column(M, 0))
    if orientation(circle.center, point1, point2) == "collinear":
        raise ValueError("input points {} {} lie on a line with the "
                         "center of the circle {}".format(point1, point2, circle))

    # detminor stands for "determinant of (matrix) minor"
    detminor_1_2 = det3(remove_column(M, 1))
    detminor_1_3 = det3(remove_column(M, 2))
    detminor_1_4 = det3(remove_column(M, 3))

    circle_center_x = 0.5 * detminor_1_2 / detminor_1_1
    circle_center_y = -0.5 * detminor_1_3 / detminor_1_1
    circle_radius = (
        circle_center_x ** 2
        + circle_center_y ** 2
        + detminor_1_4 / detminor_1_1
    ) ** 0.5

    return Circle(Point(circle_center_x, circle_center_y), circle_radius)


def rotate_around_origin(angle, point):
    """Rotate the given point about the origin by the given angle (in radians).
    For the disk model, this is the same operation in Euclidean space: the
    application of a 2x2 rotation matrix.
    """
    rotation_matrix = [
        [math.cos(angle), -math.sin(angle)],
        [math.sin(angle), math.cos(angle)],
    ]

    x, y = point
    return Point(
        rotation_matrix[0][0] * x + rotation_matrix[0][1] * y,
        rotation_matrix[1][0] * x + rotation_matrix[1][1] * y,
    )


def intersection_of_common_tangents(circle, point1, point2):
    line1 = circle.tangent_at(point1)
    line2 = circle.tangent_at(point2)
    return line1.intersect_with(line2)


def bounding_box_area(points):
    max_x = max(p.x for p in points)
    max_y = max(p.y for p in points)
    min_x = min(p.x for p in points)
    min_y = min(p.y for p in points)

    return (max_y - min_y) * (max_x - min_x)

1	"""Euclidean geometry functions related to hyperbolic geometry."""
2
3	import math	1✔
4	from collections import namedtuple	1✔
5
6
7	EPSILON = 1e-8	1✔
8
9
10	def are_close(points1, points2):	1✔
11	for p1, p2 in zip(sorted(points1), sorted(points2)):	1✔
12	if (p1 - p2).norm() > EPSILON:	1✔
13	return False	1✔
14	return True	1✔
15
16
17	class Point(namedtuple('Point', ['x', 'y'])):	1✔
18	"""A point class which doubles as a vector class."""
19
20	def norm(self):	1✔
21	return math.sqrt(inner_product(self, self))	1✔
22
23	def normalized(self):	1✔
24	norm = self.norm()	1✔
25	return Point(self.x / norm, self.y / norm)	1✔
26
27	def project(self, w):	1✔
28	"""Project self onto the input vector w."""
29	normalized_w = w.normalized()	1✔
30	signedLength = inner_product(self, normalized_w)	1✔
31
32	return Point(	1✔
33	normalized_w.x * signedLength,
34	normalized_w.y * signedLength)
35
36	def __add__(self, other):	1✔
37	x, y = other	1✔
38	return Point(self.x + x, self.y + y)	1✔
39
40	def __mul__(self, scalar):	1✔
41	return Point(scalar * self.x, scalar * self.y)	1✔
42
43	def __sub__(self, other):	1✔
44	x, y = other	1✔
45	return Point(self.x - x, self.y - y)	1✔
46
47	def is_zero(self):	1✔
48	return math.sqrt(inner_product(self, self)) < EPSILON	1✔
49
50	def is_close_to(self, other):	1✔
51	return (self - other).is_zero()	1✔
52
53	def __str__(self):	1✔
54	return 'Point(x={:.2f}, y={:.2f})'.format(self.x, self.y)	1✔
55
56	def __repr__(self):
57	return str(self)
58
59
60	def inner_product(v, w):	1✔
61	return v.x * w.x + v.y * w.y	1✔
62
63
64	class Line:	1✔
65	def __init__(self, point, slope):	1✔
66	self.point = point	1✔
67	self.slope = slope	1✔
68
69	@staticmethod	1✔
70	def through(p1, p2):
71	"""Return a Line through the two given points."""
72	if abs(p1.x - p2.x) < EPSILON:	1✔
73	return VerticalLine.at_point(p1)	1✔
74	return Line(p1, (p2.y - p1.y) / (p2.x - p1.x))	1✔
75
76	def intersect_with(self, line):	1✔
77	"""Compute the intersection of two lines.
78
79	Raise an exception if they do not intersect in a single point.
80	"""
81	if isinstance(line, VerticalLine):	1✔
82	return line.intersect_with(self)	1✔
83
84	if self == line:	1✔
85	raise ValueError("Can't intersect two identical lines; "	1✔
86	"solution is not a single point.")
87
88	if abs(self.slope) < EPSILON and abs(line.slope) < EPSILON:	1✔
89	raise ValueError("Can't intersect two horizontal lines.")	1✔
90
91	x1, y1, slope1 = self.point.x, self.point.y, self.slope	1✔
92	x2, y2, slope2 = line.point.x, line.point.y, line.slope	1✔
93
94	intersection_x = ((slope1 * x1 - slope2 * x2 + y2 - y1)	1✔
95	/ (slope1 - slope2))
96	intersection_y = y1 + slope1 * (intersection_x - x1)	1✔
97
98	return Point(intersection_x, intersection_y)	1✔
99
100	def y_value(self, x_value):	1✔
101	"""Compute the y value of the point on this line that has the given x
102	value.
103	"""
104	return self.slope * (x_value - self.point.x) + self.point.y	1✔
105
106	def contains(self, point):	1✔
107	x, y = point	1✔
108	return abs(self.y_value(x) - y) < EPSILON	1✔
109
110	def reflect(self, point):	1✔
111	"""Reflect a point across this line."""
112	translated_to_origin = point - self.point	1✔
113	projection = translated_to_origin.project(Point(1, self.slope))	1✔
114	reflection_vector = translated_to_origin - projection	1✔
115	return projection - reflection_vector + self.point	1✔
116
117	def __eq__(self, other):	1✔
118	if not isinstance(other, Line):	1✔
119	return False	1✔
120
121	if isinstance(other, VerticalLine):	1✔
122	return other.__eq__(self)	1✔
123
124	return (	1✔
125	abs(self.slope - other.slope) < EPSILON
126	and self.contains(other.point)
127	)
128
129	def __ne__(self, other):	1✔
130	return not self.__eq__(other)	1✔
131
132	def __str__(self):	1✔
133	return "Line(point={}, slope={})".format(	1✔
134	self.point, self.slope)
135
136	def __repr__(self):
137	return str(self)
138
139
140	class VerticalLine(Line):	1✔
141	@staticmethod	1✔
142	def at_point(point):
143	"""Return a VerticalLine instance based at the given point."""
144	return VerticalLine(Point(point.x, 0), "vertical")	1✔
145
146	def y_value(self, x_value):	1✔
147	raise TypeError("VerticalLine does not support y_value")	1✔
148
149	def reflect(self, point):	1✔
150	"""Reflect a point across this line."""
151	return Point(2 * self.point.x - point.x, point.y)	1✔
152
153	def intersect_with(self, line):	1✔
154	"""Compute the point of intersection of this vertical line with another
155	line.
156
157	Raise an exception if they do not intersect or if they are the same line.
158	"""
159	if isinstance(line, VerticalLine):	1✔
160	raise ValueError("Can't intersect two vertical lines; "	1✔
161	"solution is either empty or not a point.")
162
163	return Point(self.point.x, line.y_value(self.point.x))	1✔
164
165	def __eq__(self, other):	1✔
166	return (	1✔
167	isinstance(other, VerticalLine)
168	and abs(self.point.x - other.point.x) < EPSILON
169	)
170
171
172	class Circle(namedtuple('Circle', ['center', 'radius'])):	1✔
173	def contains(self, point):	1✔
174	"""Compute whether a point is on a Euclidean circle."""
175	center, radius = (self.center, self.radius)	1✔
176	return abs(	1✔
177	(point.x - center.x) ** 2
178	+ (point.y - center.y) ** 2
179	- radius ** 2
180	) < EPSILON
181
182	def tangent_at(self, point):	1✔
183	"""Compute the tangent line to a circle at a point.
184
185	Raise an ValueError if the point is not on the circle.
186	"""
187	if not self.contains(point):	1✔
188	raise ValueError("Point is not on circle")	1✔
189
190	if abs(point.y - self.center.y) < EPSILON:	1✔
191	return VerticalLine.at_point(point)	1✔
192
193	slope = -(point.x - self.center.x) / (point.y - self.center.y)	1✔
194	return Line(point, slope)	1✔
195
196	def invert_point(self, point):	1✔
197	"""Compute the inverse of a point with respect to a self.
198
199	Raises a ValueError if the point to be inverted is the center
200	of the circle.
201	"""
202	x, y = point	1✔
203	center, radius = (self.center, self.radius)	1✔
204	square_norm = (x - center.x) 2 + (y - center.y) 2	1✔
205
206	if math.sqrt(square_norm) < EPSILON:	1✔
207	raise ValueError(	1✔
208	"Can't invert the center of a circle in that same circle.")
209
210	x_inverted = center.x + radius ** 2 * (x - center.x) / square_norm	1✔
211	y_inverted = center.y + radius ** 2 * (y - center.y) / square_norm	1✔
212	return Point(x_inverted, y_inverted)	1✔
213
214	def intersect_with_line(self, line):	1✔
215	"""Return a possibly empty set containing the points of intersection
216	of the context circle and the given line.
217	"""
218	m = line.slope	1✔
219	x, y = line.point.x, line.point.y	1✔
220	c_x, c_y, r = self.center.x, self.center.y, self.radius	1✔
221	if isinstance(line, VerticalLine):	1✔
222	discriminant = r 2 - (x - c_x)2	1✔
223	if abs(discriminant) < EPSILON:	1✔
224	discriminant = 0	1✔
225
226	if discriminant < 0:	1✔
227	return set()	1✔
228
229	sqrt_disc = math.sqrt(discriminant)	1✔
230	return set([	1✔
231	Point(x, c_y + sqrt_disc),
232	Point(x, c_y - sqrt_disc),
233	])
234	else:
235	A = m ** 2 + 1	1✔
236	B = 2 * (m * y - m * c_y - c_x - m ** 2 * x)	1✔
237	C = (	1✔
238	c_x ** 2 + (m * x) 2 + (y - c_y) 2
239	- 2 * m * x * y + 2 * m * x * c_y - r ** 2
240	)
241	discriminant = B * B - 4 * A * C	1✔
242	if abs(discriminant) < EPSILON:	1✔
243	discriminant = 0	1✔
244
245	if discriminant < 0:	1✔
246	return set()	1✔
247
248	sqrt_disc = math.sqrt(discriminant)	1✔
249	x_values = set([	1✔
250	(-B + sqrt_disc) / (2 * A),
251	(-B - sqrt_disc) / (2 * A),
252	])
253	return set(	1✔
254	Point(x, line.y_value(x)) for x in x_values
255	)
256
257
258	def distance(p1, p2):	1✔
259	"""Compute the usual Euclidean plane distance between two points."""
260	return math.sqrt((p1[0] - p2[0]) 2 + (p1[1] + p2[1]) 2)	1✔
261
262
263	def det3(A):	1✔
264	"""Compute the determinant of a 3x3 matrix"""
265	if not (len(A) == 3 and len(A[0]) == 3):	1✔
266	raise ValueError("Bad matrix dims")	1✔
267
268	return (	1✔
269	A[0][0] * (A[1][1] * A[2][2] - A[1][2] * A[2][1])
270	- A[0][1] * (A[1][0] * A[2][2] - A[1][2] * A[2][0])
271	+ A[0][2] * (A[1][0] * A[2][1] - A[1][1] * A[2][0])
272	)
273
274
275	def remove_column(A, removed_col_index):	1✔
276	return [	1✔
277	[entry for j, entry in enumerate(row) if j != removed_col_index]
278	for row in A
279	]
280
281
282	def orientation(a, b, c):	1✔
283	"""Compute the orientation of three points visited in sequence, either
284	'clockwise', 'counterclockwise', or 'collinear'.
285	"""
286	a_x, a_y = a	1✔
287	b_x, b_y = b	1✔
288	c_x, c_y = c	1✔
289	value = (b_x - a_x) * (c_y - a_y) - (c_x - a_x) * (b_y - a_y)	1✔
290
291	if (value > EPSILON):	1✔
292	return 'counterclockwise'	1✔
293	elif (value < -EPSILON):	1✔
294	return 'clockwise'	1✔
295	else:
296	return 'collinear'	1✔
297
298
299	def circle_through_points_perpendicular_to_circle(point1, point2, circle):	1✔
300	"""Return a Circle that passes through the two given points and
301	intersects the given circle at a perpendicular angle.
302
303	A hyperbolic line between two points is computed as the circle arc
304	perpendicular to the boundary circle that passes between those points.
305	This can be constructed by first inverting one of the points in the
306	circle, then constructing the circle passing through all three points.
307
308	There are two cases when this may fail:
309
310	(1) If the two points and the center of the input circle lie on a common
311	line, then the hyperbolic line is a diameter of the circle. This function
312	raises a ValueError in this case.
313
314	(2) If the input points lie on the circle, then the inversion is a no-op.
315	In this case we can compute the center of the desired circle as the point
316	of intersection of the two tangent lines of the points.
317	"""
318	if circle.contains(point1):	1✔
319	if circle.contains(point2):	1✔
320	circle_center = intersection_of_common_tangents(	1✔
321	circle, point1, point2)
322	radius = distance(circle_center, point1)	1✔
323	return Circle(circle_center, radius)	1✔
324
325	point3 = circle.invert_point(point2)	1✔
326	else:
327	point3 = circle.invert_point(point1)	1✔
328
329	def row(point):	1✔
330	(x, y) = point	1✔
331	return [x 2 + y 2, x, y, 1]	1✔
332
333	"""The equation for the center of the circle passing through three points
334	is given by the ratios of determinants of a cleverly chosen matrix. This
335	corresponds to solving a system of three equations and three unknowns of
336	the following form, where the unknowns are x0, y0, and r and the values x,
337	y are set to the three points we wish the circle to pass through.
338
339	(x - x0)^2 + (y - y0)^2 = r^2
340	"""
341	M = [	1✔
342	row(point1),
343	row(point2),
344	row(point3),
345	]
346
347	detminor_1_1 = det3(remove_column(M, 0))	1✔
348	if orientation(circle.center, point1, point2) == "collinear":	1✔
349	raise ValueError("input points {} {} lie on a line with the "	1✔
350	"center of the circle {}".format(point1, point2, circle))
351
352	# detminor stands for "determinant of (matrix) minor"
353	detminor_1_2 = det3(remove_column(M, 1))	1✔
354	detminor_1_3 = det3(remove_column(M, 2))	1✔
355	detminor_1_4 = det3(remove_column(M, 3))	1✔
356
357	circle_center_x = 0.5 * detminor_1_2 / detminor_1_1	1✔
358	circle_center_y = -0.5 * detminor_1_3 / detminor_1_1	1✔
359	circle_radius = (	1✔
360	circle_center_x ** 2
361	+ circle_center_y ** 2
362	+ detminor_1_4 / detminor_1_1
363	) ** 0.5
364
365	return Circle(Point(circle_center_x, circle_center_y), circle_radius)	1✔
366
367
368	def rotate_around_origin(angle, point):	1✔
369	"""Rotate the given point about the origin by the given angle (in radians).
370	For the disk model, this is the same operation in Euclidean space: the
371	application of a 2x2 rotation matrix.
372	"""
373	rotation_matrix = [	1✔
374	[math.cos(angle), -math.sin(angle)],
375	[math.sin(angle), math.cos(angle)],
376	]
377
378	x, y = point	1✔
379	return Point(	1✔
380	rotation_matrix[0][0] * x + rotation_matrix[0][1] * y,
381	rotation_matrix[1][0] * x + rotation_matrix[1][1] * y,
382	)
383
384
385	def intersection_of_common_tangents(circle, point1, point2):	1✔
386	line1 = circle.tangent_at(point1)	1✔
387	line2 = circle.tangent_at(point2)	1✔
388	return line1.intersect_with(line2)	1✔
389
390
391	def bounding_box_area(points):	1✔
392	max_x = max(p.x for p in points)	1✔
393	max_y = max(p.y for p in points)	1✔
394	min_x = min(p.x for p in points)	1✔
395	min_y = min(p.y for p in points)	1✔
396
397	return (max_y - min_y) * (max_x - min_x)	1✔

pim-book / programmers-introduction-to-mathematics / #987

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous