查找多邊形面積的高效算法

Question

我正在尋找最好的（高效算法來計算二維多邊形的面積（特別是對於三角形給定三點）。我在網上搜索並找到以下鏈接，但我仍然不確定它們在內存成本方面是否有效（因爲我的網格非常龐大）。 我想知道是否有任何C++技巧（我是C++中的新手）可以應用他們：

這裏是鏈接：

（計算器） How to determine if a point is in a 2D triangle?

http://www.softwareandfinance.com/Visual_CPP/Triangle_Area_Perimeter.html

值得一提的是，最終的目標是要找出一個點是否內（而不是在邊框）的多邊形。

感謝您的任何幫助。

Answer 1

Joachim Pileborg在評論中提出，該區域不是必需的，但這沒有必要：有一個高效的算法，它需要一箇中間值，恰好是2*Area。

但是，在這種情況下，問題實際上是輸入域：三角形的網格。這意味着幾乎每個頂點都有兩個三角形的邊界。這不像「點P位於邊E的左邊，所以它不是三角形T」。有一大組三角形T _我，其中一些位於左側，其中一些位於右側，一個直接位於給定邊緣的任一側。

鑑於這種複雜性，您應該預先處理網格。將其劃分爲一些可管理的塊，例如16x16，並注意它所在的每個三角形。任何點P都只在一個塊中，所以你需要測試1％的三角形（一個三角形可能位於多個塊中，但平均值很低）。

（您很少，如果需要做的只是一個單一的點對網的比賽，所以預處理是有道理的。雖然你在它預先計算面積。）