Определение того, какие многоугольники точка находится в пределах от большого набора полигонов

Question

Say У меня есть 2D плоскость, покрытую многоугольников (идентифицированных как массив вершин), аналогично:

Допустим, I также имеют точку с координатами на этой плоскости, какой самый простой способ вернуть какой из полигонов находится точка?

Хотя в этом примере перечислены 4 многоугольника, было бы просто запустить check on each polygon to see if the point is within it, но я создаю систему, которая в настоящее время имеет около 150 полигонов и может распространяться до тысячи, поэтому это может стать очень медленным.

Итак, есть ли какие-либо решения для этого, которые не требуют повторения всех доступных полигонов и проверки наличия точки?

Answer 1

Вы можете использовать kd-дерево или r-дерево. Это может уменьшить пространство поиска. Вы также можете найти квадрант. Вы можете выбрать размер квадрата, чтобы соответствовать многоугольникам и минимизировать перекрывающиеся ограничивающие прямоугольники.