Welcome to sect’s documentation!
Note
If object is not listed in documentation it should be considered as implementation detail that can change and should not be relied upon.
decomposition module
- class sect.decomposition.Graph(root: Node)[source]
Represents trapezoidal decomposition graph.
- classmethod from_multisegment(multisegment: ~ground.hints.Multisegment, *, shuffler: ~typing.Callable[[~typing.MutableSequence], None] = <bound method Random.shuffle of <random.Random object>>, context: ~ground.base.Context) Graph [source]
Constructs trapezoidal decomposition graph of given multisegment.
Based on incremental randomized algorithm by R. Seidel.
- Time complexity:
O(segments_count * log segments_count)
expected,O(segments_count ** 2)
worst- Memory complexity:
O(segments_count)
where
segments_count = len(multisegment.segments)
- Reference:
https://doi.org/10.1016%2F0925-7721%2891%2990012-4 https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/A%20Simple%20and%20fast.pdf
- Parameters
multisegment – target multisegment.
shuffler – function which mutates sequence by shuffling its elements, required for randomization.
context – geometric context.
- Returns
trapezoidal decomposition graph of the multisegment.
>>> from ground.base import get_context >>> context = get_context() >>> Multisegment, Point, Segment = (context.multisegment_cls, ... context.point_cls, ... context.segment_cls) >>> graph = Graph.from_multisegment( ... Multisegment([Segment(Point(0, 0), Point(1, 0)), ... Segment(Point(0, 0), Point(0, 1))]), ... context=context ... ) >>> Point(1, 0) in graph True >>> Point(0, 1) in graph True >>> Point(1, 1) in graph False >>> graph.locate(Point(1, 0)) is Location.BOUNDARY True >>> graph.locate(Point(0, 1)) is Location.BOUNDARY True >>> graph.locate(Point(1, 1)) is Location.EXTERIOR True
- classmethod from_polygon(polygon: ~ground.hints.Polygon, *, shuffler: ~typing.Callable[[~typing.MutableSequence], None] = <bound method Random.shuffle of <random.Random object>>, context: ~ground.base.Context) Graph [source]
Constructs trapezoidal decomposition graph of given polygon.
Based on incremental randomized algorithm by R. Seidel.
- Time complexity:
O(vertices_count * log vertices_count)
expected,O(vertices_count ** 2)
worst- Memory complexity:
O(vertices_count)
where
vertices_count = (len(polygon.border.vertices) + sum(len(hole.vertices) for hole in polygon.holes) + len(extra_points) + len(extra_constraints))
- Reference:
https://doi.org/10.1016%2F0925-7721%2891%2990012-4 https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/A%20Simple%20and%20fast.pdf
- Parameters
polygon – target polygon.
shuffler – function which mutates sequence by shuffling its elements, required for randomization.
context – geometric context.
- Returns
trapezoidal decomposition graph of the border and holes.
>>> from ground.base import get_context >>> context = get_context() >>> Contour, Point, Polygon = (context.contour_cls, context.point_cls, ... context.polygon_cls) >>> graph = Graph.from_polygon( ... Polygon(Contour([Point(0, 0), Point(6, 0), Point(6, 6), ... Point(0, 6)]), ... [Contour([Point(2, 2), Point(2, 4), Point(4, 4), ... Point(4, 2)])]), ... context=context ... ) >>> Point(1, 1) in graph True >>> Point(2, 2) in graph True >>> Point(3, 3) in graph False >>> graph.locate(Point(1, 1)) is Location.INTERIOR True >>> graph.locate(Point(2, 2)) is Location.BOUNDARY True >>> graph.locate(Point(3, 3)) is Location.EXTERIOR True
- property height: int
Returns height of the root node.
triangulation module
- class sect.triangulation.QuadEdge(start: Optional[Point] = None, left_from_start: Optional[QuadEdge] = None, rotated: Optional[QuadEdge] = None, *, context: Context)[source]
- Based on:
quad-edge data structure.
- Reference:
https://en.wikipedia.org/wiki/Quad-edge http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf
- classmethod from_endpoints(start: Point, end: Point, *, context: Context) QuadEdge [source]
Creates new edge from endpoints.
- property end: Point
aka “Dest” in L. Guibas and J. Stolfi notation.
- property start: Point
aka “Org” in L. Guibas and J. Stolfi notation.
- class sect.triangulation.Triangulation(left_side: QuadEdge, right_side: QuadEdge, context: Context)[source]
Represents triangulation.
- classmethod constrained_delaunay(polygon: Polygon, *, extra_constraints: Sequence[Segment] = (), extra_points: Sequence[Point] = (), context: Context) Triangulation [source]
Constructs constrained Delaunay triangulation of given polygon (with potentially extra points and constraints).
Based on
divide-and-conquer algorithm by L. Guibas & J. Stolfi for generating Delaunay triangulation,
algorithm by S. W. Sloan for adding constraints to Delaunay triangulation,
clipping algorithm by F. Martinez et al. for deleting in-hole triangles.
- Time complexity:
O(vertices_count * log vertices_count)
for convex polygons without extra constraints,O(vertices_count ** 2)
otherwise- Memory complexity:
O(vertices_count)
where
vertices_count = (len(polygon.border.vertices) + sum(len(hole.vertices) for hole in polygon.holes) + len(extra_points) + len(extra_constraints))
- Reference:
http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf https://www.newcastle.edu.au/__data/assets/pdf_file/0019/22519/23_A-fast-algortithm-for-generating-constrained-Delaunay-triangulations.pdf https://doi.org/10.1016/j.advengsoft.2013.04.004 http://www4.ujaen.es/~fmartin/bool_op.html
- Parameters
polygon – target polygon.
extra_points – additional points to be presented in the triangulation.
extra_constraints – additional constraints to be presented in the triangulation.
context – geometric context.
- Returns
triangulation of the border, holes & extra points considering constraints.
- classmethod delaunay(points: Sequence[Point], *, context: Context) Triangulation [source]
Constructs Delaunay triangulation of given points.
Based on divide-and-conquer algorithm by L. Guibas & J. Stolfi.
- Time complexity:
O(len(points) * log len(points))
- Memory complexity:
O(len(points))
- Reference:
- Parameters
points – 3 or more points to triangulate.
context – geometric context.
- Returns
triangulation of the points.