# 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.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

Memory complexity:

`O(segments_count)`

where `segments_count = len(multisegment.segments)`

Reference:
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: 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

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:
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.

locate(point: ground.hints.Point)ground.core.enums.Location[source]

Finds location of point relative to decomposed geometry.

Time complexity:

`O(self.height)`

Memory complexity:

`O(1)`

# triangulation module¶

Based on:

Reference:

Creates new edge from endpoints.

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

property end: ground.hints.Point

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

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

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

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

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

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

property start: ground.hints.Point

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

Connects the edge with the other.

delete()None[source]

Deletes the edge.

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

Returns orientation of the point relative to the edge.

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.

Represents triangulation.

classmethod constrained_delaunay(polygon: ground.hints.Polygon, *, extra_constraints: Sequence[ground.hints.Segment] = (), extra_points: Sequence[ground.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

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:
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[ground.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:

Parameters
• points – 3 or more points to triangulate.

• context – geometric context.

Returns

triangulation of the points.