cam.voronoi#
BlenderCAM ‘voronoi.py’
Voronoi diagram calculator/ Delaunay triangulator
Voronoi Diagram Sweepline algorithm and C code by Steven Fortune, 1987, http://ect.bell-labs.com/who/sjf/
Python translation to file voronoi.py by Bill Simons, 2005, http://www.oxfish.com/
Additional changes for QGIS by Carson Farmer added November 2010
2012 Ported to Python 3 and additional clip functions by domlysz at gmail.com
Calculate Delaunay triangulation or the Voronoi polygons for a set of 2D input points.
Derived from code bearing the following notice:
The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T Bell Laboratories. Permission to use, copy, modify, and distribute this software for any purpose without fee is hereby granted, provided that this entire notice is included in all copies of any software which is or includes a copy or modification of this software and in all copies of the supporting documentation for such software. THIS SOFTWARE IS BEING PROVIDED “AS IS”, WITHOUT ANY EXPRESS OR IMPLIED WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
Comments were incorporated from Shane O’Sullivan’s translation of the original code into C++ (http://mapviewer.skynet.ie/voronoi.html)
Steve Fortune’s homepage: http://netlib.bell-labs.com/cm/cs/who/sjf/index.html
For programmatic use two functions are available:
computeVoronoiDiagram(points, xBuff, yBuff, polygonsOutput=False, formatOutput=False) : Takes :
a list of point objects (which must have x and y fields).
x and y buffer values which are the expansion percentages of the bounding box rectangle including all input points.
Returns : - With default options :
A list of 2-tuples, representing the two points of each Voronoi diagram edge. Each point contains 2-tuples which are the x,y coordinates of point. if formatOutput is True, returns :
a list of 2-tuples, which are the x,y coordinates of the Voronoi diagram vertices.
and a list of 2-tuples (v1, v2) representing edges of the Voronoi diagram. v1 and v2 are the indices of the vertices at the end of the edge.
If polygonsOutput option is True, returns : A dictionary of polygons, keys are the indices of the input points, values contains n-tuples representing the n points of each Voronoi diagram polygon. Each point contains 2-tuples which are the x,y coordinates of point. if formatOutput is True, returns :
A list of 2-tuples, which are the x,y coordinates of the Voronoi diagram vertices.
and a dictionary of input points indices. Values contains n-tuples representing the n points of each Voronoi diagram polygon. Each tuple contains the vertex indices of the polygon vertices.
- computeDelaunayTriangulation(points):
Takes a list of point objects (which must have x and y fields). Returns a list of 3-tuples: the indices of the points that form a Delaunay triangle.
Attributes#
Classes#
Functions#
|
Generate a Voronoi diagram from a list of sites. |
|
Check if two values are nearly equal within a specified relative error. |
|
Compute the Voronoi diagram for a set of points. |
|
Format edges output for a list of edges. |
|
Format the output of polygons into a standardized structure. |
|
Compute the Delaunay triangulation for a set of points. |
Module Contents#
- class Context[source]#
Bases:
object- getClipEdges()[source]#
Get the clipped edges based on the current extent.
This function iterates through the edges of a geometric shape and determines which edges are within the specified extent. It handles both finite and infinite lines, clipping them as necessary to fit within the defined boundaries. For finite lines, it checks if both endpoints are within the extent, and if not, it calculates the intersection points using the line equations. For infinite lines, it checks if at least one endpoint is within the extent and clips accordingly.
- Returns:
- A list of tuples, where each tuple contains two points representing the
clipped edges.
- Return type:
list
- getClipPolygons(closePoly)[source]#
Get clipped polygons based on the provided edges.
This function processes a set of polygons defined by their edges and vertices, clipping them according to the specified extent. It checks whether each edge is finite or infinite and determines if the endpoints of each edge are within the defined extent. If they are not, the function calculates the intersection points with the extent boundaries. The resulting clipped edges are then used to create polygons, which are returned as a dictionary. The user can specify whether to close the polygons or leave them open.
- Parameters:
closePoly (bool) – A flag indicating whether to close the polygons.
- Returns:
- A dictionary where keys are polygon indices and values are lists of
points defining the clipped polygons.
- Return type:
dict
- clipLine(x1, y1, equation, leftDir)[source]#
Clip a line segment defined by its endpoints against a bounding box.
This function calculates the intersection points of a line defined by the given equation with the bounding box defined by the extent of the object. Depending on the direction specified (left or right), it will return the appropriate intersection point that lies within the bounds.
- Parameters:
x1 (float) – The x-coordinate of the first endpoint of the line.
y1 (float) – The y-coordinate of the first endpoint of the line.
equation (tuple) – A tuple containing the coefficients (a, b, c) of the line equation in the form ax + by + c = 0.
leftDir (bool) – A boolean indicating the direction to clip the line. If True, clip towards the left; otherwise, clip towards the right.
- Returns:
The coordinates of the clipped point as (x, y).
- Return type:
tuple
- inExtent(x, y)[source]#
Check if a point is within the defined extent.
This function determines whether the given coordinates (x, y) fall within the boundaries defined by the extent of the object. The extent is defined by its minimum and maximum x and y values (xmin, xmax, ymin, ymax). The function returns True if the point is within these bounds, and False otherwise.
- Parameters:
x (float) – The x-coordinate of the point to check.
y (float) – The y-coordinate of the point to check.
- Returns:
True if the point (x, y) is within the extent, False otherwise.
- Return type:
bool
- orderPts(edges)[source]#
Order points to form a polygon.
This function takes a list of edges, where each edge is represented as a pair of points, and orders the points to create a polygon. It identifies the starting and ending points of the polygon and ensures that the points are connected in the correct order. If all points are duplicates, it recognizes that the polygon is complete and handles it accordingly.
- Parameters:
edges (list) – A list of edges, where each edge is a tuple or list containing two points.
- Returns:
- A tuple containing:
list: The ordered list of polygon points.
bool: A flag indicating whether the polygon is complete.
- Return type:
tuple
- setClipBuffer(xpourcent, ypourcent)[source]#
Set the clipping buffer based on percentage adjustments.
This function modifies the clipping extent of an object by adjusting its boundaries according to the specified percentage values for both the x and y axes. It calculates the new minimum and maximum values for the x and y coordinates by applying the given percentages to the current extent.
- Parameters:
xpourcent (float) – The percentage adjustment for the x-axis.
ypourcent (float) – The percentage adjustment for the y-axis.
- Returns:
This function does not return a value; it modifies the object’s extent in place.
- Return type:
None
- outSite(s)[source]#
Handle output for a site object.
This function processes the output based on the current settings of the instance. If debugging is enabled, it prints the site number and its coordinates. If triangulation is enabled, no action is taken. If printing is enabled, it prints the coordinates of the site.
- Parameters:
s (object) – An object representing a site, which should have attributes ‘sitenum’, ‘x’, and ‘y’.
- Returns:
This function does not return a value.
- Return type:
None
- outVertex(s)[source]#
Add a vertex to the list of vertices.
This function appends the coordinates of a given vertex to the internal list of vertices. Depending on the state of the debug, triangulate, and doPrint flags, it may also print debug information or vertex coordinates to the console.
- Parameters:
s (object) – An object containing the attributes x, y, and sitenum which represent the coordinates and identifier of the vertex.
- Returns:
This function does not return a value.
- Return type:
None
- outTriple(s1, s2, s3)[source]#
Add a triangle defined by three site numbers to the list of triangles.
This function takes three site objects, extracts their site numbers, and appends a tuple of these site numbers to the triangles list. If debugging is enabled, it prints the site numbers to the console. Additionally, if triangulation is enabled and printing is allowed, it prints the site numbers in a formatted manner.
- outBisector(edge)[source]#
Process and log the outbisector of a given edge.
This function appends the parameters of the edge (a, b, c) to the lines list and optionally prints debugging information or the parameters based on the state of the debug and doPrint flags. The function is designed to handle geometric edges and their properties in a computational geometry context.
- Parameters:
edge (Edge) – An object representing an edge with attributes a, b, c, edgenum, and reg.
- Returns:
This function does not return a value.
- Return type:
None
- outEdge(edge)[source]#
Process an edge and update the associated polygons and edges.
This function takes an edge as input and retrieves the site numbers associated with its left and right endpoints. It then updates the polygons dictionary to include the edge information for the regions associated with the edge. If the regions are not already present in the polygons dictionary, they are initialized. The function also appends the edge information to the edges list. If triangulation is not enabled, it prints the edge number and its associated site numbers.
- Parameters:
edge (Edge) – An instance of the Edge class containing information
- Returns:
This function does not return a value.
- Return type:
None
- voronoi(siteList, context)[source]#
Generate a Voronoi diagram from a list of sites.
This function computes the Voronoi diagram for a given list of sites. It utilizes a sweep line algorithm to process site events and circle events, maintaining a priority queue and edge list to manage the geometric relationships between the sites. The function outputs the resulting edges, vertices, and bisectors to the provided context.
- Parameters:
- Returns:
- This function does not return a value; it outputs results directly
to the context provided.
- Return type:
None
- isEqual(a, b, relativeError=TOLERANCE)[source]#
Check if two values are nearly equal within a specified relative error.
This function determines if the absolute difference between two values is within a specified relative error of the larger of the two values. It is useful for comparing floating-point numbers where precision issues may arise.
- Parameters:
a (float) – The first value to compare.
b (float) – The second value to compare.
relativeError (float) – The allowed relative error for the comparison.
- Returns:
True if the values are considered nearly equal, False otherwise.
- Return type:
bool
- class Site(x=0.0, y=0.0, sitenum=0)[source]#
Bases:
object- dump()[source]#
Dump the site information.
This function prints the site number along with its x and y coordinates in a formatted string. It is primarily used for debugging or logging purposes to provide a quick overview of the site’s attributes.
- Returns:
This function does not return any value.
- Return type:
None
- __lt__(other)[source]#
Compare two objects based on their coordinates.
This method implements the less-than comparison for objects that have x and y attributes. It first compares the y coordinates; if they are equal, it then compares the x coordinates. The method returns True if the current object is considered less than the other object based on these comparisons.
- Parameters:
other (object) – The object to compare against, which must have x and y attributes.
- Returns:
- True if the current object is less than the other object,
otherwise False.
- Return type:
bool
- __eq__(other)[source]#
Determine equality between two objects.
This method checks if the current object is equal to another object by comparing their ‘x’ and ‘y’ attributes. If both attributes are equal for the two objects, it returns True; otherwise, it returns False.
- Parameters:
other (object) – The object to compare with the current object.
- Returns:
True if both objects are equal, False otherwise.
- Return type:
bool
- distance(other)[source]#
Calculate the distance between two points in a 2D space.
This function computes the Euclidean distance between the current point (represented by the instance’s coordinates) and another point provided as an argument. It uses the Pythagorean theorem to calculate the distance based on the differences in the x and y coordinates of the two points.
- Parameters:
other (Point) – Another point in 2D space to calculate the distance from.
- Returns:
The Euclidean distance between the two points.
- Return type:
float
- class Edge[source]#
Bases:
object- dump()[source]#
Dump the current state of the object.
This function prints the values of the object’s attributes, including the edge number, and the values of a, b, c, as well as the ep and reg attributes. It is useful for debugging purposes to understand the current state of the object.
- setEndpoint(lrFlag, site)[source]#
Set the endpoint for a given flag.
This function assigns a site to the specified endpoint flag. It checks if the corresponding endpoint for the opposite flag is not set to None. If it is None, the function returns False; otherwise, it returns True.
- Parameters:
lrFlag (int) – The flag indicating which endpoint to set.
site (str) – The site to be assigned to the specified endpoint.
- Returns:
True if the opposite endpoint is set, False otherwise.
- Return type:
bool
- static bisect(s1, s2)[source]#
Bisect two sites to create a new edge.
This function takes two site objects and computes the bisector edge between them. It calculates the slope and intercept of the line that bisects the two sites, storing the necessary parameters in a new edge object. The edge is initialized with no endpoints, as it extends to infinity. The function determines whether to fix x or y based on the relative distances between the sites.
- class Halfedge(edge=None, pm=Edge.LE)[source]#
Bases:
object- dump()[source]#
Dump the internal state of the object.
This function prints the current values of the object’s attributes, including left, right, edge, pm, vertex, and ystar. If the vertex attribute is present and has a dump method, it will call that method to print the vertex’s internal state. Otherwise, it will print “None” for the vertex.
- __lt__(other)[source]#
Compare two objects based on their ystar and vertex attributes.
This method implements the less-than comparison for objects. It first compares the ystar attributes of the two objects. If they are equal, it then compares the x-coordinate of their vertex attributes to determine the order.
- Parameters:
other (YourClass) – The object to compare against.
- Returns:
- True if the current object is less than the other object, False
otherwise.
- Return type:
bool
- __eq__(other)[source]#
Check equality of two objects.
This method compares the current object with another object to determine if they are equal. It checks if the ‘ystar’ attribute and the ‘x’ coordinate of the ‘vertex’ attribute are the same for both objects.
- Parameters:
other (object) – The object to compare with the current instance.
- Returns:
True if both objects are considered equal, False otherwise.
- Return type:
bool
- leftreg(default)[source]#
Retrieve the left registration value based on the edge state.
This function checks the state of the edge attribute. If the edge is not set, it returns the provided default value. If the edge is set and its property indicates a left edge (Edge.LE), it returns the left registration value. Otherwise, it returns the right registration value.
- Parameters:
default – The value to return if the edge is not set.
- Returns:
The left registration value if applicable, otherwise the default value.
- rightreg(default)[source]#
Retrieve the appropriate registration value based on the edge state.
This function checks if the current edge is set. If it is not set, it returns the provided default value. If the edge is set and the current state is Edge.LE, it returns the registration value associated with Edge.RE. Otherwise, it returns the registration value associated with Edge.LE.
- Parameters:
default – The value to return if there is no edge set.
- Returns:
- The registration value corresponding to the current edge state or the
default value if no edge is set.
- isPointRightOf(pt)[source]#
Determine if a point is to the right of a half-edge.
This function checks whether the given point pt is located to the right of the half-edge represented by the current object. It takes into account the position of the top site of the edge and various geometric properties to make this determination. The function uses the edge’s parameters to evaluate the relationship between the point and the half- edge.
- Parameters:
pt (Point) – A point object with x and y coordinates.
- Returns:
True if the point is to the right of the half-edge, False otherwise.
- Return type:
bool
- intersect(other)[source]#
Create a new site where two edges intersect.
This function calculates the intersection point of two edges, represented by the current instance and another instance passed as an argument. It first checks if either edge is None, and if they belong to the same parent region. If the edges are parallel or do not intersect, it returns None. If an intersection point is found, it creates and returns a new Site object at the intersection coordinates.
- class EdgeList(xmin, xmax, nsites)[source]#
Bases:
object- insert(left, he)[source]#
Insert a node into a doubly linked list.
This function takes a node and inserts it into the list immediately after the specified left node. It updates the pointers of the surrounding nodes to maintain the integrity of the doubly linked list.
- Parameters:
left (Node) – The node after which the new node will be inserted.
he (Node) – The new node to be inserted into the list.
- delete(he)[source]#
Delete a node from a doubly linked list.
This function updates the pointers of the neighboring nodes to remove the specified node from the list. It also marks the node as deleted by setting its edge attribute to Edge.DELETED.
- Parameters:
he (Node) – The node to be deleted from the list.
- gethash(b)[source]#
Retrieve an entry from the hash table, ignoring deleted nodes.
This function checks if the provided index is within the valid range of the hash table. If the index is valid, it retrieves the corresponding entry. If the entry is marked as deleted, it updates the hash table to remove the reference to the deleted entry and returns None.
- Parameters:
b (int) – The index in the hash table to retrieve the entry from.
- Returns:
The entry at the specified index, or None if the index is out of bounds or if the entry is marked as deleted.
- Return type:
object
- leftbnd(pt)[source]#
Find the left boundary half-edge for a given point.
This function computes the appropriate half-edge that is to the left of the specified point. It utilizes a hash table to quickly locate the half-edge that is closest to the desired position based on the x-coordinate of the point. If the initial bucket derived from the point’s x-coordinate does not contain a valid half-edge, the function will search adjacent buckets until it finds one. Once a half-edge is located, it will traverse through the linked list of half-edges to find the correct one that lies to the left of the point.
- Parameters:
pt (Point) – A point object containing x and y coordinates.
- Returns:
The half-edge that is to the left of the given point.
- Return type:
HalfEdge
- class PriorityQueue(ymin, ymax, nsites)[source]#
Bases:
object- __len__()[source]#
Return the length of the object.
This method returns the count of items in the object, which is useful for determining how many elements are present. It is typically used to support the built-in len() function.
- Returns:
The number of items in the object.
- Return type:
int
- isEmpty()[source]#
Check if the object is empty.
This method determines whether the object contains any elements by checking the value of the count attribute. If the count is zero, the object is considered empty; otherwise, it is not.
- Returns:
True if the object is empty, False otherwise.
- Return type:
bool
- insert(he, site, offset)[source]#
Insert a new element into the data structure.
This function inserts a new element represented by he into the appropriate position in the data structure based on its value. It updates the ystar attribute of the element and links it to the next element in the list. The function also manages the count of elements in the structure.
- Parameters:
he (Element) – The element to be inserted, which contains a vertex and a y-coordinate.
site (Site) – The site object that provides the y-coordinate for the insertion.
offset (float) – The offset to be added to the y-coordinate of the site.
- Returns:
This function does not return a value.
- Return type:
None
- delete(he)[source]#
Delete a specified element from the data structure.
This function removes the specified element (he) from the linked list associated with the corresponding bucket in the hash table. It traverses the linked list until it finds the element to delete, updates the pointers to bypass the deleted element, and decrements the count of elements in the structure. If the element is found and deleted, its vertex is set to None to indicate that it is no longer valid.
- Parameters:
he (Element) – The element to be deleted from the data structure.
- getBucket(he)[source]#
Get the appropriate bucket index for a given value.
This function calculates the bucket index based on the provided value and the object’s parameters. It ensures that the bucket index is within the valid range, adjusting it if necessary. The calculation is based on the difference between a specified value and a minimum value, scaled by a delta value and the size of the hash table. The function also updates the minimum index if the calculated bucket is lower than the current minimum index.
- Parameters:
he – An object that contains the attribute ystar, which is used in the bucket calculation.
- Returns:
The calculated bucket index, constrained within the valid range.
- Return type:
int
- getMinPt()[source]#
Retrieve the minimum point from a hash table.
This function iterates through the hash table starting from the current minimum index and finds the next non-null entry. It then extracts the coordinates (x, y) of the vertex associated with that entry and returns it as a Site object.
- Returns:
An object representing the minimum point with x and y coordinates.
- Return type:
- popMinHalfedge()[source]#
Remove and return the minimum half-edge from the data structure.
This function retrieves the minimum half-edge from a hash table, updates the necessary pointers to maintain the integrity of the data structure, and decrements the count of half-edges. It effectively removes the minimum half-edge while ensuring that the next half-edge in the sequence is correctly linked.
- Returns:
The minimum half-edge that was removed from the data structure.
- Return type:
HalfEdge
- class SiteList(pointList)[source]#
Bases:
object- setSiteNumber(site)[source]#
Set the site number for a given site.
This function assigns a unique site number to the provided site object. It updates the site object’s ‘sitenum’ attribute with the current value of the instance’s private ‘__sitenum’ attribute and then increments the ‘__sitenum’ for the next site.
- Parameters:
site (object) – An object representing a site that has a ‘sitenum’ attribute.
- Returns:
This function does not return a value.
- Return type:
None
- class Iterator(lst)[source]#
Bases:
object- __iter__()[source]#
Return the iterator object itself.
This method is part of the iterator protocol. It allows an object to be iterable by returning the iterator object itself when the __iter__ method is called. This is typically used in conjunction with the __next__ method to iterate over the elements of the object.
- Returns:
The iterator object itself.
- Return type:
self
- next()[source]#
Retrieve the next item from a generator.
This function attempts to get the next value from the provided generator. It handles both Python 2 and Python 3 syntax for retrieving the next item. If the generator is exhausted, it returns None instead of raising an exception.
- Parameters:
this (object) – An object that contains a generator attribute.
- Returns:
The next item from the generator, or None if the generator is exhausted.
- Return type:
object
- iterator()[source]#
Create an iterator for the sites.
This function returns an iterator object that allows iteration over the collection of sites stored in the instance. It utilizes the SiteList.Iterator class to facilitate the iteration process.
- Returns:
An iterator for the sites in the SiteList.
- Return type:
- __iter__()[source]#
Iterate over the sites in the SiteList.
This method returns an iterator for the SiteList, allowing for traversal of the contained sites. It utilizes the internal Iterator class to manage the iteration process.
- Returns:
An iterator for the sites in the SiteList.
- Return type:
- __len__()[source]#
Return the number of sites.
This method returns the length of the internal list of sites. It is used to determine how many sites are currently stored in the object. The length is calculated using the built-in len() function on the __sites attribute.
- Returns:
The number of sites in the object.
- Return type:
int
- _getxmin()[source]#
Retrieve the minimum x-coordinate value.
This function accesses and returns the private attribute __xmin, which holds the minimum x-coordinate value for the object. It is typically used in contexts where the minimum x value is needed for calculations or comparisons.
- Returns:
The minimum x-coordinate value.
- Return type:
float
- _getymin()[source]#
Retrieve the minimum y-coordinate value.
This function returns the minimum y-coordinate value stored in the instance variable __ymin. It is typically used in contexts where the minimum y-value is needed for calculations or comparisons.
- Returns:
The minimum y-coordinate value.
- Return type:
float
- _getxmax()[source]#
Retrieve the maximum x value.
This function returns the maximum x value stored in the instance. It is a private method intended for internal use within the class and provides access to the __xmax attribute.
- Returns:
The maximum x value.
- Return type:
float
- _getymax()[source]#
Retrieve the maximum y-coordinate value.
This function accesses and returns the private attribute __ymax, which represents the maximum y-coordinate value stored in the instance.
- Returns:
The maximum y-coordinate value.
- Return type:
float
- _getextent()[source]#
Retrieve the extent of the object.
This function returns the current extent of the object, which is typically a representation of its boundaries or limits. The extent is stored as a private attribute and can be used for various purposes such as rendering, collision detection, or spatial analysis.
- Returns:
The extent of the object, which may be in a specific format depending on the implementation (e.g., a tuple, list, or custom object).
- computeVoronoiDiagram(points, xBuff=0, yBuff=0, polygonsOutput=False, formatOutput=False, closePoly=True)[source]#
Compute the Voronoi diagram for a set of points.
This function takes a list of point objects and computes the Voronoi diagram, which partitions the plane into regions based on the distance to the input points. The function allows for optional buffering of the bounding box and can return various formats of the output, including edges or polygons of the Voronoi diagram.
- Parameters:
points (list) – A list of point objects, each having ‘x’ and ‘y’ attributes.
xBuff (float?) – The expansion percentage of the bounding box in the x-direction. Defaults to 0.
yBuff (float?) – The expansion percentage of the bounding box in the y-direction. Defaults to 0.
polygonsOutput (bool?) – If True, returns polygons instead of edges. Defaults to False.
formatOutput (bool?) – If True, formats the output to include vertex coordinates. Defaults to False.
closePoly (bool?) – If True, closes the polygons by repeating the first point at the end. Defaults to True.
- Returns:
- list: A list of 2-tuples representing the edges of the Voronoi
diagram, where each tuple contains the x and y coordinates of the points. If formatOutput is True: - tuple: A list of 2-tuples for vertex coordinates and a list of edges indices.
- If polygonsOutput is True:
dict: A dictionary where keys are indices of input points and values
are n-tuples representing the vertices of each Voronoi polygon. If formatOutput is True: - tuple: A list of 2-tuples for vertex coordinates and a dictionary of polygon vertex indices.
- Return type:
If polygonsOutput is False
- formatEdgesOutput(edges)[source]#
Format edges output for a list of edges.
This function takes a list of edges, where each edge is represented as a tuple of points. It extracts unique points from the edges and creates a mapping of these points to their corresponding indices. The function then returns a list of unique points and a list of edges represented by their indices.
- Parameters:
edges (list) – A list of edges, where each edge is a tuple containing points.
- Returns:
- A tuple containing:
list: A list of unique points extracted from the edges.
list: A list of edges represented by their corresponding indices.
- Return type:
tuple
- formatPolygonsOutput(polygons)[source]#
Format the output of polygons into a standardized structure.
This function takes a dictionary of polygons, where each polygon is represented as a list of points. It extracts unique points from all polygons and creates an index mapping for these points. The output consists of a list of unique points and a dictionary that maps each polygon’s original indices to their corresponding indices in the unique points list.
- Parameters:
polygons (dict) – A dictionary where keys are polygon identifiers and values are lists of points (tuples) representing the vertices of the polygons.
- Returns:
- A tuple containing:
list: A list of unique points (tuples) extracted from the input
polygons. - dict: A dictionary mapping each polygon’s identifier to a list of indices corresponding to the unique points.
- Return type:
tuple
- computeDelaunayTriangulation(points)[source]#
Compute the Delaunay triangulation for a set of points.
This function takes a list of point objects, each of which must have ‘x’ and ‘y’ fields. It computes the Delaunay triangulation and returns a list of 3-tuples, where each tuple contains the indices of the points that form a Delaunay triangle. The triangulation is performed using the Voronoi diagram method.
- Parameters:
points (list) – A list of point objects with ‘x’ and ‘y’ attributes.
- Returns:
- A list of 3-tuples representing the indices of points that
form Delaunay triangles.
- Return type:
list