"""Geometry functions.
Rectangle is a utility class for working with rectangles (unions and
intersections).
A point is represented as a tuple `(x, y)`.
"""
from __future__ import annotations
from math import sqrt
from typing import Iterator, Tuple
Point = Tuple[float, float] # x, y
Rect = Tuple[float, float, float, float] # x, y, width, height
[docs]
class Rectangle:
"""Python Rectangle implementation. Rectangles can be added (union),
substituted (intersection) and points and rectangles can be tested to be in
the rectangle.
>>> r1= Rectangle(1,1,5,5)
>>> r2 = Rectangle(3,3,6,7)
Test if two rectangles intersect:
>>> if r1 - r2: 'yes'
'yes'
>>> r1, r2 = Rectangle(1,2,3,4), Rectangle(1,2,3,4)
>>> r1 == r2
True
>>> r = Rectangle(-5, 3, 10, 8)
>>> r.width = 2
>>> r
Rectangle(-5, 3, 2, 8)
>>> r = Rectangle(-5, 3, 10, 8)
>>> r.height = 2
>>> r
Rectangle(-5, 3, 10, 2)
"""
def __init__(
self,
x: float = 0,
y: float = 0,
width: float | None = None,
height: float | None = None,
x1: float = 0,
y1: float = 0,
):
if width is None:
self.x = min(x, x1)
self.width = abs(x1 - x)
else:
self.x = x
self.width = width
if height is None:
self.y = min(y, y1)
self.height = abs(y1 - y)
else:
self.y = y
self.height = height
@property
def x1(self) -> float:
return self.x + self.width
@x1.setter
def x1(self, x1: float) -> None:
width = x1 - self.x
width = max(width, 0)
self.width = width
@property
def y1(self) -> float:
return self.y + self.height
@y1.setter
def y1(self, y1: float) -> None:
height = y1 - self.y
height = max(height, 0)
self.height = height
[docs]
def expand(self, delta: float) -> None:
"""
>>> r = Rectangle(-5, 3, 10, 8)
>>> r.expand(5)
>>> r
Rectangle(-10, -2, 20, 18)
"""
self.x -= delta
self.y -= delta
self.width += delta * 2
self.height += delta * 2
[docs]
def tuple(self) -> tuple[float, float, float, float]:
"""A type safe version of `tuple(rectangle)`."""
return (self.x, self.y, self.width, self.height)
def __repr__(self) -> str:
"""
>>> Rectangle(5,7,20,25)
Rectangle(5, 7, 20, 25)
"""
if self:
return f"{self.__class__.__name__}({self.x}, {self.y}, {self.width}, {self.height})"
return f"{self.__class__.__name__}()"
def __iter__(self) -> Iterator[float]:
"""
>>> tuple(Rectangle(1,2,3,4))
(1, 2, 3, 4)
"""
return iter((self.x, self.y, self.width, self.height))
def __getitem__(self, index: int) -> float:
"""
>>> Rectangle(1,2,3,4)[1]
2
"""
return (self.x, self.y, self.width, self.height)[index]
def __bool__(self) -> bool:
"""
>>> r=Rectangle(1,2,3,4)
>>> if r: 'yes'
'yes'
>>> r = Rectangle(1,1,0,0)
>>> if r: 'no'
"""
return self.width > 0 and self.height > 0
def __eq__(self, other: object) -> bool:
return (
isinstance(other, Rectangle)
and self.x == other.x
and self.y == other.y
and self.width == other.width
and self.height == other.height
)
def __add__(self, obj: Rectangle | Rect) -> Rectangle:
"""Create a new Rectangle is the union of the current rectangle with
another Rectangle, tuple `(x,y)` or tuple `(x, y, width, height)`.
>>> r=Rectangle(5, 7, 20, 25)
>>> r + (0, 0)
Traceback (most recent call last):
...
TypeError: Can only add Rectangle or tuple (x, y, width, height), not (0, 0).
>>> r + (20, 30, 40, 50)
Rectangle(5, 7, 55, 73)
"""
return Rectangle(self.x, self.y, self.width, self.height).__iadd__(obj)
def __iadd__(self, obj: Rectangle | Rect) -> Rectangle:
"""
>>> r = Rectangle()
>>> r += Rectangle(5, 7, 20, 25)
>>> r += (0, 0, 30, 10)
>>> r
Rectangle(0, 0, 30, 32)
>>> r += 'aap'
Traceback (most recent call last):
...
TypeError: Can only add Rectangle or tuple (x, y, width, height), not 'aap'.
"""
try:
x, y, width, height = obj
except ValueError as e:
raise TypeError(
f"Can only add Rectangle or tuple (x, y, width, height), not {obj!r}."
) from e
x1, y1 = x + width, y + height
if self:
ox1, oy1 = self.x + self.width, self.y + self.height
self.x = min(self.x, x)
self.y = min(self.y, y)
self.x1 = max(ox1, x1)
self.y1 = max(oy1, y1)
else:
self.x, self.y, self.width, self.height = x, y, width, height
return self
def __sub__(self, obj: Rectangle | Rect) -> Rectangle:
"""Create a new Rectangle is the union of the current rectangle with
another Rectangle or tuple (x, y, width, height).
>>> r = Rectangle(5, 7, 20, 25)
>>> r - (20, 30, 40, 50)
Rectangle(20, 30, 5, 2)
>>> r - (30, 40, 40, 50)
Rectangle()
"""
return Rectangle(self.x, self.y, self.width, self.height).__isub__(obj)
def __isub__(self, obj: Rectangle | Rect) -> Rectangle:
"""
>>> r = Rectangle()
>>> r -= Rectangle(5, 7, 20, 25)
>>> r -= (0, 0, 30, 10)
>>> r
Rectangle(5, 7, 20, 3)
>>> r -= 'aap'
Traceback (most recent call last):
...
TypeError: Can only subtract Rectangle or tuple (x, y, width, height), not 'aap'.
"""
try:
x, y, width, height = obj
except ValueError as e:
raise TypeError(
f"Can only subtract Rectangle or tuple (x, y, width, height), not {obj!r}."
) from e
x1, y1 = x + width, y + height
if self:
ox1, oy1 = self.x + self.width, self.y + self.height
self.x = max(self.x, x)
self.y = max(self.y, y)
self.x1 = min(ox1, x1)
self.y1 = min(oy1, y1)
else:
self.x, self.y, self.width, self.height = x, y, width, height
return self
def __contains__(self, obj: Rectangle | Rect | Point) -> bool:
"""Check if a point `(x, y)` in inside rectangle `(x, y, width,
height)` or if a rectangle instance is inside with the rectangle.
>>> r=Rectangle(10, 5, 12, 12)
>>> (0, 0) in r
False
>>> (10, 6) in r
True
>>> (12, 12) in r
True
>>> (100, 4) in r
False
>>> (11, 6, 5, 5) in r
True
>>> (11, 6, 15, 15) in r
False
>>> Rectangle(11, 6, 5, 5) in r
True
>>> Rectangle(11, 6, 15, 15) in r
False
>>> 'aap' in r
Traceback (most recent call last):
...
TypeError: Should compare to Rectangle, tuple (x, y, width, height) or point (x, y), not 'aap'.
"""
try:
x, y, width, height = obj # type: ignore[misc]
x1, y1 = x + width, y + width
except ValueError:
# point
try:
(x, y) = (x1, y1) = obj # type: ignore[misc]
except ValueError as e:
raise TypeError(
f"Should compare to Rectangle, tuple (x, y, width, height) or point (x, y), not {obj!r}."
) from e
return x >= self.x and x1 <= self.x1 and y >= self.y and y1 <= self.y1
[docs]
def distance_point_point(point1: Point, point2: Point = (0.0, 0.0)) -> float:
"""Return the distance from point ``point1`` to ``point2``.
>>> f"{distance_point_point((0,0), (1,1)):.3f}"
'1.414'
"""
dx = point1[0] - point2[0]
dy = point1[1] - point2[1]
return sqrt(dx * dx + dy * dy)
[docs]
def distance_point_point_fast(point1: Point, point2: Point = (0.0, 0.0)) -> float:
"""Return the distance from point ``point1`` to ``point2``. This version is
faster than ``distance_point_point()``, but less precise.
>>> distance_point_point_fast((0,0), (1,1))
2
"""
dx = point1[0] - point2[0]
dy = point1[1] - point2[1]
return abs(dx) + abs(dy)
def distance_rectangle_border_point(rect: Rect | Rectangle, point: Point) -> float:
"""Return the distance (fast) from a rectangle ``(x, y, width,height)`` to
a ``point``."""
dx = dy = 0.0
px, py = point
rx, ry, rw, rh = rect # typing: ignore[misc]
rx1 = rx + rw
ry1 = ry + rh
if rx < px < rx1 and ry < py < ry1:
return -min(px - rx, rx1 - px, py - ry, ry1 - py)
if px < rx:
dx = rx - px
elif px > rx1:
dx = px - rx1
if py < ry:
dy = ry - py
elif py > ry1:
dy = py - ry1
return abs(dx) + abs(dy)
[docs]
def distance_rectangle_point(rect: Rect | Rectangle, point: Point) -> float:
"""Return the distance (fast) from a rectangle ``(x, y, width,height)`` to
a ``point``."""
return max(0, distance_rectangle_border_point(rect, point))
[docs]
def point_on_rectangle(
rect: Rect | Rectangle, point: Point, border: bool = False
) -> Point:
"""Return the point on which ``point`` can be projecten on the rectangle.
``border = True`` will make sure the point is bound to
the border of the reactangle. Otherwise, if the point is in the
rectangle, it's okay.
"""
px, py = point
rx, ry, rw, rh = rect
x_inside = y_inside = False
if px < rx:
px = rx
elif px > rx + rw:
px = rx + rw
elif border:
x_inside = True
if py < ry:
py = ry
elif py > ry + rh:
py = ry + rh
elif border:
y_inside = True
if x_inside and y_inside:
if min(abs(rx - px), abs(rx + rw - px)) > min(abs(ry - py), abs(ry + rh - py)):
py = ry if py < ry + rh / 2.0 else ry + rh
else:
px = rx if px < rx + rw / 2.0 else rx + rw
return px, py
[docs]
def distance_line_point(
line_start: Point, line_end: Point, point: Point
) -> tuple[float, Point]:
"""Calculate the distance of a ``point`` from a line. The line is marked by
begin and end point ``line_start`` and ``line_end``.
A tuple is returned containing the distance and point on the line.
"""
# The original end point:
true_line_end = line_end
# "Move" the line, so it "starts" on (0, 0)
line_end = line_end[0] - line_start[0], line_end[1] - line_start[1]
point = point[0] - line_start[0], point[1] - line_start[1]
line_len_sqr = line_end[0] * line_end[0] + line_end[1] * line_end[1]
# Both points are very near each other.
if line_len_sqr < 0.0001:
return distance_point_point(point), (line_start[0], line_start[1])
projlen = (line_end[0] * point[0] + line_end[1] * point[1]) / line_len_sqr
if projlen < 0.0:
# Closest point is the start of the line.
return distance_point_point(point), (line_start[0], line_start[1])
elif projlen > 1.0:
# Point has a projection after the line_end.
return distance_point_point(point, line_end), (
true_line_end[0],
true_line_end[1],
)
else:
# Projection is on the line. multiply the line_end with the projlen
# factor to obtain the point on the line.
proj = line_end[0] * projlen, line_end[1] * projlen
return (
distance_point_point((proj[0] - point[0], proj[1] - point[1])),
(line_start[0] + proj[0], line_start[1] + proj[1]),
)
[docs]
def intersect_line_line(
line1_start: Point, line1_end: Point, line2_start: Point, line2_end: Point
) -> Point | None:
"""Find the point where the lines (segments) defined by ``(line1_start,
line1_end)`` and ``(line2_start, line2_end)`` intersect. If no
intersection occurs, ``None`` is returned.
>>> intersect_line_line((3, 0), (8, 10), (0, 0), (10, 10))
(6, 6)
>>> intersect_line_line((0, 0), (10, 10), (3, 0), (8, 10))
(6, 6)
>>> intersect_line_line((0, 0), (10, 10), (8, 10), (3, 0))
(6, 6)
>>> intersect_line_line((8, 10), (3, 0), (0, 0), (10, 10))
(6, 6)
>>> intersect_line_line((0, 0), (0, 10), (3, 0), (8, 10))
>>> intersect_line_line((0, 0), (0, 10), (3, 0), (3, 10))
Ticket #168:
>>> intersect_line_line((478.0, 117.0), (478.0, 166.0), (527.5, 141.5), (336.5, 139.5))
(478.5, 141.48167539267016)
>>> intersect_line_line((527.5, 141.5), (336.5, 139.5), (478.0, 117.0), (478.0, 166.0))
(478.5, 141.48167539267016)
This is a Python translation of the ``lines_intersect``, C Code from
Graphics Gems II, Academic Press, Inc. The original routine was written
by Mukesh Prasad.
EULA: The Graphics Gems code is copyright-protected. In other words, you
cannot claim the text of the code as your own and resell it. Using the code
is permitted in any program, product, or library, non-commercial or
commercial. Giving credit is not required, though is a nice gesture. The
code comes as-is, and if there are any flaws or problems with any Gems
code, nobody involved with Gems - authors, editors, publishers, or
webmasters - are to be held responsible. Basically, don't be a jerk, and
remember that anything free comes with no guarantee.
"""
#
# This function computes whether two line segments,
# respectively joining the input points (x1,y1) -- (x2,y2)
# and the input points (x3,y3) -- (x4,y4) intersect.
# If the lines intersect, the output variables x, y are
# set to coordinates of the point of intersection.
#
# All values are in integers. The returned value is rounded
# to the nearest integer point.
#
# If non-integral grid points are relevant, the function
# can easily be transformed by substituting floating point
# calculations instead of integer calculations.
#
# Entry
# x1, y1, x2, y2 Coordinates of endpoints of one segment.
# x3, y3, x4, y4 Coordinates of endpoints of other segment.
#
# Exit
# x, y Coordinates of intersection point.
#
# The value returned by the function is one of:
#
# DONT_INTERSECT 0
# DO_INTERSECT 1
# COLLINEAR 2
#
# Error conditions:
#
# Depending upon the possible ranges, and particularly on 16-bit
# computers, care should be taken to protect from overflow.
#
# In the following code, 'long' values have been used for this
# purpose, instead of 'int'.
#
x1, y1 = line1_start
x2, y2 = line1_end
x3, y3 = line2_start
x4, y4 = line2_end
# long a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
# long r1, r2, r3, r4; /* 'Sign' values */
# long denom, offset, num; /* Intermediate values */
# Compute a1, b1, c1, where line joining points 1 and 2
# is "a1 x + b1 y + c1 = 0".
a1 = y2 - y1
b1 = x1 - x2
c1 = x2 * y1 - x1 * y2
# Compute r3 and r4.
r3 = a1 * x3 + b1 * y3 + c1
r4 = a1 * x4 + b1 * y4 + c1
# Check signs of r3 and r4. If both point 3 and point 4 lie on
# same side of line 1, the line segments do not intersect.
if r3 and r4 and (r3 * r4) >= 0:
return None # ( DONT_INTERSECT )
# Compute a2, b2, c2
a2 = y4 - y3
b2 = x3 - x4
c2 = x4 * y3 - x3 * y4
# Compute r1 and r2
r1 = a2 * x1 + b2 * y1 + c2
r2 = a2 * x2 + b2 * y2 + c2
# Check signs of r1 and r2. If both point 1 and point 2 lie
# on same side of second line segment, the line segments do
# not intersect.
if r1 and r2 and (r1 * r2) >= 0: # SAME_SIGNS( r1, r2 ))
return None # ( DONT_INTERSECT )
# Line segments intersect: compute intersection point.
# The denom / 2 is to get rounding instead of truncating. It
# is added or subtracted to the numerator, depending upon the
# sign of the numerator.
denom = a1 * b2 - a2 * b1
x_num = b1 * c2 - b2 * c1
y_num = a2 * c1 - a1 * c2
if not denom:
return None # ( COLLINEAR )
offset = abs(denom) / 2
x = ((x_num - offset) if (x_num < 0) else (x_num + offset)) / denom
y = ((y_num - offset) if (y_num < 0) else (y_num + offset)) / denom
return x, y
[docs]
def rectangle_contains(inner: Rect, outer: Rect) -> bool:
"""Returns True if ``inner`` rect is contained in ``outer`` rect."""
ix, iy, iw, ih = inner
ox, oy, ow, oh = outer
return ox <= ix and oy <= iy and ox + ow >= ix + iw and oy + oh >= iy + ih
[docs]
def rectangle_intersects(recta: Rect, rectb: Rect) -> bool:
"""Return True if ``recta`` and ``rectb`` intersect.
>>> rectangle_intersects((5,5,20, 20), (10, 10, 1, 1))
True
>>> rectangle_intersects((40, 30, 10, 1), (1, 1, 1, 1))
False
"""
ax, ay, aw, ah = recta
bx, by, bw, bh = rectb
return ax <= bx + bw and ax + aw >= bx and ay <= by + bh and ay + ah >= by
[docs]
def rectangle_clip(recta: Rect, rectb: Rect) -> Rect | None:
"""Return the clipped rectangle of ``recta`` and ``rectb``. If they do not
intersect, ``None`` is returned.
>>> rectangle_clip((0, 0, 20, 20), (10, 10, 20, 20))
(10, 10, 10, 10)
"""
ax, ay, aw, ah = recta
bx, by, bw, bh = rectb
x = max(ax, bx)
y = max(ay, by)
w = min(ax + aw, bx + bw) - x
h = min(ay + ah, by + bh) - y
return None if w < 0 or h < 0 else (x, y, w, h)