包含區域之間的內部關係算法

Question

我有兩個區域由它們包含的點定義。

這是一個區域是點{X，Y}的列表。

每個區域都連接在一起。

一個區域在另一個區域內。

我需要一個算法來確定裏面的區域。

有人可以給我一個鏈接到算法來解決這個問題嗎？

如果有人知道解決這個問題的opencv函數是非常受歡迎的。

在此先感謝。

Answer 1

只要外部形狀的點都不在內部形狀的點內，就可以通過點定位算法在線性時間內完成。從兩組中較大的一組中選擇一個點，並通過光線投射檢查它是否在另一個區域內。見Point in Polygon problem。多種語言的全面實現在這裏：ray casting implementations。