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: sect.core.trapezoidal.node.Node)[source]

Represents trapezoidal decomposition graph.

classmethod from_multisegment(multisegment: ground.core.hints.Multisegment, *, shuffler: Callable[[MutableSequence], None] = <bound method Random.shuffle of <random.Random object>>, context: ground.base.Context)sect.core.trapezoidal.graph.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, where segments_count = len(multisegment).

Memory complexity:

O(segments_count), where segments_count = len(multisegment).

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.core.hints.Polygon, *, shuffler: Callable[[MutableSequence], None] = <bound method Random.shuffle of <random.Random object>>, context: ground.base.Context)sect.core.trapezoidal.graph.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, where vertices_count = len(border) + sum(map(len, holes)).

Memory complexity:

O(vertices_count), where vertices_count = len(border) + sum(map(len, holes)).

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

Returns height of the root node.

locate(point: ground.core.hints.Point)sect.core.trapezoidal.location.Location[source]

Finds location of point relative to decomposed geometry.

Time complexity:

O(self.height)

Memory complexity:

O(1)

class sect.decomposition.Location(value)[source]

Represents kinds of locations in which point can be relative to geometry.

EXTERIOR = 0

point lies in the exterior of the geometry

BOUNDARY = 1

point lies on the boundary of the geometry

INTERIOR = 2

point lies in the interior of the geometry

triangulation module

class sect.triangulation.QuadEdge(start: Optional[ground.core.hints.Point] = None, left_from_start: Optional[sect.core.delaunay.quad_edge.QuadEdge] = None, rotated: Optional[sect.core.delaunay.quad_edge.QuadEdge] = None, *, context: ground.base.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: ground.core.hints.Point, end: ground.core.hints.Point, *, context: ground.base.Context)sect.core.delaunay.quad_edge.QuadEdge[source]

Creates new edge from endpoints.

property left_from_start

aka “Onext” in L. Guibas and J. Stolfi notation.

property end

aka “Dest” in L. Guibas and J. Stolfi notation.

property left_from_end

aka “Lnext” in L. Guibas and J. Stolfi notation.

property opposite

aka “Sym” in L. Guibas and J. Stolfi notation.

property right_from_end

aka “Rprev” in L. Guibas and J. Stolfi notation.

property right_from_start

aka “Oprev” in L. Guibas and J. Stolfi notation.

property rotated

aka “Rot” in L. Guibas and J. Stolfi notation.

property start

aka “Org” in L. Guibas and J. Stolfi notation.

connect(other: sect.core.delaunay.quad_edge.QuadEdge)sect.core.delaunay.quad_edge.QuadEdge[source]

Connects the edge with the other.

delete()None[source]

Deletes the edge.

orientation_of(point: ground.core.hints.Point)ground.core.enums.Orientation[source]

Returns orientation of the point relative to the edge.

splice(other: sect.core.delaunay.quad_edge.QuadEdge)None[source]

Splices the edge with the other.

swap()None[source]

Swaps diagonal in a quadrilateral formed by triangles in both clockwise and counterclockwise order around the start.

class sect.triangulation.Triangulation(left_side: sect.core.delaunay.quad_edge.QuadEdge, right_side: sect.core.delaunay.quad_edge.QuadEdge, context: ground.base.Context)[source]

Represents triangulation.

classmethod constrained_delaunay(polygon: ground.core.hints.Polygon, *, extra_constraints: Sequence[ground.core.hints.Segment] = (), extra_points: Sequence[ground.core.hints.Point] = (), context: ground.base.Context)sect.core.delaunay.triangulation.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, where vertices_count = len(border) + sum(map(len, holes))     + len(extra_points) + len(extra_constraints).

Memory complexity:

O(vertices_count), where vertices_count = len(border) + sum(map(len, 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.

>>> from ground.base import get_context
>>> context = get_context()
>>> Contour, Point, Polygon = (context.contour_cls, context.point_cls,
...                            context.polygon_cls)
>>> dart = [Point(0, 0), Point(3, 0), Point(1, 1), Point(0, 3)]
>>> (Triangulation.constrained_delaunay(Polygon(Contour(dart), []),
...                                     context=context).triangles()
...  == [Contour([Point(0, 0), Point(3, 0), Point(1, 1)]),
...      Contour([Point(0, 0), Point(1, 1), Point(0, 3)])])
True
classmethod delaunay(points: Sequence[ground.core.hints.Point], *, context: ground.base.Context)sect.core.delaunay.triangulation.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:

http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf

Parameters
  • points – 3 or more points to triangulate.

  • context – geometric context.

Returns

triangulation of the points.

>>> from ground.base import get_context
>>> context = get_context()
>>> Contour, Point = context.contour_cls, context.point_cls
>>> dart = [Point(0, 0), Point(3, 0), Point(1, 1), Point(0, 3)]
>>> (Triangulation.delaunay(dart,
...                         context=context).triangles()
...  == [Contour([Point(0, 0), Point(3, 0), Point(1, 1)]),
...      Contour([Point(0, 0), Point(1, 1), Point(0, 3)]),
...      Contour([Point(0, 3), Point(1, 1), Point(3, 0)])])
True
delete(edge: sect.core.delaunay.quad_edge.QuadEdge)None[source]

Deletes given edge from the triangulation.

triangles()List[ground.core.hints.Contour][source]

Returns triangles of the triangulation.