CODEWITHSUNDEEP
graphgeometrycomputational-geometry
dogrush
dogrush

Reputation: 43

how to obtain the closed polygons from the relative neighbor graph

There are many 2D points in the plane。 Firstly, I have obtained a graph by two approaches:

  1. perform Delaunay triangulation, then delete the longest edge for each triangle;

  2. obtain the relative neighbor graph by the code NGL: http://www.ngraph.org/

The result seems similar by the above two approaches. Results But now, I have a question. How to obtain all the polygons from the above relative neighbor graph? That is, these polygons will never include other edges inside. I want to obtain all the sub regions from the graph, so I may find all the polygons first.

Someone knows how to do it?

Upvotes: 4

Views: 569

Answers (1)

Darren Engwirda
Darren Engwirda

Reputation: 7015

First up, the two graphs you mention are actually distinct graph types:

  1. The Relative Neighbourhood Graph contains an edge ij in the absence of another vertex k satisfying dist(i,k) < dist(i,j) and dist(j,k) < dist(i,j).

  2. The Urquhart Graph is formed by removing the longest edge from each triangle in the Delaunay Triangulation, as you've mentioned.

While these graphs are often similar, and can be the same in some instances, they are in general distinct.

Your comments seem to indicate that you're indeed constructing the Urquhart Graph U from the Delaunay Triangulation T, and, as such, you can alter your edge removal algorithm to also construct the set of disjoint polygons while you build U.

Simply note that when removing an edge from the triangulation T you are also merging the two polygons adjacent to that edge. Initially, each internal edge will be adjacent to two triangles, but as the edge removal proceeds edges will become adjacent to more complex polygons.

An algorithm could proceed 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's own initial polygon
P <- mark each triangle as it's 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 a set of disjoint polygons as lists of triangles.

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

Hope this helps.

Upvotes: 2

Related Questions