確定一組點的「內部域」

Question

我有一組（x，y）點，我想從這些點插入這組點中的任何點「內部」的值。 （圖中的黃色區域）。

的問題是，我還沒有找到什麼好的辦法：

1. 找到這將是我的內插點的邊界（綠線）
2. 測試，如果多邊形點在多邊形內或不在。我發現了Point in Polygon算法，但我不確定是否在某個範圍內考慮了所有點，並且測試它們是否屬於多邊形是個好主意。我希望找到一種讓我測試比（max（x）-min（x））*（max（y）-min（y））少的點數的方法，理想的方法是知道哪些點做我的迭代。

編輯：在第二部分我重複了圖像中的所有點（像素），我想要做的只是迭代黃色字段中的點。

您是否有鉛？

Ps：我用C++編寫，如果它有任何幫助。

Answer 1

您正在查看的綠線被稱爲點集合中的convex hull並且有many good, efficient algorithms for computing it。其中最好的時間運行在O（n log h），其中h是船體上的點數，n是點的總數。作爲一個完全無恥的自我推廣，我有我的個人網站上提供的a C++ implementation of one of these algorithms。

至於你的第二個問題 - 一旦你有凸包，很容易確定哪些點完全位於多邊形內部，而不是在船體上。只需製作所有點的散列表，然後遍歷凸包並移除包含在船體中的所有點。散列表中剩餘的是包含在多邊形中但不在邊界上的一組點。

希望這會有所幫助！