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)
 Broadphase (rect2)
 Extrapolated intersection (extrapolated_intersection)
Vector2¶

class
pygorithm.geometry.vector2.
Vector2
(*args, **kwargs)[source]¶ Define a simple twodimensional, 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 oneReturns: 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 oneReturns: 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 humanreadable 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 humanreadable 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 vectorReturns: the dot product of self and other Return type: numbers.Number

cross
(other)[source]¶ Calculate the zcomponent 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:

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
 x (
Line2¶

class
pygorithm.geometry.line2.
Line2
(start, end)[source]¶ Define a twodimensional 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:  start (
pygorithm.geometry.vector2.Vector2
) – the start of this line  end (
pygorithm.geometry.vector2.Vector2
) – the end of this line

__init__
(start, end)[source]¶ Create a new line from start to end.
Parameters:  start (
pygorithm.geometry.vector2.Vector2
) – the start point  end (
pygorithm.geometry.vector2.Vector2
) – the end point
Raises: ValueError – if start and end are at the same point
 start (

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 counterclockwise 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
andvertical
properties.Returns: the slope of this line (rise over run). Return type: numbers.Number

y_intercept
¶ Get the yintercept 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 yintercept for nonvertical line segments that do not reach
x=0
.Caution
The yintercept will change based on the offset in a somewhat complex manner.
calculate_y_intercept()
accepts an offset parameter.Returns: the yintercept 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 humanreadable 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: humanreadable representation of this line Return type: string

calculate_y_intercept
(offset)[source]¶ Calculate the yintercept 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 calculationsReturns: the yintercept 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:  line1 (
pygorithm.geometry.line2.Line2
) – the first line  line2 (
pygorithm.geometry.line2.Line2
) – the second line
Returns: if the lines are parallel
Return type: bool
 line1 (

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:  line (
pygorithm.geometry.line2.Line2
) – the line  point (
pygorithm.geometry.vector2.Vector2
) – the point  offset (
pygorithm.geometry.vector2.Vector2
or None) – the offset of the line or None for the origin
Returns: if the point is on the line
Return type: bool
 line (

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:  line1 (
pygorithm.geometry.line2.Line2
) – the first line  line2 (
pygorithm.geometry.line2.Line2
) – the second line  offset1 (
pygorithm.geometry.vector2.Vector2
or None) – the offset of line 1  offset2 (
pygorithm.geometry.vector2.Vector2
or None) – the offset of line 2
Returns: (touching, overlapping, intersection_location)
Return type: (bool, bool,
pygorithm.geometry.line2.Line2
orpygorithm.geometry.vector2.Vector2
or None) line1 (

__weakref__
¶ list of weak references to the object (if defined)
 start (
AxisAligned 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 twodimensional 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
 axis (

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:  line1 (
pygorithm.geometry.axisall.AxisAlignedLine
) – the first line  line2 (
pygorithm.geometry.axisall.AxisAlignedLine
) – the second line
Returns: (touching, overlapping)
Return type: (bool, bool)
 line1 (

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:  line1 (
pygorithm.geometry.axisall.AxisAlignedLine
) – the first line  line2 (
pygorithm.geometry.axisall.AxisAlignedLine
) – the second line
Returns: (touching, (mtv against 1, intersection min, intersection max))
Return type: (bool, (
numbers.Number
or None,numbers.Number
,numbers.Number
) or None) line1 (

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:  line (
pygorithm.geometry.axisall.AxisAlignedLine
) – the line  point (
numbers.Number
) – the point
Returns: (if the point is an edge of the line, if the point is contained by the line)
Return type: (bool, bool)
 line (

__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: unambiguous representation of this line Return type: string

__str__
()[source]¶ Create a humanreadable 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: humanreadable representation of this line Return type: string

__weakref__
¶ list of weak references to the object (if defined)
 axis (
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 AxisAligned Bounding Boxes and similar tools.
Caution
The length of
normals
is not necessarily the same aspoints
orlines
. 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:  points (list of
pygorithm.geometry.vector2.Vector2
) – the ordered list of points on this polygon  lines (list of
pygorithm.geometry.line2.Line2
) – the ordered list of lines on this polygon  normals (list of
pygorithm.geometry.vector2.Vector2
) – the unordered list of unique normals on this polygon  center (
pygorithm.geometry.vector2.Vector2
) – the center of this polygon when unshifted.

__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)
 points (list of

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 counterclockwise.
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: Raises:  ValueError – if
sides < 3
orlength <= 0
 ValueError – if
start_rads is not None and start_degs is not None
 sides (

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 2d 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: Raises:  ValueError – if
rotation is not None and rotation_degrees is not None
 ValueError – if
rotation is None and rotation_degrees is None
 original (

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:  polygon (
pygorithm.geometry.polygon2.Polygon2
) – the polygon to project  offset (
pygorithm.geometry.vector2.Vector2
) – the offset of the polygon  axis (
pygorithm.geometry.vector2.Vector2
) – the axis to project onto
Returns: the projection of the polygon along the axis
Return type:  polygon (

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:  polygon (
pygorithm.geometry.polygon2.Polygon2
) – the polygon  offset (
pygorithm.geometry.vector2.Vector2
or None) – the offset of the polygon  point (
pygorithm.geometry.vector2.Vector2
) – the point to check
Returns: on edge, contained
Return type: bool, bool
 polygon (

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 2dimensional 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 nonnull 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:  poly1 (
pygorithm.geometry.polygon2.Polygon2
) – the first polygon  poly2 (
pygorithm.geometry.polygon2.Polygon2
) – the second polygon  offset1 (
pygorithm.geometry.vector2.Vector2
or None) – the offset of the first polygon  offset2 (
pygorithm.geometry.vector2.Vector2
or None) – the offset of the second polygon  find_mtv (bool) – if False, the mtv is always None and there is a small performance improvement
Returns: (touching, overlapping, (mtv distance, mtv axis))
Return type: (bool, bool, (
numbers.Number
,pygorithm.geometry.vector2.Vector2
) or None) poly1 (

__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 humanreadable representation of this polygon and includes a link to visualize it
Returns: humanreadable representation Return type: string

__weakref__
¶ list of weak references to the object (if defined)
 points (list of
AxisAligned Rectangle¶

class
pygorithm.geometry.rect2.
Rect2
(width, height, mincorner=None)[source]¶ A rectangle. Uses SAT collision against polygons and broadphase collision against other rectangles.
Rectangles are fast to construct and have very fast rectanglerectangle 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
 width (

polygon
¶ Get the polygon representation of this rectangle, without the offset. Lazily initialized and uptodate 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 rectanglepolygon collision.
Returns: width of this rect Return type: numbers.Number
Raises: ValueError – if trying to set width <= 1e07

height
¶ Get or set the height of this rect
Caution
Setting the height of the rectangle will remove the cached operations required for rectanglepolygon collision.
Returns: height of this rect Return type: numbers.Number
Raises: ValueError – if trying to set height <= 1e07

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:  rect (
pygorithm.geometry.rect2.Rect2
) – the rect to project  axis (
pygorithm.geometry.vector2.Vector2
) – the axis to project onto (normalized)
Returns: the projection of the rect along axis
Return type:  rect (

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:  rect (
pygorithm.geometry.rect2.Rect2
) – the rect  point (
pygorithm.geometry.vector2.Vector2
) – the point
Returns: point on edge, point inside
Return type: bool, bool
 rect (

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:  rect1 (
pygorithm.geometry.rect2.Rect2
) – first rectangle  rect2 (
pygorithm.geometry.rect2.Rect2
) – second rectangle  find_mtv (bool) – False to never find mtv (may allow small performance improvement)
Returns: (touching, overlapping, (mtv distance, mtv axis))
Return type: (bool, bool, (
numbers.Number
,pygorithm.geometry.vector2.Vector2
) or None) rect1 (

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:  rect (
pygorithm.geometry.rect2.Rect2
) – rectangle  poly (
pygorithm.geometry.polygon2.Polygon2
) – polygon  offset (
pygorithm.geometry.vector2.Vector2
) – offset for the polygon  find_mtv (bool) – False to never find mtv (may allow small performance improvement)
Returns: (touching, overlapping, (mtv distance, mtv axis))
Return type: (bool, bool, (
numbers.Number
,pygorithm.geometry.vector2.Vector2
) or None) rect (

__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:  poly (
pygorithm.geometry.polygon2.Polygon2
) – polygon  offset (
pygorithm.geometry.vector2.Vector2
) – offset for the polygon  rect (
pygorithm.geometry.rect2.Rect2
) – rectangle  find_mtv (bool) – False to never find mtv (may allow small performance improvement)
Returns: (touching, overlapping, (mtv distance, mtv axis))
Return type: (bool, bool, (
numbers.Number
,pygorithm.geometry.vector2.Vector2
) or None) poly (

classmethod
find_intersection
(*args, **kwargs)[source]¶ Determine the state of intersection between a rect and a polygon.
For RectPolygon intersection:
Must be passed in 3 arguments  a
Rect2
, aPolygon2
, and aVector2
. 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 RectRect 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 rectrect, 3 arguments for rectpolygon (see above)
Returns: (touching, overlapping, (mtv distance, mtv axis))
Return type: (bool, bool, (
numbers.Number
,pygorithm.geometry.vector2.Vector2
) or None) find_mtv (bool) – if mtv should be found where possible (default

__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: humanreadable 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:  point (
pygorithm.geometry.vector2.Vector2
) – the starting location of the point  velocity (
pygorithm.geometry.vector2.Vector2
) – the velocity of the point  line (
pygorithm.geometry.line2.Line2
) – the geometry of the stationary line  offset (
pygorithm.geometry.vector2.Vector2
) – the offset of the line
Returns: if the point will intersect the line, distance until intersection
Return type: bool,
numbers.Number
or None point (

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:  line1 (
pygorithm.geometry.line2.Line2
) – the geometry of the moving line  offset1 (
pygorithm.geometry.vector2.Vector2
) – the starting location of the moving line  velocity1 (
pygorithm.geometry.vector2.Vector2
) – the velocity of the moving line  _line2 (
pygorithm.geometry.line2.Line2
) – the geometry of the second line  offset2 (
pygorithm.geometry.vector2.Vector2
) – the location of the second line
Returns: if the lines will ever intersect, distance until intersection
Return type: bool,
numbers.Number
or None line1 (

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:  poly1 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the polygon that is moving  poly1_offset (
pygorithm.geometry.vector2.Vector2
) – the starting location of the moving polygon  poly1_velocity (
pygorithm.geometry.vector2.Vector2
) – the velocity of the moving polygon  poly2 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the stationary polygon  poly2_offset (
pygorithm.geometry.vector2.Vector2
) – the offset of the stationary polygon
Returns: if they will intersect
Return type: bool
 poly1 (

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 anyangle 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:  poly1 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the polygon that is moving  poly1_offset (
pygorithm.geometry.vector2.Vector2
) – the starting location of the moving polygon  poly1_velocity (
pygorithm.geometry.vector2.Vector2
) – the velocity of the moving polygon  poly2 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the stationary polygon  poly2_offset (
pygorithm.geometry.vector2.Vector2
) – the offset of the stationary polygon  max_distance (
numbers.Number
) – the max distance that poly1 can go
Returns: if they will intersect
Return type: bool
 poly1 (

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:  poly1 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the polygon that is moving  poly1_start (
pygorithm.geometry.vector2.Vector2
) – where the moving polygon begins moving from  poly1_end (
pygorithm.geometry.vector2.Vector2
) – where the moving polygon stops moving  poly2 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the stationary polygon  poly2_offset (
pygorithm.geometry.vector2.Vector2
) – the location of the second polygon
Returns: if they will intersect
Return type: bool
 poly1 (

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:  poly1 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the polygon that is moving  poly1_offset (
pygorithm.geometry.vector2.Vector2
) – the starting location of the moving polygon  poly1_velocity (
pygorithm.geometry.vector2.Vector2
) – the velocity of the moving polygon  other_poly_offset_tuples (list of (
pygorithm.geometry.polygon2.Polygon2
,pygorithm.geometry.vector2.Vector2
)) – list of (polygon, offset) of the stationary polygons
Returns: if an intersection will occur
Return type: bool
 poly1 (

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:  poly1 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the polygon that is moving  poly1_offset (
pygorithm.geometry.vector2.Vector2
) – the starting location of the moving polygon  poly1_velocity (
pygorithm.geometry.vector2.Vector2
) – the velocity of the moving polygon  max_distance (
numbers.Number
) – the max distance the polygon will go  other_poly_offset_tuples (list of (
pygorithm.geometry.polygon2.Polygon2
,pygorithm.geometry.vector2.Vector2
)) – list of (polygon, offset) of the stationary polygons
Returns: if an intersection will occur
Return type: bool
 poly1 (

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:  poly1 (
pygorithm.geometry.polygon2.Polygon2
) – the geometry of the polygon that is moving  poly1_start (
pygorithm.geometry.vector2.Vector2
) – where the polygon begins moving from  poly1_end (
pygorithm.geometry.vector2.Vector2
) – where the polygon stops moving at  other_poly_offset_tuples (list of (
pygorithm.geometry.polygon2.Polygon2
,pygorithm.geometry.vector2.Vector2
)) – list of (polygon, offset) of the stationary polygons
Returns: if an intersection will occur
Return type: bool
 poly1 (

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:  poly1 (
pygorithm.geometry.polygon2.Polygon2
) – the first polygon  poly1_offset (
pygorithm.geometry.vector2.Vector2
) – where the first polygon starts at  poly1_vel (
pygorithm.geometry.vector2.Vector2
) – the velocity of the first polygon  poly2 (
pygorithm.geometry.polygon2.Polygon2
) – the second polygon  poly2_offset (
pygorithm.geometry.vector2.Vector2
) – where the second polygon starts at  poly2_vel (
pygorithm.geometry.vector2.Vector2
) – the velocity of the second polygon
Returns: if an intersectino will occur
Return type: bool
 poly1 (