Geometry

Some geometrical shapes and operations

Quick Start Guide

# import the required shapes and structures
from pygorithm.geometry import polygon2
from pygorithm.geometry import vector2

# create a regular polygon
poly1 = polygon2.Polygon2.from_regular(5, 5)

# create a polygon from tuple (x, y) - note that the polygon must be convex
# and the points must be clockwise
poly2 = polygon2.Polygon2(points=[ (0, 0), (1, 0), (1, 1), (0, 1) ])

# create a polygon from vector2s.
poly3 = polygon2.Polygon2(points=[ vector2.Vector2(0, 0),
                                 vector2.Vector2(1, 1),
                                 vector2.Vector2(2, 0) ])

# create a polygon by rotating another polygon
poly4 = poly3.rotate(0.2)
poly5 = poly3.rotate(degrees = 30)


# check intersection
intrs, mtv = polygon2.Polygon2.find_intersection(poly1, poly2, (0, 0), (1, 0))

if intrs:
    mtv_dist = mtv[0]
    mtv_vec = mtv[1]
    print('They intersect. The best way to push poly1 is {} units along {}'.format(mtv_dist, mtv_vec))
else:
    print('No intersection')

Features

  • Structures available:
    • Vector2 (vector2)
    • Line2 (line2)
    • AxisAlignedLine (axisall)
  • Shapes available:
    • Concave Polygons (polygon2)
    • Rectangles (rect2)
  • Algorithms available:
    • Separating Axis Theorem (polygon2)
    • Broad-phase (rect2)
    • Extrapolated intersection (extrapolated_intersection)

Vector2

class pygorithm.geometry.vector2.Vector2(*args, **kwargs)[source]

Define a simple two-dimensional, mutable vector.

Important

Equality is not overriden on vectors, because it is expected that vectors will be used mutably by directly modifying x and y. However, all functions on vectors are immutable (they return a copy)

Variables:
  • x (numbers.Number) – The first component of this vector.
  • y (numbers.Number) – The second component of this vector.
__init__(*args, **kwargs)[source]

Create a new Vector2 from the two components.

Accepts a pair of unnamed parameters, a pair of named x, y parameters, another Vector2, or a tuple with 2 numerics. Examples of each:

from pygorithm.geometry import vector2

# A pair of unnamed parameters
vec1 = vector2.Vector2(0, 5)

# A pair of named parameters
vec2 = vector2.Vector2(x = 0, y = 5)

# Another vector2
vec3 = vector2.Vector2(vec2)

# A tuple with two numerics
vec4 = vector2.Vector2( (0, 5) )
Parameters:
  • args – unnamed arguments (purpose guessed by order)
  • kwargs – named arguments (purpose known by name)
__add__(other)[source]

Adds the two vectors component wise.

Example:

from pygorithm.geometry import vector2

vec1 = vector2.Vector2(0, 3)
vec2 = vector2.Vector2(2, 4)

vec3 = vec1 + vec2

# prints <2, 7>
print(vec3)
Parameters:other (pygorithm.geometry.vector2.Vector2) – the vector to add to this one
Returns:a new vector that is the sum of self and other
Return type:pygorithm.geometry.vector2.Vector2
__sub__(other)[source]

Subtract the two vectors component wise.

Example:

from pygorithm.geometry import vector2

vec1 = vector2.Vector2(5, 5)
vec2 = vector2.Vector2(2, 3)

vec3 = vec1 - vec2
vec4 = vec2 - vec1

# prints <3, 2>
print(vec3)

# prints <2, 3>
print(vec4)
Parameters:other (pygorithm.geometry.vector2.Vector2) – the vector to subtract from this one
Returns:a new vector two that is the difference of self and other
Return type:pygorithm.geometry.vector2.Vector2
__mul__(scale_factor)[source]

Scale the vector by the specified factor.

Caution

This will never perform a dot product. If scale_factor is a Vector2, an exception is thrown.

Example:

from pygorithm.geometry import vector2

vec1 = vector2.Vector2(4, 8)

vec2 = vec1 * 0.5

# prints <2, 4>
print(vec2)
Param:scale_factor the amount to scale this vector by
Returns:a new vector that is self scaled by scale_factor
Return type:pygorithm.geometry.vector2.Vector2
Raises:TypeError – if scale_factor is a Vector2
__rmul__(scale_factor)[source]

Scale the vector by the specified factor.

Caution

This will never perform a dot product. If scale_factor is a Vector2, an exception is thrown.

Example:

from pygorithm.geometry import vector2

vec1 = vector2.Vector2(4, 8)

vec2 = 2 * vec1

# prints <8, 16>
print(vec2)
Param:scale_factor the amount to scale this vector by
Returns:a new vector that is self scaled by scale_factor
Return type:pygorithm.geometry.vector2.Vector2
Raises:TypeError – if scale_factor is a Vector2
__repr__()[source]

Create an unambiguous representation of this vector

Example:

from pygorithm.geometry import vector2

vec = vector2.Vector2(3, 5)

# prints vector2(x=3, y=5)
print(repr(vec))
Returns:an unambiguous representation of this vector
Return type:string
__str__()[source]

Create a human-readable representation of this vector.

Rounds to 3 decimal places if there are more.

Example:

from pygorithm.geometry import vector2

vec = vector2.Vector2(7, 11)

# prints <7, 11>
print(str(vec))

# also prints <7, 11>
print(vec)
Returns:a human-readable representation of this vector
Return type:string
__weakref__

list of weak references to the object (if defined)

dot(other)[source]

Calculate the dot product between this vector and other.

The dot product of two vectors is calculated as so:

Let v1 be a vector such that v1 = <v1_x, v1_y>
Let v2 be a vector such that v2 = <v2_x, v2_y>

v1 . v2 = v1_x * v2_x + v1_y * v2_y

Example:

from pygorithm.geometry import vector2

vec1 = vector2.Vector2(3, 5)
vec2 = vector2.Vector2(7, 11)

dot_12 = vec1.dot(vec2)

# prints 76
print(dot_12)
Parameters:other (pygorithm.geometry.vector2.Vector2) – the other vector
Returns:the dot product of self and other
Return type:numbers.Number
cross(other)[source]

Calculate the z-component of the cross product between this vector and other.

The cross product of two vectors is calculated as so:

Let v1 be a vector such that v1 = <v1_x, v1_y>
Let v2 be a vector such that v2 = <v2_x, v2_y>

v1 x v2 = v1.x * v2.y - v1.y * v2.x

Caution

This is the special case of a cross product in 2 dimensions returning 1 value. This is really a vector in the z direction!

rotate(*args, **kwargs)[source]

The named argument “degrees” or “radians” may be passed in to rotate this vector by the specified amount in degrees (or radians), respectively. If both are omitted, the first unnamed argument is assumed to be the amount to rotate in radians.

Additionally, the named argument “about” may be passed in to specify about what the vector should be rotated. If omitted then the first unconsumed unnamed argument is assumed to be the vector. If there are no unconsumed unnamed arguments then the origin is assumed.

Examples:

from pygorithm.geometry import vector2
import math

vec1 = vector2.Vector2(1, 0)

vec2 = vec1.rotate(math.pi * 0.25)

# prints <0.707, 0.707>
print(vec2)

vec3 = vec1.rotate(degrees = 45)

# prints <0.707, 0.707>
print(vec3)

# The following operations are all identical

vec4 = vec1.rotate(math.pi, vector2.Vector2(1, 1))
vec5 = vec1.rotate(radians = math.pi, about = vector2.Vector2(1, 1))
vec6 = vec1.rotate(degrees = 180, about = vector2.Vector2(1, 1))
vec7 = vec1.rotate(vector2.Vector2(1, 1), degrees = 180)

# prints <1, 2>
print(vec4)
Parameters:
  • args – the unnamed arguments (purpose guessed by position)
  • kwargs – the named arguments (purpose known by name)
Returns:

the new vector formed by rotating this vector
Return type:

pygorithm.geometry.vector2.Vector2
normalize()[source]

Create the normalized version of this vector

The normalized version will go in the same direction but will have magnitude of 1.

Note

This will never return self, even if this vector is already normalized.

Example:

from pygorithm.geometry import vector2

vec1 = vector2.Vector2(2, 0)

vec2 = vec1.normalize()

# prints <1, 0>
print(vec2)
Returns:a new normalized version of this vector
Return type:pygorithm.geometry.vector2.Vector2
magnitude_squared()[source]

Calculate the square of the magnitude of this vector.

Example:

from pygorithm.geometry import vector2

vec1 = vector2.Vector2(5, 12)
magn_sq = vec1.magnitude_squared()

# prints 169 (13^2)
print(magn_sq)
Returns:square of the magnitude of this vector
Return type:numbers.Number
magnitude()[source]

Calculate the magnitude of this vector

Note

It is substantially faster to operate on magnitude squared where possible.

Example:

from pygorithm.geometry import vector2

vec1 = vector2.Vector2(3, 4)
magn = vec1.magnitude()

# prints 5
print(magn)
Returns:magnitude of this vector
Return type:numbers.Number

Line2

class pygorithm.geometry.line2.Line2(start, end)[source]

Define a two-dimensional directed line segment defined by two points. This class is mostly used as a way to cache information that is regularly required when working on geometrical problems.

Caution

Lines should be used as if they were completely immutable to ensure correctness. All attributes of Line2 can be reconstructed from the two points, and thus cannot be changed on their own and must be recalculated if there were any changes to start or end.

Tip

To prevent unnecessary recalculations, many functions on lines accept an ‘offset’ argument, which is used to perform calculations on lines that are simply shifts of other lines.

Note

The minimum x is guarranteed to be on either (or both) of the start and end. However, minimum x and minimum y might not come from the same point. The same is true for the maximum x and maximum y.

Variables:
__init__(start, end)[source]

Create a new line from start to end.

Parameters:
Raises:

ValueError – if start and end are at the same point
delta

Get the vector from start to end, lazily initialized.

Returns:delta from start to end
Return type:pygorithm.geometry.vector2.Vector2
axis

Get the normalized delta vector, lazily initialized

Returns:normalized delta
Return type:pygorithm.geometry.vector2.Vector2
normal

Get normalized normal vector to axis, lazily initialized.

Get the normalized normal vector such that the normal vector is 90 degrees counter-clockwise from the axis.

Returns:normalized normal to axis
Return type:pygorithm.geometry.vector2.Vector2
magnitude_squared

Get the square of the magnitude of delta, lazily initialized.

Returns:square of magnitude of delta
Return type:numbers.Number
magnitude

Get the magnitude of delta, lazily initialized.

Note

It is substantially faster to operate on squared magnitude, where possible.

Returns:magnitude of delta
Return type:numbers.Number
min_x

Get the minimum x that this line contains, lazily initialized.

Returns:minimum x this line contains
Return type:numbers.Number
min_y

Get the minimum y that this line contains, lazily initialized.

Returns:minimum x this line contains
Return type:numbers.Number
max_x

Get the maximum x that this line contains, lazily initialized.

Returns:maximum x this line contains
Return type:numbers.Number
max_y

Get the maximum y that this line contains, lazily initialized.

Returns:maximum x this line contains
Return type:numbers.Number
slope

Get the slope of this line, lazily initialized.

Caution

The slope may be 0 (horizontal line) or positive or negative infinity (vertical lines). It may be necessary to handle these lines seperately, typically through checking the horizontal and vertical properties.

Returns:the slope of this line (rise over run).
Return type:numbers.Number
y_intercept

Get the y-intercept of this line, lazily initialized.

This does not take into account any offset of the line and may return None if this is a vertical line.

Caution

This function will return a y-intercept for non-vertical line segments that do not reach x=0.

Caution

The y-intercept will change based on the offset in a somewhat complex manner. calculate_y_intercept() accepts an offset parameter.

Returns:the y-intercept of this line when unshifted
Return type:numbers.Number or None
horizontal

Get if this line is horizontal, lazily initialized.

A line is horizontal if it has a slope of 0. This also means that start.y == end.y

Returns:if this line is horizontal
Return type:bool
vertical

Get if this line is vertical, lazily initialized.

A line is vertical if it has a slope of +inf or -inf. This also means that start.x == end.x.

Returns:if this line is vertical
Return type:bool
__repr__()[source]

Get an unambiguous representation of this line

Example:

from pygorithm.geometry import (vector2, line2)

vec1 = vector2.Vector2(1, 1)
vec2 = vector2.Vector2(3, 4)

line = line2.Line2(vec1, vec2)

# prints line2(start=vector2(x=1, y=1), end=vector2(x=3, y=4))
print(repr(line))
Returns:unambiguous representation of this line
Return type:string
__str__()[source]

Get a human-readable representation of this line

Example:

from pygorithm.geometry import (vector2, line2)

vec1 = vector2.Vector2(1, 1)
vec2 = vector2.Vector2(3, 4)

line = line2.Line2(vec1, vec2)

# prints <1, 1> -> <3, 4>
print(str(line))

# same as above
print(line)
Returns:human-readable representation of this line
Return type:string
calculate_y_intercept(offset)[source]

Calculate the y-intercept of this line when it is at the specified offset.

If the offset is None this is exactly equivalent to y_intercept

Parameters:offset (pygorithm.geometry.vector2.Vector2 or None) – the offset of this line for this calculations
Returns:the y-intercept of this line when at offset
Return type:numbers.Number
static are_parallel(line1, line2)[source]

Determine if the two lines are parallel.

Two lines are parallel if they have the same or opposite slopes.

Parameters:
Returns:

if the lines are parallel
Return type:

bool
static contains_point(line, point, offset=None)[source]

Determine if the line contains the specified point.

Optionally, specify an offset for the line. Being on the line is determined using math.isclose.

Parameters:
Returns:

if the point is on the line
Return type:

bool
static find_intersection(line1, line2, offset1=None, offset2=None)[source]

Find the intersection between the two lines.

The lines may optionally be offset by a fixed amount. This will incur a minor performance penalty which is less than that of recreating new lines.

Two lines are considered touching if they only share exactly one point and that point is an edge of one of the lines.

If two lines are parallel, their intersection could be a line.

Tip

This will never return True, True

Parameters:
Returns:

(touching, overlapping, intersection_location)
Return type:

(bool, bool, pygorithm.geometry.line2.Line2 or pygorithm.geometry.vector2.Vector2 or None)
__weakref__

list of weak references to the object (if defined)

Axis-Aligned Line

class pygorithm.geometry.axisall.AxisAlignedLine(axis, point1, point2)[source]

Define an axis aligned line.

This class provides functions related to axis aligned lines as well as acting as a convienent container for them. In this context, an axis aligned line is a two-dimensional line that is defined by an axis and length on that axis, rather than two points. When working with two lines defined as such that have the same axis, many calculations are simplified.

Note

Though it requires the same amount of memory as a simple representation of a 2 dimensional line (4 numerics), it cannot describe all types of lines. All lines that can be defined this way intersect (0, 0).

Note

min and max are referring to nearness to negative and positive infinity, respectively. The absolute value of min may be larger than that of max.

Note

AxisAlignedLines are an intermediary operation, so offsets should be baked into them.

Variables:
  • axis (pygorithm.geometry.vector2.Vector2) – the axis this line is on
  • min (numbers.Number) – the point closest to negative infinity
  • max (numbers.Number) – the point closest to positive infinity
__init__(axis, point1, point2)[source]

Construct an axis aligned line with the appropriate min and max.

Parameters:
  • axis (pygorithm.geometry.vector2.Vector2) – axis this line is on (for bookkeeping only, may be None)
  • point1 (numbers.Number) – one point on this line
  • point2 (numbers.Number) – a different point on this line
static intersects(line1, line2)[source]

Determine if the two lines intersect

Determine if the two lines are touching, if they are overlapping, or if they are disjoint. Lines are touching if they share only one end point, whereas they are overlapping if they share infinitely many points.

Note

It is rarely faster to check intersection before finding intersection if you will need the minimum translation vector, since they do mostly the same operations.

Tip

This will never return True, True

Parameters:
Returns:

(touching, overlapping)
Return type:

(bool, bool)
static find_intersection(line1, line2)[source]

Calculate the MTV between line1 and line2 to move line1

Determine if the two lines are touching and/or overlapping and then returns the minimum translation vector to move line 1 along axis. If the result is negative, it means line 1 should be moved in the opposite direction of the axis by the magnitude of the result.

Returns true, (None, touch_point_numeric, touch_point_numeric) if the lines are touching and not overlapping.

Note

Ensure your program correctly handles true, (None, numeric, numeric)

Parameters:
Returns:

(touching, (mtv against 1, intersection min, intersection max))
Return type:

(bool, (numbers.Number or None, numbers.Number, numbers.Number) or None)
static contains_point(line, point)[source]

Determine if the line contains the specified point.

The point must be defined the same way as min and max.

Tip

It is not possible for both returned booleans to be True.

Parameters:
Returns:

(if the point is an edge of the line, if the point is contained by the line)
Return type:

(bool, bool)
__repr__()[source]

Create an unambiguous representation of this axis aligned line.

Example:

from pygorithm.geometry import axisall

aal = axisall.AxisAlignedLine(None, 3, 5)

# prints AxisAlignedLine(axis=None, min=3, max=5)
print(repr(aal))
Returns:un-ambiguous representation of this line
Return type:string
__str__()[source]

Create a human-readable representation of this axis aligned line.

Example:

from pygorithm.geometry import axisall

aal = axisall.AxisAlignedLine(None, 0.7071234, 0.7071234)

# prints axisall(along None from 0.707 to 0.707)
print(aal)
Returns:human-readable representation of this line
Return type:string
__weakref__

list of weak references to the object (if defined)

Concave Polygon

class pygorithm.geometry.polygon2.Polygon2(points, suppress_errors=False)[source]

Define a concave polygon defined by a list of points such that each adjacent pair of points form a line, the line from the last point to the first point form a line, and the lines formed from the smaller index to the larger index will walk clockwise around the polygon.

Note

Polygons should be used as if they were completely immutable to ensure correctness. All attributes of Polygon2 can be reconstructed from the points array, and thus cannot be changed on their own and must be recalculated if there were any changes to points.

Note

To reduce unnecessary recalculations, Polygons notably do not have an easily modifiable position. However, where relevant, the class methods will accept offsets to the polygons. In all of these cases the offset may be None for a minor performance improvement.

Note

Unfortunately, operations on rotated polygons require recalculating the polygon based on its rotated points. This should be avoided unless necessary through the use of Axis-Aligned Bounding Boxes and similar tools.

Caution

The length of normals is not necessarily the same as points or lines. It is only guarranteed to have no two vectors that are the same or opposite directions, and contain either the vector in the same direction or opposite direction of the normal vector for every line in the polygon.

Variables:
__init__(points, suppress_errors=False)[source]

Create a new polygon from the set of points

Caution

A significant amount of calculation is performed when creating a polygon. These should be reused whenever possible. This cost can be alleviated somewhat by suppressing certain expensive sanity checks, but the polygon can behave very unexpectedly (and potentially without explicit errors) if the errors are suppressed.

The center of the polygon is calculated as the average of the points.

The lines of the polygon are constructed using line2.

The normals of the lines are calculated using line2.

A simple linear search is done to check for repeated points.

The area is calculated to check for clockwise order using the Shoelace Formula <https://en.wikipedia.org/wiki/Shoelace_formula>

The polygon is proven to be convex by ensuring the cross product of the line from the point to previous point and point to next point is positive or 0, for all points.

Parameters:
  • points (list of pygorithm.geometry.vector2.Vector2 or list of (numbers.Number, numbers.Number)) – the ordered set of points on this polygon
  • suppress_errors (bool) – True to not do somewhat expensive sanity checks
Raises:
  • ValueError – if there are less than 3 points (not suppressable)
  • ValueError – if there are any repeated points (suppressable)
  • ValueError – if the points are not clockwise oriented (suppressable)
  • ValueError – if the polygon is not convex (suppressable)
classmethod from_regular(sides, length, start_rads=None, start_degs=None, center=None)[source]

Create a new regular polygon.

Hint

If no rotation is specified there is always a point at (length, 0)

If no center is specified, the center will be calculated such that all the vertexes positive and the bounding box includes (0, 0). This operation requires O(n) time (where n is the number if sides)

May specify the angle of the first point. For example, if the coordinate system is x to the right and y upward, then if the starting offset is 0 then the first point will be at the right and the next point counter-clockwise.

This would make for the regular quad (sides=4) to look like a diamond. To make the bottom side a square, the whole polygon needs to be rotated 45 degrees, like so:

from pygorithm.geometry import (vector2, polygon2)
import math

# This is a diamond shape (rotated square) (0 degree rotation assumed)
diamond = polygon2.Polygon2.from_regular(4, 1)

# This is a flat square
square = polygon2.Polygon2.from_regular(4, 1, start_degs = 45)

# Creating a flat square with radians 
square2 = polygon2.Polygon2.from_regular(4, 1, math.pi / 4)

Uses the definition of a regular polygon <https://en.wikipedia.org/wiki/Regular_polygon> to find the angle between each vertex in the polygon. Then converts the side length to circumradius using the formula explained here <http://mathworld.wolfram.com/RegularPolygon.html>

Finally, each vertex is found using <radius * cos(angle), radius * sin(angle)>

If the center is not specified, the minimum of the bounding box of the polygon is calculated while the vertices are being found, and the inverse of that value is offset to the rest of the points in the polygon.

Parameters:
  • sides (numbers.Number) – the number of sides in the polygon
  • length (numbers.Number) – the length of any side of the polygon
  • start_rads (numbers.Number or None) – the starting radians or None
  • start_degs (numbers.Number or None) – the starting degrees or None
  • center (pygorithm.geometry.vector2.Vector2) – the center of the polygon
Returns:

the new regular polygon
Return type:

pygorithm.geometry.polygon2.Polygon2
Raises:
  • ValueError – if sides < 3 or length <= 0
  • ValueError – if start_rads is not None and start_degs is not None
classmethod from_rotated(original, rotation, rotation_degrees=None)[source]

Create a regular polygon that is a rotation of a different polygon.

The rotation must be in radians, or null and rotation_degrees must be specified. Positive rotations are clockwise.

Examples:

from pygorithm.goemetry import (vector2, polygon2)
import math

poly = polygon2.Polygon2.from_regular(4, 1)

# the following are equivalent (within rounding)
rotated1 = polygon2.Polygon2.from_rotated(poly, math.pi / 4)
rotated2 = polygon2.Polygon2.from_rotated(poly, None, 45)

Uses the 2-d rotation matrix <https://en.wikipedia.org/wiki/Rotation_matrix> to rotate each point.

Parameters:
  • original (pygorithm.geometry.polygon2.Polygon2) – the polygon to rotate
  • rotation (numbers.Number) – the rotation in radians or None
  • rotation_degrees (numbers.Number) – the rotation in degrees or None
Returns:

the rotated polygon
Return type:

pygorithm.geometry.polygon2.Polygon2
Raises:
  • ValueError – if rotation is not None and rotation_degrees is not None
  • ValueError – if rotation is None and rotation_degrees is None
area

Get the area of this polygon. Lazily initialized.

Uses the Shoelace Formula <https://en.wikipedia.org/wiki/Shoelace_formula> to calculate the signed area, allowing this to also test for correct polygon orientation.

Returns:area of this polygon
Return type:numbers.Number
Raises:ValueError – if the polygon is not in clockwise order
static project_onto_axis(polygon, offset, axis)[source]

Find the projection of the polygon along the axis.

Uses the dot product <https://en.wikipedia.org/wiki/Dot_product> of each point on the polygon to project those points onto the axis, and then finds the extremes of the projection.

Parameters:
Returns:

the projection of the polygon along the axis
Return type:

pygorithm.geometry.axisall.AxisAlignedLine
static contains_point(polygon, offset, point)[source]

Determine if the polygon at offset contains point.

Distinguish between points that are on the edge of the polygon and points that are completely contained by the polygon.

Tip

This can never return True, True

This finds the cross product of this point and the two points comprising every line on this polygon. If any are 0, this is an edge. Otherwise, they must all be negative (when traversed clockwise).

Parameters:
Returns:

on edge, contained
Return type:

bool, bool
static find_intersection(poly1, poly2, offset1, offset2, find_mtv=True)[source]

Find if the polygons are intersecting and how to resolve it.

Distinguish between polygons that are sharing 1 point or a single line (touching) as opposed to polygons that are sharing a 2-dimensional amount of space.

The resulting MTV should be applied to the first polygon (or its offset), or its negation can be applied to the second polygon (or its offset).

The MTV will be non-null if overlapping is True and find_mtv is True.

Note

There is only a minor performance improvement from setting find_mtv to False. It is rarely an improvement to first check without finding mtv and then to find the mtv.

Caution

The first value in the mtv could be negative (used to inverse the direction of the axis)

This uses the `Seperating Axis Theorem <http://www.dyn4j.org/2010/01/sat/> to calculate intersection.

Parameters:
Returns:

(touching, overlapping, (mtv distance, mtv axis))
Return type:

(bool, bool, (numbers.Number, pygorithm.geometry.vector2.Vector2) or None)
__repr__()[source]

Creates an unambiguous representation of this polygon, only showing the list of points.

Returns:unambiguous representation of this polygon
Return type:string
__str__()[source]

Creates a human-readable representation of this polygon and includes a link to visualize it

Returns:human-readable representation
Return type:string
__weakref__

list of weak references to the object (if defined)

Axis-Aligned Rectangle

class pygorithm.geometry.rect2.Rect2(width, height, mincorner=None)[source]

A rectangle. Uses SAT collision against polygons and broad-phase collision against other rectangles.

Rectangles are fast to construct and have very fast rectangle-rectangle collision detection.

Rect2 is designed to have almost exactly the opposite performance characteristics as Polygon2 when doing collision against Polygon2s: Fast to construct and complex on first call with many operations incurring expensive recalculations.

Caution

Collision detection against a polygon with cause initialization of the polygon representation of a rectangle. This has the noticeable performance characteristics that are seen whenever a polygon is constructed (see Polygon2). This operation recurrs only if width and height were modified.

Variables:mincorner (pygorithm.geometry.vector2.Vector2) – the position of this polygon
__init__(width, height, mincorner=None)[source]

Create a new rectangle of width and height.

If mincorner is None, the origin is assumed.

Parameters:
  • width (numbers.Number) – width of this rect
  • height (numbers.Number) – height of this rect
  • mincorner (pygorithm.geometry.vector2.Vector2 or None) – the position of this rect
Raises:

ValueError – if width or height are not strictly positive
polygon

Get the polygon representation of this rectangle, without the offset. Lazily initialized and up-to-date with width and height.

Caution

This does not include the mincorner (which should be passed as offset for polygon operations)

Returns:polygon representation of this rectangle
Return type:pygorithm.geometry.polygon2.Polygon2
width

Get or set the width of this rect.

Caution

Setting the width of the rectangle will remove the polygon caching required for rectangle-polygon collision.

Returns:width of this rect
Return type:numbers.Number
Raises:ValueError – if trying to set width <= 1e-07
height

Get or set the height of this rect

Caution

Setting the height of the rectangle will remove the cached operations required for rectangle-polygon collision.

Returns:height of this rect
Return type:numbers.Number
Raises:ValueError – if trying to set height <= 1e-07
area

Get the area of this rect

Returns:area of this rect
Return type:numbers.Number
static project_onto_axis(rect, axis)[source]

Project the rect onto the specified axis.

Tip

This function is extremely fast for vertical or horizontal axises.

Parameters:
Returns:

the projection of the rect along axis
Return type:

pygorithm.geometry.axisall.AxisAlignedLine
static contains_point(rect, point)[source]

Determine if the rect contains the point

Distinguish between points that are on the edge of the rect and those that are not.

Tip

This will never return True, True

Parameters:
Returns:

point on edge, point inside
Return type:

bool, bool
classmethod _find_intersection_rects(rect1, rect2, find_mtv=True)[source]

Find the intersection between two rectangles.

Not intended for direct use. See find_intersection()

Parameters:
Returns:

(touching, overlapping, (mtv distance, mtv axis))
Return type:

(bool, bool, (numbers.Number, pygorithm.geometry.vector2.Vector2) or None)
classmethod _find_intersection_rect_poly(rect, poly, offset, find_mtv=True)[source]

Find the intersection between a rect and polygon.

Not intended for direct use. See find_intersection()

Parameters:
Returns:

(touching, overlapping, (mtv distance, mtv axis))
Return type:

(bool, bool, (numbers.Number, pygorithm.geometry.vector2.Vector2) or None)
__weakref__

list of weak references to the object (if defined)

classmethod _find_intersection_poly_rect(poly, offset, rect, find_mtv=True)[source]

Find the intersection between a polygon and rect.

Not intended for direct use. See find_intersection()

Parameters:
Returns:

(touching, overlapping, (mtv distance, mtv axis))
Return type:

(bool, bool, (numbers.Number, pygorithm.geometry.vector2.Vector2) or None)
classmethod find_intersection(*args, **kwargs)[source]

Determine the state of intersection between a rect and a polygon.

For Rect-Polygon intersection:

Must be passed in 3 arguments - a Rect2, a Polygon2, and a Vector2. The vector must come immediately after the polygon, but the rect can be either the first or last unnamed argument. If it is the first argument, the mtv is against the rectangle. If it is the last argument, the mtv is against the polygon.

For Rect-Rect intersection:

Must be passed in 2 arguments (both rects).

Note

The first argument is checked with isinstance(arg, Rect2). If this is False, the first argument is assumed to be a Polygon2. If you want to use a compatible rectangle class for which this check would fail, you can call _find_intersection_rect_poly() directly or pass the polygon first and invert the resulting mtv (if one is found). If two unnamed arguments are provided, they are assumed to be both rects without further checks.

Examples:

from pygorithm.geometry import (vector2, polygon2, rect2)

octogon = polygon2.Polygon2.from_regular(8, 1)
oct_offset = vector2.Vector2(0.5, 0)

unit_square = rect2.Rect2(1, 1)

# find mtv for square against octogon
touching, overlapping, mtv = rect2.Rect2.find_intersection(unit_square, octogon, oct_offset)

# find mtv for octogon against square
touching, overlapping, mtv = rect2.Rect2.find_intersection(octogon, oct_offset, unit_square)

# find intersection but skip mtv (two options)
touching, overlapping, alwaysNone = rect2.Rect2.find_intersection(unit_square, octogon, oct_offset, find_mtv=False)
touching, overlapping, alwaysNone = rect2.Rect2.find_intersection(octogon, oct_offset, unit_square, find_mtv=False)

big_square = rect2.Rect2(2, 2, vector2.Vector2(-1.5, 0))

# find mtv for square against big square
touching, overlapping, mtv = rect2.Rect2.find_intersection(unit_square, big_square)

# find mtv for big square against square 
touching, overlapping, mtv = rect2.Rect2.find_intersection(big_square, unit_square)
Parameters:
  • find_mtv (bool) – if mtv should be found where possible (default True)
  • args (list) – 2 arguments for rect-rect, 3 arguments for rect-polygon (see above)
Returns:

(touching, overlapping, (mtv distance, mtv axis))
Return type:

(bool, bool, (numbers.Number, pygorithm.geometry.vector2.Vector2) or None)
__repr__()[source]

Create an unambiguous representation of this rectangle.

Example:

from pygorithm.geometry import (vector2, rect2)

unit_square = rect2.Rect2(1, 1, vector2.Vector2(3, 4))

# prints rect2(width=1, height=1, mincorner=vector2(x=3, y=4))
print(repr(unit_square))
Returns:unambiguous representation of this rectangle
Return type:string
__str__()[source]

Create a human readable representation of this rectangle

Example:

from pygorithm.geometry import (vector2, rect2)

unit_square = rect2.Rect2(1, 1, vector2.Vector2(3, 4))
ugly_rect = rect2.Rect2(0.7071234, 0.7079876, vector2.Vector2(0.56789123, 0.876543))

# prints rect(1x1 at <3, 4>)
print(str(unit_square))

# prints rect(0.707x0.708 at <0.568, 0.877>)
print(str(ugly_rect))
Returns:human-readable representation of this rectangle
Return type:string

Extrapolated Intersection

Author: Timothy Moore Created On: 4th September 2017

Contains various approaches to determining if a polygon will intersect another polygon as one or both polygons go along a a single direction at a constant speed.

This problem could be thought of as one of extrapolation - given these initial conditions, extrapolate to determine if intersections will occur.

Note

Touching is not considered intersecting in this module, unless otherwise stated. Touching is determined using math.isclose

pygorithm.geometry.extrapolated_intersection.calculate_one_moving_point_and_one_stationary_line(point, velocity, line, offset)[source]

Determine if the point moving at velocity will intersect the line.

The line is positioned at offset. Given a moving point and line segment, determine if the point will ever intersect the line segment.

Caution

Points touching at the start are considered to be intersection. This is because there is no way to get the “direction” of a stationary point like you can a line or polygon.

Parameters:
Returns:

if the point will intersect the line, distance until intersection
Return type:

bool, numbers.Number or None
pygorithm.geometry.extrapolated_intersection.calculate_one_moving_line_and_one_stationary_line(line1, offset1, velocity1, _line2, offset2)[source]

Determine if the moving line will intersect the stationary line.

Given two line segments, one moving and one not, determine if they will ever intersect.

Parameters:
Returns:

if the lines will ever intersect, distance until intersection
Return type:

bool, numbers.Number or None
pygorithm.geometry.extrapolated_intersection.calculate_one_moving_and_one_stationary(poly1, poly1_offset, poly1_velocity, poly2, poly2_offset)[source]

Determine if the moving polygon will intersect the stationary polygon.

This is the simplest question. Given two polygons, one moving and one not, determine if the two polygons will ever intersect (assuming they maintain constant velocity).

Parameters:
Returns:

if they will intersect
Return type:

bool
pygorithm.geometry.extrapolated_intersection.calculate_one_moving_one_stationary_distancelimit(poly1, poly1_offset, poly1_velocity, poly2, poly2_offset, max_distance)[source]

Determine if the moving polygon will intersect the stationary polygon within some distance.

This is a step up, and very similar to the actual problem many any-angle pathfinding algorithms run into. Given two polygons, 1 moving and 1 stationary, determine if the first polygon will intersect the second polygon before moving a specified total distance.

Parameters:
Returns:

if they will intersect
Return type:

bool
pygorithm.geometry.extrapolated_intersection.calculate_one_moving_one_stationary_along_path(poly1, poly1_start, poly1_end, poly2, poly2_offset)[source]

Determine if the moving polygon will intersect the stationary polygon as it moves from the start to the end.

This is a rewording of calculate_one_moving_one_stationary_distancelimit() that is more common. Given two polygons, 1 moving and 1 stationary, where the moving polygon is going at some speed from one point to another, determine if the two polygons will intersect.

Parameters:
Returns:

if they will intersect
Return type:

bool
pygorithm.geometry.extrapolated_intersection.calculate_one_moving_many_stationary(poly1, poly1_offset, poly1_velocity, other_poly_offset_tuples)[source]

Determine if the moving polygon will intersect anything as it moves at a constant direction and speed forever.

This is the simplest arrangement of this problem with a collection of stationary polygons. Given many polygons of which 1 is moving, determine if the moving polygon intersects the other polygons now or at some point in the future if it moves at some constant direction and speed forever.

This does not verify the stationary polygons are not intersecting.

Parameters:
Returns:

if an intersection will occur
Return type:

bool
pygorithm.geometry.extrapolated_intersection.calculate_one_moving_many_stationary_distancelimit(poly1, poly1_offset, poly1_velocity, max_distance, other_poly_offset_tuples)[source]

Determine if the moving polygon will intersect anyything as it moves in a constant direction and speed for a certain distance.

This does not verify the stationary polygons are not intersecting.

Parameters:
Returns:

if an intersection will occur
Return type:

bool
pygorithm.geometry.extrapolated_intersection.calculate_one_moving_many_stationary_along_path(poly1, poly1_start, poly1_end, other_poly_offset_tuples)[source]

Determine if a polygon that moves from one point to another will intersect anything.

This is the question that the Theta* family of pathfinding algorithms require. It is simply a rewording of calculate_one_moving_many_stationary_distancelimit()

This does not verify the stationary polygons are not intersecting.

Parameters:
Returns:

if an intersection will occur
Return type:

bool
pygorithm.geometry.extrapolated_intersection.calculate_two_moving(poly1, poly1_offset, poly1_vel, poly2, poly2_offset, poly2_vel)[source]

Determine if two moving polygons will intersect at some point.

This is the simplest question when there are multiple moving polygons. Given two polygons moving at a constant velocity and direction forever, determine if an intersection will occur.

It should be possible for the reader to extrapolate from this function and the process for stationary polygons to create similar functions to above where all or some polygons are moving.

Parameters:
Returns:

if an intersectino will occur
Return type:

bool