определить, находится ли точка внутри произвольной формы?

Question

Учитывая координаты точки, как я могу определить, находится ли она в произвольной форме?

Форма определяется массивом точек, я не знаю, где фигура «закрыта», частьМне действительно нужна помощь, чтобы понять, где фигура закрыта.

Вот изображение, чтобы проиллюстрировать, что я имею в виду немного лучше:

Answer 1

Самый простой способ сделать это - отвести луч из этой точки и посчитать, сколько раз он пересекает границу.Если это нечетно, точка находится внутри, даже точка находится снаружи.

Wiki: http://en.wikipedia.org/wiki/Point_in_polygon

Обратите внимание, что это работает только для многообразных форм.

Answer 2

Если вы хотите определить, находится ли точка P в произвольной форме, я бы просто заполнил заливку, начиная с P. Если ваша заливка покидает заранее определенную ограничивающую рамку, вы находитесь за пределами фигуры. В противном случае, если заливка завершится, вы окажетесь в форме:)

Я полагаю, что это алгоритм O (N ^ 2), где N - количество точек, поскольку максимальная площадь пропорциональна N ^ 2.

Википедия: Наводнение

Answer 3

На самом деле, если вам дан массив точек, вы можете проверить близость формы следующим образом:
Рассмотрим пары точек P[i] и P[i+1], заданные в массиве - они образуют некоторый отрезок границы вашей фигуры. Вам нужно проверить, существуют ли два таких пересекающихся сегмента, которые можно проверить за O(N^2) время (просто проверяя все возможные пары таких сегментов). Если существует пересечение, это означает, что ваша фигура закрыта.
Примечание: вы должны быть внимательны, чтобы не забыть проверить сегмент P[0],P[n-1] (то есть первая и последняя точки в массиве).