10.1.4.8. Polygon

Module to implement polygon and convex hull.

For resources on polygon see this section.

class Patro.GeometryEngine.Polygon.Polygon2D(*points, is_convex=None, is_clockwise=None)[source]

Bases: Patro.GeometryEngine.Primitive.Primitive2DMixin, Patro.GeometryEngine.Primitive.ClosedPrimitiveMixin, Patro.GeometryEngine.Primitive.PathMixin, Patro.GeometryEngine.Primitive.PrimitiveNP

Class to implements 2D Polygon.

__init__(*points, is_convex=None, is_clockwise=None)[source]

Initialize self. See help(type(self)) for accurate signature.

_check_area()[source]
_check_moment()[source]
_compute_area_barycenter()[source]

Compute polygon area and barycenter.

_compute_inertia_moment()[source]

Compute inertia moment on vertices.

_crossing_number_test(point)[source]

Crossing number test for a point in a polygon.

_test_is_convex()[source]
_test_is_simple()[source]
_winding_number_test(point)[source]

Winding number test for a point in a polygon.

area

Return polygon area.

axis_ratio
barycenter

Return polygon barycenter.

convex_hull()[source]
edges
is_clockwise
is_concave
is_convex
is_counterclockwise
is_point_inside(point)[source]
is_simple

Test if the polygon is simple, i.e. if it doesn’t self-intersect.

is_triangle
major_axis
major_axis_angle
minor_axis
perimeter
point_barycenter
recenter()[source]

Recenter the polygon to the barycenter.

to_triangle()[source]
class Patro.GeometryEngine.Polygon.RegularPolygon(center, radius, number_of_edges, angle=0)[source]

Bases: Patro.GeometryEngine.Polygon.Polygon2D

Class to implement regular polygon (N-gon).

LARGE_NGON_NAMES = {24: 'icositetragon', 30: 'triacontagon', 40: 'tetracontagon', 50: 'pentacontagon', 60: 'hexacontagon', 70: 'heptacontagon', 80: 'octacontagon', 90: 'enneacontagon', 100: 'hectogon', 257: '257-gon', 1000: 'chiliagon', 10000: 'myriagon', 65537: '65537-gon', 1000000: 'megagon'}
NGON_NAMES = ('monogon', 'digon', 'triangle', 'quadrilateral', 'pentagon', 'hexagon', 'heptagon', 'octagon', 'nonagon', 'decagon', 'hendecagon', 'dodecagon', 'tridecagon', 'tetradecagon', 'pentadecagon', 'hexadecagon', 'heptadecagon', 'octadecagon', 'enneadecagon', 'icosagon')
__init__(center, radius, number_of_edges, angle=0)[source]

Initialize self. See help(type(self)) for accurate signature.

angle
center
circumcircle
edge_angle
classmethod ngon_name(number_of_edges)[source]
number_of_edges
radius
str_name
Patro.GeometryEngine.Polygon.ccw(p1, p2, p3)[source]

Three points are a counter-clockwise turn if ccw > 0, clockwise if ccw < 0, and collinear if ccw = 0 because ccw is a determinant \((\mathbf{P}_3-\mathbf{P}_1) \cross (\mathbf{P}_2-\mathbf{P}_1)\) that gives twice the signed area of the triangle formed by p1, p2 and p3.

Patro.GeometryEngine.Polygon.convex_hull(points, as_polygon=True)[source]

Return the convex hull of the list of points using Graham Scan algorithm.

  • The first point is the leftmost point having the smallest y-coordinate.
  • The polygon is counter-clockwise oriented.
  • Time complexity is O(n log n).

References

Patro.GeometryEngine.Polygon.is_three_point_ccw(p1, p2, p3)[source]
Patro.GeometryEngine.Polygon.is_three_point_collinear(p1, p2, p3)[source]
Patro.GeometryEngine.Polygon.is_three_point_cw(p1, p2, p3)[source]
Patro.GeometryEngine.Polygon.sort_point_for_graham_scan(points)[source]

Sort the points for the Graham scan algorithm.

points must be an iterable.

The first step in this algorithm is to find the point with the lowest y-coordinate. If the lowest y-coordinate exists in more than one point in the set, the point with the lowest x-coordinate out of the candidates should be chosen. Call this point P0. This step takes O(n).

Next, the set of points must be sorted in increasing order of the angle they and the point P0 make with the x-axis.