我需要圍繞凹形（非凸）內部多邊形生成Voronoi diagram。我在網上尋找方法，但我一直無法弄清楚如何做到這一點。基本上，我生成點的凸包，計算雙點，並建立這些點之間的邊緣網絡。但是，當遇到內部多邊形的邊緣時，它必須看起來像形狀的邊緣，就像凸包。因此，通過這樣做並剪切邊界處的所有邊緣，我最終應該得到一個Voronoi圖，該邊框對於內部多邊形的邊界具有良好的邊緣，並且內部多邊形的兩側都沒有任何單元格。計算多邊形周圍的Voronoi
讓我給你舉個例子：
的問題，這是細胞穿越內多邊形邊緣，存在小區結構和多邊形之間沒有視覺關係。
有沒有人知道如何解決這個問題？有沒有一些算法已經做到這一點，或者接近我想要達到的目標？
非常感謝您的任何輸入！
您可能可以構建一個符合德勞內三角剖分（即包含多邊形邊緣作爲約束的三角剖分），然後形成Voronoi圖作爲對偶。符合的三角測量將確保三角測量中的邊緣與約束邊緣相交 - 所有約束邊緣都將是三角測量中的邊緣。
看看三角形包here，作爲這種類型的方法的參考。根據我的經驗，這是一個快速而強大的庫，儘管它的編寫方式是c而不是java。
我不確定在這個階段我的理解是如何在你的圖中生成點（Voronoi中心）。如果您實際上想要在多邊形域中進行網格生成，則可能需要考慮其他方法，但三角形包支持（符合）Delaunay細化網格生成。
編輯：它看起來像你也可以直接形成一般線段Voronoi圖，檢查出VRONI庫，here。解決你的評論 - 我不確定你總是可以期待有一個統一的Voronoi圖，它也符合一般的多邊形邊界。我預計多邊形邊界的形狀會在邊界Voronoi單元上施加最大維數。
希望這會有所幫助。
Darren，我使用Poisson磁盤採樣器（http://devmag.org.za/2009/05/03/poisson-disk-sampling/）生成Voronoi中心以生成voronoi單元尺寸相對相等。接下來，我移除距離內部多邊形太近的點以減少僞像。 – Alex
我認爲Triangle能夠幫助我。如果我是對的，我應該生成一個形狀的三角形網格，然後使用該網格，生成雙點並從那裏構建我的Voronoi？ – Alex
@Alex：是的 - 那正是我想的。儘管如此，我認爲你仍然必須小心謹慎。在某些情況下，強制三角測量符合一組約束邊可以局部犧牲Delaunay準則 - 可能導致帶有外部中心的邊界三角形（Voronoi頂點）。如果你允許有足夠的邊界細化，我認爲有可能得到一個符合真正的Delaunay三角剖分，儘管我需要考慮這個有點難... –
很明顯，你需要生成你的Voronoi圖來約束更大的多邊形。雖然您將它稱爲多邊形，但我注意到您的示例圖具有基於樣條線的邊。現在讓我們忘記。
你想要做什麼是確保你開始與具有相當的長度相等邊緣的含多邊形（無論是通過您或從另一個源產生的）;方差因素會使這看起來更自然。我可能會去10-20％的差異。
現在，您已經將包含多邊形的線劃分爲長度大致相等的線段，您可以從中開始生成Voronoi圖。對於您的容器上的每個邊緣：
隨着您逐漸生成每個點，您應該開始看到該算法以徑向方式細分凹形容器的每個凸面「構成區域」。
您可能想知道該列表是什麼。很顯然，你還沒有完成，你只產生了你想要的總Voronoi鑲嵌的一小部分。一旦創建了凹面空間的這些「邊界」單元，就不希望新邊界單元比邊界單元更接近邊界，只需要它們在該區域內。通過維護邊界單元源點的列表，您可以確保您創建的任何其他點位於的區域內。這有點像拿一個內部閔可夫斯基和來確保你有一個緩衝區。現在你可以在這個派生的凹空間中隨機化剩下的細胞，直到完成。如果任何「通道」區域太窄，那麼這個派生空間的邊界將會重疊，你將會得到一個非簡單的多邊形，並且你將會得到一個非簡單的多邊形。可能會發現自己在錯誤的地方放置點，儘管你付出了努力，解決方法是確保你的最大放置距離不會超過最小通道寬度的一半......或者使用其他幾何方法，包括Minkowski總結作爲一種可能性，以確保你不會結尾退化衍生多邊形。很可能你會以多面體結束，即碎片。）
我還沒有應用此方法，但儘管肯定會出現一些錯誤，我認爲他的一般想法會讓你開始朝正確的方向發展。
查找一個文件名爲：
通過柯克帕特里克，大衛摹，寫於1979年
這裏的 「連續骨架的高效計算」 是抽象：
的O（n lgn）算法用於構造任意n線多邊形圖形的骨架 。該算法基於用於構建廣義Voronoi 圖的O（n lgn）算法（我們的泛化用僅限於在端點處相交的線段組 來替換點集）。通用的Voronoi圖算法採用線性時間算法對兩個任意（標準）Voronoi圖進行合併。
「線段集被約束爲僅在終點相交」是你所描述的凹多邊形。
+1對於可視化 – Johan