geom2d.polygon

Some handy polygon tools.

Includes convex hull, area, and centroid calculations.

Some references:

geom2d.polygon.all_points_inside(polygon: Sequence[TPoint], points: Iterable[TPoint], edge_ok: bool = False) → bool

True if all points are within the polygon.

geom2d.polygon.area(vertices: Iterable[TPoint]) → float

Area of a simple polygon.

Also determines winding (area >= 0 ==> CCW, area < 0 ==> CW).

Parameters:

vertices – the polygon vertices. A list of 2-tuple (x, y) points.

Returns (float):

The area of the polygon. The area will be negative if the vertices are ordered clockwise.

geom2d.polygon.area_triangle(a: Sequence[float], b: Sequence[float] | None = None, c: Sequence[float] | None = None) → float

Area of a triangle.

This is just a slightly more efficient specialization of the more general polygon area.

Parameters:

  • a – The first vertex of a triangle or an iterable of three vertices.

  • b – The second vertex or None if a is iterable.

  • c – The third vertex or None if a is iterable.

Returns (float):

The area of the triangle.

geom2d.polygon.centroid(vertices: Sequence[TPoint]) → P

Return the centroid of a simple polygon.

See http://paulbourke.net/geometry/polygonmesh/

Parameters:

vertices – The polygon vertices. A list of 2-tuple (x, y) points.

Returns:

The centroid point as a 2-tuple (x, y)

geom2d.polygon.clipper2poly(clipper_poly: Iterable[clipper.Point]) → list[P]

Convert a Clipper polygon to a float tuple polygon.

Convert a Clipper polygon (a list of integer 2-tuples) to a polygon (as a list of float 2-tuple vertices).

Parameters:

clipper_poly – An interable of integer coordinates.

Returns:

A list of floating point coordinates.

geom2d.polygon.convex_hull(points: Iterable[TPoint]) → list[P]

Returns points on convex hull of an array of points in CCW order.

Uses the Graham Scan algorithm.

Parameters:

points – a list of 2-tuple (x, y) points.

Returns:

The convex hull as a list of 2-tuple (x, y) points.

geom2d.polygon.convex_hull_chan(points: list[Sequence[float]]) → list[P]

Returns the points on the convex hull of points in CCW order.

Uses Chan’s algorithm. May be faster than Graham scan on large point collections.

See http://tomswitzer.net/2010/12/2d-convex-hulls-chans-algorithm/

Parameters:

points – a list of 2-tuple (x, y) points.

Returns:

The convex hull as a list of 2-tuple (x, y) points.

geom2d.polygon.intersect_line(polygon: Sequence[TPoint], lineseg: TLine, edge_ok: bool = False) → list[Line]

Compute the intersection(s) of a polygon/polyline and a line segment.

Parameters:

  • polygon – Polygon vertices.

  • lineseg – A line possibly intersecting the polygon. A sequence of two line end points, of the form ((x1, y1), (x2, y2)).

  • edge_ok – Intersection considered if segment endpoint lies on polygon edge.

Returns:

A list of one or more interior line segments that intersect the polygon or that lie completely within the polygon. Returns an empty list if there are no intersections.

geom2d.polygon.is_closed(polygon: Sequence[TPoint]) → bool

Test if the polygon is closed.

I.e. if the first vertice matches the last vertice.

geom2d.polygon.is_inside(polygon1: Sequence[TPoint], polygon2: Iterable[TPoint]) → bool

Is polygon2 inside polygon1?

It is assumed that the polygons are non-intersecting and non-self-intersecting.

geom2d.polygon.length(polyline: Iterable[TPoint]) → float

The total length of a polyline/polygon.

geom2d.polygon.offset_polygons(poly: Sequence[TPoint], offset: float, jointype: clipper.JoinType = 2, limit: float = 0.0) → list[list[P]]

Offset a polygon by offset amount.

This is also called polygon buffering.

See:

http://www.angusj.com/delphi/clipper.php

Parameters:

  • poly – A polygon as a list of 2-tuple vertices.

  • offset – The amount to offset (can be negative).

  • jointype – The type of joins for offset vertices.

  • limit – The max distance to a offset vertice before it will be squared off.

Returns:

Zero or more offset polygons as a list of 2-tuple vertices. If the specified offset cannot be performed for the input polygon an empty list will be returned.

geom2d.polygon.offset_polyline(poly: Sequence[TPoint], offset: float, jointype: clipper.JoinType = 2, endtype: clipper.EndType = 1, limit: float = 0.0) → list[list[P]]

Offset a polyline by offset amount.

This is also called polygon buffering.

See:

http://www.angusj.com/delphi/clipper.php

Parameters:

  • poly – A polyline as a list of 2-tuple vertices.

  • offset – The amount to offset (can be negative).

  • jointype – The type of joins for offset vertices.

  • endtype – The type of end caps for polylines.

  • limit – The max distance to a offset vertice before it will be squared off.

Returns:

Zero or more offset polygons as a list of 2-tuple vertices. If the specified offset cannot be performed for the input polygon an empty list will be returned.

geom2d.polygon.point_inside(polygon: Sequence[TPoint], p: TPoint, edge_ok: bool = False) → bool

Test if point is inside a closed polygon.

See:

The original C code:

int pnpoly(int nvert, float *x, float *y, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if (
      ((y[i] > testy) != (y[j] > testy)) &&
      (testx < (x[j] - x[i]) * (testy - y[i]) / (y[j] - y[i]) + x[i])
    )
       c = !c;
  }
  return c;
}
Parameters:

  • polygon – polygon vertices. A list of 2-tuple (x, y) points.

  • p – Point to test.

  • edge_ok – Point is considered inside if it lies on a vertex or an edge segment.

Returns:

True if the point lies inside the polygon, else False.

geom2d.polygon.poly2clipper(poly: Iterable[TPoint]) → list[clipper.Point]

Convert a polygon to a Clipper polygon.

Parameters:

poly – An iterable of floating point coordinates.

Returns:

A Clipper polygon which is a list of integer coordinates.

geom2d.polygon.poly_stroke_to_path(poly: Sequence[TPoint], stroke_width: float, jointype: clipper.JoinType = 2, endtype: clipper.EndType = 1, limit: float = 0.0) → list[list[P]]

Convert a stroke (line + width) to a path.

Parameters:

  • poly – A polyline as a list of 2-tuple vertices.

  • stroke_width – Stroke width.

  • offset – The amount to offset (can be negative).

  • jointype – The type of joins for offset vertices.

  • endtype – The type of end caps.

  • limit – The max distance to a offset vertice before it will be squared off.

If the stroke is a closed polygon then two closed sub-paths will be returned, allowing a fillable SVG entity defined by an inner and outer polygon.. Otherwise a single closed path.

geom2d.polygon.simplify_polyline_rdp(points: Sequence[TPoint], tolerance: float) → list[P]

Simplify a polyline.

A polyline is a sequence of vertices.

Uses Ramer-Douglas-Peucker algorithm.

See:

https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Parameters:

  • points – A sequence of polyline vertices.

  • tolerance (float) – Line flatness tolerance.

Returns:

A list of points defining the vertices of the simplified polyline.

geom2d.polygon.simplify_polyline_vw(points: Iterable[TPoint], min_area: float) → list[TPoint]

Simplify a polyline.

Uses Visvalingam-Whyatt algorithm.

See:

[1] Visvalingam, M., and Whyatt, J.D. (1992) “Line Generalisation by Repeated Elimination of Points”, Cartographic J., 30 (1), 46 - 51

Parameters:

  • points – A sequence of polyline vertices.

  • min_area – Minimum point triplet triangle area to filter for.

Returns:

A list of points defining the vertices of the simplified polyline.

geom2d.polygon.turn(p: Sequence[float], q: Sequence[float], r: Sequence[float]) → int

Determine relative direction of point.

Parameters:

  • p – Point from which initial direction is determined.

  • q – Point from which turn is determined.

  • r – End point which determines turn direction. I.e. from q this point is to the left or right of p.

Returns:

-1, 0, 1 if p,q,r forms a right, straight, or left turn.

geom2d.polygon.winding(vertices: Sequence[TPoint]) → int

Determine polygon winding.

Returns:

1 if CCW else -1 if CW