在任意形狀中遍歷點

Question

我有一個包含（無縫）任意形狀（具體的陸地區域）的點multimap<int,int>的多重映射。我將如何迭代包含在任意形狀中的所有點？我知道multimap不足以確定內部點，因此我有一個額外的點，這是在形狀內部（以確定形狀的內部和外部）。

更多信息：由於multimap是一個已排序的容器，因此這些點將按x向排序。所有點都位於網格中，因爲我使用的是位圖。

Answer 1

1. 如果你的點距離比1個像素更遠，那麼按x座標排序的點不會很有幫助。對它們進行排序，使得應該連接的點彼此相鄰。

2. Draw lines between the points

3. 發現裏面並flood fill形狀的點，多數民衆贊成。如果您自己實現它，則需要遍歷該形狀內的每個像素。

Answer 2

一個測試點是否在形狀的內部/外部是想象一個射線從該點到已知在該形狀之外的點。計算光線穿過邊界的次數，如果這個數字是奇數，則該點在形狀內，如果它的點數超過形狀的話。請參閱ray casting algorithm for a point in polygon。

在你的情況下，最簡單的方法是拍攝與你測試點具有相同x值的垂直射線，(x0,y0)表示。讓(x0,y1)位於形狀的邊界框之外的某個點。只需使用相同的x值來計算multimap中的點數。如果它很奇怪，你就在裏面，如果它甚至在外面。

上面假定了一些關於形狀邊界的細節：包含形狀的完整邊界，因此如果形狀穿過邊緣上的圖像點的邊緣包含在多重貼圖中，也沒有兩個相鄰的積分(x,y)和(x,y+1)都不在多重映射中。