矩形約束沒有內

Question

邊緣我使用三角測量庫來進行一些大的邊界內的矩形集合的約束Delaunay三角。該算法返回所有邊，但也會在定義約束的矩形內添加邊。

我希望能夠創建一個沒有任何約束的矩形內的邊界（除了大邊界之外），但在給予我的三角剖分中移除這些邊需要更長的時間至少比O（nlog（n））時間要短，這對我所需要的並不好。

什麼我問的是，有沒有快速的方法來獲得CDT保持邊緣從一些多邊形中出現？我想要矩形是空的邊緣，但我不知道如何快速做到這一點。

如果這有幫助，我使用的庫是Marcello Kallmann的TriPath，它是用C++編寫的（http://graphics.ucmerced.edu/software/tripath/）。我的應用程序是在Java中，我正在使用JNI。

編輯：根據要求，這裏有一些圖像來幫助你想象我想描述什麼。這個CDT是由黑線構成的。如您所見，每個約束邊是矩形的一部分。藍線是無約束的Delaunay邊緣。我試圖從黑色約束矩形中刪除任何藍色無約束Delaunay邊。

Answer 1

如果約束矩形不能重疊或互相牽制，我建議把一個稍小的矩形每個原始矩形的內部。內部矩形和原始矩形之間的間隙應該足夠小，以便在不與較小的矩形相交的情況下，沒有不受約束的邊緣可能適合原始矩形內部。然後，在完成三角測量後，刪除與這些較小矩形的任何頂點相鄰的每條邊。這樣你就可以找出是否應該在O（1）時間內刪除一個邊緣，所以整個過程將採用O（E）。選擇一個足夠小的差距

的方法之一是評估不小長方形的三角測量，發現最小長度的邊緣，走，比方說，該長度爲缺口的1/3。