如何從相對相鄰圖表獲得閉合多邊形

Question

有在平面許多2D點 首先，我已通過兩種方法獲得的曲線圖：

1. 執行Delaunay三角網，然後刪除該最長每個三角形的邊緣;

2. 由代碼NGL獲得相對相鄰圖表：http://www.ngraph.org/

結果似乎由上述兩種方法類似。 但現在，我有一個問題。如何從上述相對鄰居圖中獲取所有多邊形？ 也就是說，這些多邊形永遠不會包含其他邊緣。 我想從圖中獲取所有的子區域，所以我可以先找到所有的多邊形。

有人知道該怎麼做嗎？

Answer 1

先上去，你所提到的兩個圖實際上是不同的圖形類型：

1. 的Relative Neighbourhood Graph包含在沒有另一個頂點k滿足dist(i,k) < dist(i,j)和dist(j,k) < dist(i,j)的邊緣ij。

2. Urquhart Graph是通過從Delaunay Triangulation中的每個三角形中移除最長邊緣而形成的，如您所述。

雖然這些圖通常是相似的，並且在某些情況下可能是相同的，但它們通常是不同的。

您的意見似乎表明，你確實是從Delaunay三角T構建厄克特圖U，並且，正因爲如此，你可以改變你的邊緣去除算法，當你建立U也構建一套不相交的多邊形。

只需注意，當從三角測量中去除邊緣時，您還將合併與該邊緣相鄰的兩個多邊形。最初，每個內部邊緣將與兩個三角形相鄰，但隨着邊緣去除的進行，邊緣將變得與更復雜的多邊形相鄰。

的算法可以進行如下操作：

// 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 

結果將是一組不相交的多邊形爲三角形的列表。

形成多邊形區域邊界的邊將是那些出現在圖中的邊U - 這些邊是與不同多邊形中的三角形相鄰的邊。

希望這會有所幫助。