# 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
mtv_vec = mtv
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)
• 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 a new vector that is the sum of self and other `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 a new vector two that is the difference of self and other `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 a new vector that is self scaled by scale_factor `pygorithm.geometry.vector2.Vector2` 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 a new vector that is self scaled by scale_factor `pygorithm.geometry.vector2.Vector2` 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 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 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 the dot product of self and other `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))
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) the new vector formed by rotating this vector `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 `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 `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 `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: 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 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 `pygorithm.geometry.vector2.Vector2`
`axis`

Get the normalized delta vector, lazily initialized

Returns: normalized delta `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 `pygorithm.geometry.vector2.Vector2`
`magnitude_squared`

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

Returns: square of magnitude of delta `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 `numbers.Number`
`min_x`

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

Returns: minimum x this line contains `numbers.Number`
`min_y`

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

Returns: minimum x this line contains `numbers.Number`
`max_x`

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

Returns: maximum x this line contains `numbers.Number`
`max_y`

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

Returns: maximum x this line contains `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). `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 `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 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 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 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 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 the y-intercept of this line when at offset `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 if the lines are parallel 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: 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 if the point is on the line 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: 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 (touching, overlapping, intersection_location) (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: line1 (`pygorithm.geometry.axisall.AxisAlignedLine`) – the first line line2 (`pygorithm.geometry.axisall.AxisAlignedLine`) – the second line (touching, overlapping) (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: line1 (`pygorithm.geometry.axisall.AxisAlignedLine`) – the first line line2 (`pygorithm.geometry.axisall.AxisAlignedLine`) – the second line (touching, (mtv against 1, intersection min, intersection max)) (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: line (`pygorithm.geometry.axisall.AxisAlignedLine`) – the line point (`numbers.Number`) – the point (if the point is an edge of the line, if the point is contained by the line) (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 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 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: 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 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 the new regular polygon `pygorithm.geometry.polygon2.Polygon2` 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 the rotated polygon `pygorithm.geometry.polygon2.Polygon2` 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 `numbers.Number` 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 the projection of the polygon along the axis `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: 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 on edge, contained 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: 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 (touching, overlapping, (mtv distance, mtv axis)) (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 string
`__str__`()[source]

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

`__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 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 `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 `numbers.Number` 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 `numbers.Number` ValueError – if trying to set `height <= 1e-07`
`area`

Get the area of this rect

Returns: area of this rect `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) the projection of the rect along axis `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: rect (`pygorithm.geometry.rect2.Rect2`) – the rect point (`pygorithm.geometry.vector2.Vector2`) – the point point on edge, point inside 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: 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) (touching, overlapping, (mtv distance, mtv axis)) (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: 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) (touching, overlapping, (mtv distance, mtv axis)) (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: 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) (touching, overlapping, (mtv distance, mtv axis)) (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) (touching, overlapping, (mtv distance, mtv axis)) (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 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 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 if the point will intersect the line, distance until intersection 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: 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 if the lines will ever intersect, distance until intersection 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: 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 if they will intersect 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: 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 if they will intersect 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: 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 if they will intersect 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: 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 if an intersection will occur 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: 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 if an intersection will occur 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: 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 if an intersection will occur 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: 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 if an intersectino will occur bool