多邊形算法中的點，當測試點位於多邊形邊上時返回true

我已經實現了基於http://alienryderflex.com/polygon/的點中多邊形算法。多邊形算法中的點，當測試點位於多邊形邊上時返回true

它工作正常，但是，因爲它在文章中說：

如果測試點在多邊形的邊界，該算法將提供不可預知的結果

原來我當測試點位於多邊形的邊界/邊（以及頂點）時，需要算法返回true。

有兩種：

另一種算法，這將幫助我。或
一種方法來修改這個算法，得到我想要的東西（例如，通過運行算法之前擴大多邊形一點點）

2016-03-04 James Bateson

該算法適用於浮點數，所以通常「邊上」的概念比看起來更棘手。請參閱[每個計算機科學家應瞭解的浮點算術知識]（https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html）和[幾何學中的健壯性問題的課堂示例計算]（https://people.mpi-inf.mpg.de/~mehlhorn/ftp/classroomExamplesNonrobustness.pdf）。 –

無論如何，您可以對您關心的情況進行預檢。即如果點在多邊形的邊的ε內，則返回true。如果你的座標是整數，那麼你甚至可以用epsilon = 0來做到這一點。但即使對於多邊形之外的距離爲epsilon的點，該算法也可能返回true，因爲它可能適用於浮點數 –

擴大多邊形位是一個選項，但是這可能會非常棘手與凹多邊形。

我的建議是將點轉移到不同的方向（上/下/左/右）一小部分，然後對每個這些移動點進行計算。如果至少有一個移動點被確定爲內部，那麼將其計爲內部。

另一種選擇是讓交叉點的計數行在不同的方向上運行，而不僅僅是水平方向。

但是這可能不值得，因爲，正如您的鏈接文章所述：「這通常不是一個問題，因爲無論如何多邊形的邊緣是無限薄的，並且點落在邊緣上可以不管怎樣都不會影響多邊形的外觀。「

來源

2016-03-04 19:48:05

多邊形算法中的點，當測試點位於多邊形邊上時返回true

回答

相關問題