獲取多邊形內的點

Question

我有一個點是一個封閉的路徑來描述多邊形的列表，我怎樣才能得到一個點必須位於多邊形區域？ 我不知道凹多邊形的情況，但所有的點的平均值位於多邊形的內部，當案例來凸多邊形。

Answer 1

1. 之所以選擇第一個連續3個百分點的多邊形
2. 檢查，如果第一個和第三個點之間的中間點是多邊形
3. 如果是內部的：你找到你的觀點
4. 如果沒有：放下第一個點，加上下一個點，然後轉到2.

保證結束，因爲每個嚴格閉合的多邊形至少有一個三角形，即完整的多邊形的一部分。

對於第2步。搜索SO，這已被多次回答。

Answer 2

https://mathoverflow.net/questions/56655/get-a-point-inside-a-polygon

鏈接：

http://www.exaflop.org/docs/cgafaq/cga2.html#Subject%202.06:%20How%20do%20I%20find%20a%20single%20point%20inside%20a%20simple%20polygon

它說，部分：

Given a simple polygon, find some point inside it. Here is a method based on the proof that 
there exists an internal diagonal, in [O'Rourke, 13-14]. The idea is that the midpoint of  
a diagonal is interior to the polygon. 

1. Identify a convex vertex v; let its adjacent vertices be a and b. 
2. For each other vertex q do: 
2a. If q is inside avb, compute distance to v (orthogonal to ab). 
2b. Save point q if distance is a new min. 
3. If no point is inside, return midpoint of ab, or centroid of avb. 
4. Else if some point inside, qv is internal: return its midpoint.