API Documentation

class incrementalconvexhull.graph.Graph

Undirected convex graph of 2D Euclidean points. Points are stored in a list in counterclockwise sorted order. Edges are stored using an adjacency list on each vertex.

add_edge(v1, v2)

Add an edge between two vertices in the graph.

Params:

v1 (Vertex): Vertex at one endpoint of the graph

v2 (Vertex): Vertex at opposite end of edge

Returns:

None Raise ValueError if a duplicate edge is being added to graph

add_vertex(x, y)

Add a vertex at an XY position to the graph and return the new Vertex. If the point is already on the interior of the convex hull, no action is taken. Similarly, any vertices currently on the hull that become interior vertices due to the addition of z are removed.

Params:

x (flaot): x coordinate of vertex y (float): y coordinate of vertex

Returns:

None

can_flip(v1, v2)

Returns whether an edge in the graph can be flipped. See flip_edge().

Params:

v1 (Vertex): Vertex at one end of the edge to flip v2 (Vertex): Vertex at the other end of the edge to flip

Returns:

True if an edge can be flipped between the 2 verticies False if the edge cannot be flipped between the 2 veritices

check_can_flip(v1, v2)

Returns a ValueError if an edge in the graph cannot be flipped. See flip_edge().

Params:

v1 (Vertex): Vertex at one end of the edge to flip v2 (Vertex): Vertex at the other end of the edge to flip

Returns:

None

Raises:

ValueError: The edge cannot be flipped

edges()

Return a generator over all edges in the graph.

Params:

None

Returns:

Generator of all edges in the graph represented as (current vertex (Vertex), neighbors list (List)

find_convex_nbrs(v)

Find neighbors of the newly inserted point in the existing graph

Params:

v (Vertex): Vertex to be inserted into the graph

Returns:

None Raise ValueError if there are less than 2 points in the graph

flip_between(a, b)

Transform the given graph’s triangulation such that an edge between a and b exists.

Params:

a (Vertex): b (Vertex):

Returns:

None

flip_edge(v1, v2)

Flip an edge between two vertices in graph.

An edge is flipped by creating a new edge crossing the other diagonal of the quadrilateral formed by the triangles on either side of the original edge.

Raises a ValueError if the edge cannot be flipped for any of the following reasons:

• Either vertex is not in the graph.

• The edge is not in the graph.

• The edge is on the convex hull of the graph.

Note that the quadrilateral formed by the triangles on either side of the edge is never concave because the vertices of the graph form a convex polygon.

Params:

v1 (Vertex): Vertex at one end of the edge to flip v2 (Vertex): Vertex at the other end of the edge to flip

Returns:

None

Raises:

ValueError: The edge cannot be flipped

get_cross_edges(a, b)

Compute the edges in the graph that cross the line through the specified vertices.

Params:

a (Vertex): b (Vertex):

Returns:

None

hull_contains(x, y)

Return whether an XY position is inside the convex hull of the vertices of the graph.

Params:

x (float): position x coordinate y (float): position y coordinate

Returns:

True if point is contained within the hull. False if the point is on the convex hull boundary or outside of the hull.

index(v)

Return the index of the vertex

Params:

v (Vertex): Vertex to index

Returns:

Index of vertex in graph vertex list (int)

remove_edge(v1, v2)

Remove the edge between two vertictes from the graph.

Params:

v1 (Vertex): Vertex at the end of edge to be removed v2 (Vertex): Vertex at the opposing end of the edge to be removed

Returns:

None

remove_vertex(v1)

Remove a vertex and all its edges from the graph.

Params:

v1 (Vertex): Vertex to be removed from the graph

Returns:

None

vertex_pairs()

Return a generator over all pairs of adjacent points on the convex hull.

Params:

None

Returns:

Generator of all pairs of adjacent points in the form (Vertex, Vertex)

class incrementalconvexhull.graph.Vertex(x, y)

Vertex in an undirected graph of 2D Euclidean points. Each vertex contains a list of neighboring vertices for which there is a connecting edge. The list of vertices is sorted counterclockwise by angle, however the starting index is arbitrary.

add_neighbor(v)

Add another vertex as a neighbor to this one.

Params:

v (Vertex): Adds the vertex to the list of neighbors in the current vertex

Returns:

None

get_next_nbr(v)

Returns the next neighboring vertex in counterclockwise order.

Params:

v (Vertex): vertex to find next neighbor in ccw order

Returns:

neighboring vertex in CCW order

nbr_pairs()

Return a generator over all pairs of adjacent points on the list of neighbors.

remove_neighbor(v)

Remove another vertex as a neighbor of this one. This does NOT remove this vertex as a neighbor of the other one.

Params:

v (Vertex): Vertex to be removed from list of neighbors

Returns:

None