How to get closed polygons from the graph of relative neighbors

Question

There are many two-dimensional points in the plane. Firstly, I got the schedule in two ways:

• Triangulate Delaunay, then remove the longest edge for each triangle;

• get relative neighbor graph by NGL code: http://www.ngraph.org/

The result is similar to the above two approaches. But now I have a question. How to get all the polygons from the above graph of the neighboring neighborhood? That is, these polygons will never include other edges inside. I want to get all the subregions from the graph, so first I can find all the polygons.

Does anyone know how to do this?

Answer 1

First of all, the two graphs you mentioned are really different types of graphs:

• The relative neighborhood graph contains the edge ij in the absence of another vertex k satisfying dist(i,k) < dist(i,j) and dist(j,k) < dist(i,j) .

• Urquhart Graph is formed by removing the longest edge from each triangle in the Delaunay triangulation , as you already mentioned.

Although these graphs are often similar and may be the same in some cases, they are generally different.

Your comments indicate that you are actually plotting Urquhart U from the Delaunay T triangulation, and so you can change the edge removal algorithm to also build many disjoint polygons while you build U

Just notice that when you remove the edge from the triangulation T you also merge the two polygons adjacent to this edge. Initially, each inner edge will be adjacent to two triangles, but as the edge moves away, the edges of the edge become adjacent to more complex polygons.

The algorithm can act as follows:

 // Data-structures: // S: a set of polygons - each polygon is a list of triangles // P: a pointer to the parent polygon for each triangle // Triangulation should give O(1) access to edge-adjacent triangles S <- push each triangle as it own initial polygon P <- mark each triangle as it own initial parent while (removing edges) ij <- edge to be removed from U ti <- 1st tria adjacent to edge ij tj <- 2nd tria adjacent to edge ij pi <- P(ti); // poly containing ti pj <- P(tj); // poly containing tj // merge pi and pj into single poly S(pi) <- S(pj) // push triangles from pj onto pi P(S(pj)) = pi // mark pi as parent for trias // from pj S(pj) <- 0 // poly pj is now null endwhile 

The result will be many disjoint polygons in the form of lists of triangles.

The edges forming the boundaries of the polygonal regions will be those edges that appear in the graph U - these are edges adjacent to triangles in different polygons.

Hope this helps.