具有固定最大邊緣長度的平面圖

我想在2D空間中生成隨機點，這些點將成爲平面圖的節點（使用Gabriel graph算法或RNG構建）。具有固定最大邊緣長度的平面圖

我寫了java代碼來做到這一點，但我有兩個難解決的問題。

1）我需要的是，圖的所有邊緣不大於給定的閾值

2）後，我想知道圖表的面更長，面部是由邊緣連接的節點的集合。一張臉不包含其他節點。在下面的圖片中，人臉是由標籤（F1，F2 ...）簽署的

如何做到這兩件事？一些算法？有一些方法已經知道了嗎？

下面有圖的一個例子，我必須創建

http://imageshack.us/photo/my-images/688/immagineps.png/

來源

2011-05-13 tulkas85

你可以進一步定義'臉部'嗎？從圖片看，它像一組點中的凸包。 – dfb 2011-05-13 20:44:21

一張臉是由邊連接的節點的集合。一張臉不包含其他節點。在圖像中，人臉由標籤（F1，F2 ...）簽名。可能的人臉必須是凸的，這個屬性可能是由Gabriel圖的構造造成的，但我不確定。 – tulkas85 2011-05-14 13:55:51

如果你可以容忍的點數一些變化，那麼你可以修改你的加布裏埃爾圖形算法是增量式的（大部分努力會讓你的Delaunay算法增加），然後每當邊緣太長時，在圓上插入一個隨機點作爲直徑。
平面圖的最方便的數據結構是以邊爲中心的：例如，doubly-connected edge list和quad-edge表示法。如果你還沒有在Delaunay步驟中使用這種類型的數據結構（並且我無法想象你爲什麼不這樣做），那麼可以按角度對每個頂點的傳出連接進行排序。從那裏開始，很容易實現一個功能，該功能佔用半邊並以逆時針的順序返回同一面上的下一個半邊。現在遍歷所有的半邊，並且對於每個尚未訪問過的半邊，遍歷該面，直到返回到開始的位置。將內迭代中的所有半邊標記爲一個面。

來源

2011-05-13 21:40:04 qwerty

我解決了第一步，在我的代碼上幾乎沒有任何變化，但我沒有使用Delaunay創建Gabriel Graph。你能解釋我怎麼能找到共享同一點的邊的逆時針順序？我的數據結構由Vector的邊組成，每個邊都包含兩個點。如果共享一個點，兩個邊相鏈接。 – tulkas85 2011-05-14 13:58:00

此解決方案的+1。 @ tulkas85，在大多數語言中，您可以使用'atan2（）'來確定矢量相對於X軸的角度。然後按角度對所有邊進行排序。 – brainjam 2011-05-14 15:59:33

@ tulkas85「但我不使用Delaunay創建Gabriel圖」 - >如何在沒有Delaunay的情況下創建圖？我確實使用德勞內，但寧願不這樣做。即使我不確定我的圖表是否正確。（a，b）是gabriel對，如果d^2（a，b）<= d^2（a，c）+ d^2（b，c）'，則通過檢查條件創建它一個德勞內三角形 – embert 2014-01-19 11:41:00

具有固定最大邊緣長度的平面圖

回答

相關問題