triangulate module

synopsis:Module contains functions and classes used to triangulate a discretionary polygon which employ the algorithm described in de Berg’s ‘Computational Geometry’, chapter 3.
class triangulate.Edge(start=None, end=None, helper=None)

Bases: object

Class represents a polygon edge on a 2D plane.

Parameters:
  • start (Vertex) – edge first vertex.
  • end (Vertex) – edge second vertex.
  • helper (Vertex) – edge helper vertex.
class triangulate.Polygon(vertices)

Bases: object

Class represents a polygon with its vertices and edges.

Parameters:vertices (list of Vertex) – list of polygon vertices.
centroid()

Calculate polygons centeroid (geometric centre).

Returns:polygon centroid.
Return type:Vertex
edge_index(e)

Get an index of a given vertex.

Parameters:v (Vertex) – examined vertex.
Returns:index of a given vertex.
Return type:integer
get_edge(v)

Get a polygon edge begining in a given vertex.

Parameters:v (Vertex) – examined vertex.
Returns:an edge that begins in a given vertex.
Return type:Edge
get_first_edge()

Get first edge of the polygon.

Returns:first edge of the polygon.
Return type:Edge
get_first_vertex()

Get first vertex of the polygon.

Returns:first vertex of the polygon.
Return type:Vertex
get_vertices()

Get a list of polygon vertices.

Returns:list of polygon vertices.
Return type:list of Vertex
next_edge(v=None, edge=None)

Get an edge following the given one, or a given vertex, in the edges list.

Parameters:
  • v (Vertex) – examined vertex.
  • edge (Edge) – examined edge
Returns:

edge following the given one, or a given vertex.
Return type:

Edge
next_vertex(v)

Get a vertex following the given one in the vertices list.

Parameters:v (Vertex) – examined vertex.
Returns:vertex following the given one.
Return type:Vertex
num_of_vertices()

Get number of polygon vertices.

Returns:number of polygon vertices.
Return type:integer
point_in_polygon(v)

Check whether given point lies within the polygon. Source: http://idav.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html

Parameters:v (Vertex) – examined point.
Returns:True of v lies within the polygon area, False otherwise.
Return type:boolean
previous_edge(v=None, edge=None)

Get an edge preceding the given one, or a given vertex, in the edges list.

Parameters:
  • v (Vertex) – examined vertex.
  • edge (Edge) – examined edge
Returns:

edge preceding the given one, or a given vertex.
Return type:

Edge
previous_vertex(v)

Get a vertex preceding the given one in the vertices list.

Parameters:v (Vertex) – examined vertex.
Returns:vertex preceding the given one.
Return type:Vertex
signed_area(vertices=None)

Calculate a signed polygon area (ie. positive or negative).

Parameters:vertices (list of Vertex) – list of vertices constituing a polygon. If none is given, method computes area of self.
Returns:signed polygon area.
Return type:float
vertex_index(v)

Get an index of a given vertex.

Parameters:v (Vertex) – examined vertex.
Returns:index of a given vertex.
Return type:integer
class triangulate.Vertex(x, y, v_type=None)

Bases: object

Class represents a polygon vertex on a 2D plane.

Parameters:
  • x (float) – vertex x coordinate.
  • y (float) – vertex y coordinate.
  • v_type (string) – vertex type.
triangulate.angle(v1, v2, v3)

Calculate an angle between points v1, v2 and v3. Source: https://stackoverflow.com/questions/1211212/how-to-calculate-an-angle-from-three-points

Parameters:
  • v1 (Vertex) – angle first point.
  • v2 (Vertex) – angle second point.
  • v3 (Vertex) – angle third point.
Returns:

Angle between v1, v2 and v3 in radians.
Return type:

float
triangulate.create_edges(p)

Create edges list from a given vertices list.

Parameters:p (list of Vertex) –
Returns:list of created edges.
Return type:list of Edge
triangulate.inner_diagonal(v1, v2, polygon)

Check whether given line segment constitutes a inner diagonal of the polygon. Source: https://stackoverflow.com/questions/693837/how-to-determine-a-diagonal-is-in-or-out-of-a-concave-polygon

Parameters:
  • v1 (Vertex) – first diagonal point.
  • v2 (Vertex) – second diagonal point.
  • polygon (Polygon) – examined polygon.
Returns:

True if a line segment contitutes an inner polygon diagonal, False otherwise.
Return type:

boolean
triangulate.intersect(v1, v2, v3, v4)

Calculate a intersection point of two line segments. Source: https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

Parameters:
  • v1 (Vertex) – original point of the first line segment.
  • v2 (Vertex) – final point of the first line segment.
  • v3 (Vertex) – original point of the second line segment.
  • v4 (Vertex) – final point of the second line segment.
Returns:

None if line segments do not intersect, a intersection point otherwise.
Return type:

Vertex
triangulate.make_monotone(polygon)

Divide a polygon into y-monotone pieces. Source: de Berg, van Kreveld, Overmars, Schwrzkopf ‘Computational geometry’ Section 3.2

Parameters:polygon (Polygon) – polygon to be divided.
Returns:list of diagonals dividing the polygon into y-monotone pieces.
Return type:list of Edge
triangulate.overlapping(v1, v2, v3, v4)

Check whether two line segments overlap each other. Source: https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

Parameters:
  • v1 (Vertex) – original point of the first line segment.
  • v2 (Vertex) – final point of the first line segment.
  • v3 (Vertex) – original point of the second line segment.
  • v4 (Vertex) – final point of the second line segment.
Returns:

True if line segment overlap each other, False otherwise.
Return type:

boolean
triangulate.plot_diags(polygon, diags, point=None, point2=None, title=None)

Plot polygon diagonals.

Parameters:
  • diags (list of Edge) – list of diagonals to be ploted.
  • point (Vertex) – point to be ploted againts the polygon with diagonals.
  • point2 (Vertex) – second point to be ploted againts the polygon with diagonals.
  • title (string) – plot title.
triangulate.split_polygons(polygon, diagolnals)

Split a polygon into separate shapes along given diagonals. Source https://stackoverflow.com/questions/9455875/how-to-split-a-polygon-along-n-given-diagonals

Parameters:
  • polygon (Polygon.) – polygon to be split.
  • diagonals – diagonals along which the polygon is to be split.
Type:

diagonal: list of Edge
triangulate.triangulate_monotone_polygon(polygon)

Triangulate an y-monotone polygon. Source: de Berg, van Kreveld, Overmars, Schwrzkopf ‘Computational geometry’ Section 3.3

Parameters:polygon (Polygon) – y-monotone polygon to be triangulated.
triangulate.vector_between_two_other(v1, v2, v3)

Check whether a vector lies between two other. Source: https://stackoverflow.com/questions/693806/how-to-determine-whether-v3-is-between-v1-and-v2-when-we-go-from-v1-to-v2-counter/693969#693969

Parameters:
  • v1 (Vertex) – first vector limiting the area.
  • v2 (Vertex) – second vector limiting the area.
  • v3 (Vertex) – vector to be examined.