如何找到具有特定距離函數的Voronoi圖？

找到具有歐氏距離的Voronoi圖的算法相當多。但是，我還沒有找到任何其他距離函數的算法，例如曼哈頓距離（可能因爲沒有實際應用）。如何找到具有特定距離函數的Voronoi圖？

可以在Wikipedia見例如：
https://en.wikipedia.org/wiki/Voronoi_diagram#/media/File:Manhattan_Voronoi_Diagram.svg

曼哈頓Voronoi圖還包括多邊形（但非凸）的，所以我想類似Fortune's algorithm該算法可以被構建。然而，使用更復雜的距離函數，邊界不再是多邊形。將需要不同的數據結構和算法。

是否有任何算法找到具有特定距離函數的Voronoi圖（爲了簡單起見，在2D中）？

注：我不需要與像素作品的算法，這是非常簡單的，我需要的算法，它開創細胞的邊界。

注2 實際上我需要距離函數abs(dx)^3 + abs(dy)^3，但是，從理論上說，我很感興趣如何做一個讓其他距離函數的算法Voronoi圖。以下是如何使用abs(dx)^3 + abs(dy)^3的Voronoi。網站是連續的，它們的邊緣類似於圖形y=x^3（只是假設）。

來源

2015-12-15 Somnium

https://github.com/bobbysoon/TaxiVoronoi – Bytemain

如果你只對算法感興趣（不涉及代碼），這對於計算機科學SE來說可能是個好問題。有幾個問題，我發現[這裏]（http://cs.stackexchange.com/questions/43817/voronoi-diagrams-with-l%E2%88%9E-metric）和[這裏]（http：/ /cs.stackexchange.com/questions/34116/voronoi-diagram-algorithm-with-non-euclidean-metric），但不幸的是他們沒有算法。 – whrrgarbl

@whrrgarbl我對算法更感興趣，代碼太大，無法在SO上發佈。如果可能，我想自己編寫代碼。 – Somnium

最有可能的，你可以使用像素出租車沃羅諾伊並給每個多邊形不同的顏色。然後，您可以使用像素顏色測試來檢查邊界。

來源

2015-12-16 15:22:24 Bytemain

如何找到具有特定距離函數的Voronoi圖？

回答

相關問題