geometry

2D geometry primitives and implementation of some geometric algorithms.

class backpack.geometry.Point(x, y)

Bases: object

A point on the 2D plane.

Parameters:

  • x (float) – The x coordinate of the point

  • y (float) – The y coordinate of the point

x: float

The x coordinate of the point

y: float

The y coordinate of the point

static ccw(pt1, pt2, pt3)

Determines if the three points form a counterclockwise angle. If two points are equal, or the three points are collinear, this method returns True.

Parameters:

  • pt1 (Point) – The first point

  • pt2 (Point) – The second point

  • pt3 (Point) – The third point

Returns:

True if the points form a counterclockwise angle

Return type:

bool

distance(other)

Calculates the distance between this and an other point.

Parameters:

other (Point) – The other point

Returns:

The distance between this and an other point.

Return type:

float

classmethod from_value(value)

Deserializes a Point from different formats.

Supported formats:

  • sequence containing exactly two numbers

  • dictionary containing numbers under ‘x’ and ‘y’ keys

  • Point instance (returns the same instance)

Parameters:

value – the value to be converted

Return: The new Point instance

Raises:

ValueError – If the conversion was not successful.

class backpack.geometry.Line(pt1, pt2)

Bases: object

A line segment.

Parameters:

  • pt1 (float) – The first point of the line segment

  • pt2 (float) – The second point of the line segment

class Intersection(value)

Bases: Enum

The intersection type of two line segments.

LEFT = -1

The second segment intersects the first one in left direction.

NONE = 0

The two segments do not intersect.

RIGHT = 1

The second segment intersects the first one in right direction.

pt1: Point

The first point of the line segment

pt2: Point

The second point of the line segment

intersects(other)

Determines if this line segment intersects an other one.

The direction of intersection is interpreted as follows. Place an observer to the first point of this line, looking to the second point of this line. If the second point of the other line is on the left side, the directions of the intersection is “left”, otherwise it is “right”. Attention: when considering the line intersection direction, keep in mind that the geometry module uses the screen coordinate system orientation, i.e. the origin can be found in the upper left corner of the screen.

Parameters:

other (Line) – The other line segment

Returns:

The line intersection type.

Return type:

Intersection

classmethod from_value(value)

Deserializes a Line from different formats.

Supported formats:

  • sequence containing exactly two values that can be deserialized with Point.from_value

  • dictionary containing such Point values under ‘pt1’ and ‘pt2’ keys

  • Line instance (returns the same instance)

Parameters:

value – the value to be converted

Returns:

The Line instance

Raises:

ValueError – If the value could not be converted to a Line.

class backpack.geometry.Rectangle(pt1, pt2)

Bases: object

An axis aligned rectangle.

Parameters:

  • pt1 (Point) – The first corner of the rectangle

  • pt2 (Point) – The second corner of the rectangle

pt1: Point

The first corner of the rectangle

pt2: Point

The second corner of the rectangle

has_inside(pt)

Determines if a point is inside this rectangle.

Parameters:

pt (Point) – the point

Returns:

True if the point lies inside this rectangle.

Return type:

bool

property pt_min: Point

The point with the minimum coordinates of this rectangle.

property pt_max: Point

The point with the maximum coordinates of this rectangle.

property center: Point

The center of the rectangle.

property base: Point

Returns the center of the base of the rectangle.

property size: Tuple[float, float]

The width and height of the rectangle.

property width: float

The width of the rectangle.

property height: float

The height of the rectangle.

property area: float

The area of the rectangle.

property aspect_ratio: float

The aspect ratio of the rectangle.

property top: float

The top edge of the rectangle.

property left: float

The left edge of the rectangle.

property bottom: float

The bottom edge of the rectangle.

property right: float

The right edge of the rectangle.

property tlbr: Tuple[float, float, float, float]

Returns this rectangles coordinates as a top-left-bottom-right tuple.

property tlhw: Tuple[float, float, float, float]

Returns this rectangles coordinates as a top-left-width-height tuple.

classmethod from_value(value)

Converts a tuple in the form of ((0.1, 0.2), (0.3, 0.4)) to a Rectangle.

Parameters:

value – the tuple

Returns:

The Rectangle instance

Raises:

ValueError – If the tuple could not be converted to a Rectangle.

classmethod from_tlbr(tlbr)

Converts a top-left-bottom-right sequence of floats to a Rectangle.

Parameters:

tlbr (Tuple[float, float, float, float]) – A top-left-bottom-right sequence of floats.

Returns:

The Rectangle instance

Raises:

ValueError – If the sequence could not be converted to a Rectangle.

Return type:

Rectangle

classmethod from_tlhw(tlhw)

Converts a top-left-width-height sequence of floats to a Rectangle.

Parameters:
Returns:

The Rectangle instance

Raises:

ValueError – If the sequence could not be converted to a Rectangle.

Return type:

Rectangle

class backpack.geometry.PolyLine(points, closed=True)

Bases: object

A PolyLine is a connected series of line segments.

Parameters:
points: Sequence[Point]

The list of the points of the PolyLine

closed: bool = True

True if the PolyLine is closed.

property lines: List[Line]

The line segments of this PolyLine

property boundingbox: Rectangle

The bounding box of this PolyLine

property self_intersects: bool

Determines if this PolyLine self-intersects.

property is_convex: bool

Determines if the polygon formed from this PolyLine is convex.

The result of this method is undefined for complex (self-intersecting) polygons.

Returns:

True if the polygon is convex, False otherwise.

has_inside(point)

Determines if a point is inside this closed PolyLine.

This implementation uses the ray casting algorithm.

Parameters:

point (Point) – The point

Returns:

True if the point is inside this closed PolyLine.

Return type:

bool

classmethod from_value(value, closed=True)

Converts a tuple in the form of ((0.1, 0.2), (0.3, 0.4), …) to a PolyLine.

Parameters:

  • value – the tuple

  • closed – flags if the newly created PolyLine should be closed or not.

Returns:

The PolyLine instance

Raises:

ValueError – If the tuple could not be converted to a PolyLine.