Для точечных координат, как я могу определить, находится ли он в произвольной форме?
Форма определяется массивом точек, я не знаю, где фигура "закрыта", той части, в которой мне действительно нужна помощь, заключается в том, чтобы определить, где форма закрыта.
Здесь изображение, чтобы проиллюстрировать, что я имею в виду, немного лучше:
Самый простой способ сделать это - бросить луч с этой точки и подсчитать, сколько раз он пересекает границу. Если он нечетен, точка находится внутри, даже точка снаружи.
Wiki: http://en.wikipedia.org/wiki/Point_in_polygon
Обратите внимание, что это работает только для форм многообразия.
Если вы хотите определить, находится ли точка P в произвольной форме, я бы просто запускал заливку заливки, начиная с P. Если ваша заливка заливки оставляет предопределенный ограничивающий прямоугольник, вы находитесь за пределами формы. В противном случае, если заполнение заливки завершается, вы находитесь в пределах формы:)
Я считаю, что этот алгоритм O (N ^ 2), где N - число точек, так как максимальная площадь пропорциональна N ^ 2.
Википедия: Flood Fill
Собственно, если вам задан массив точек, вы можете проверить близость формы следующим образом:
Рассмотрим пары точек P[i] и P[i+1], заданные в массиве, - они образуют некоторый сегмент границы вашей фигуры. Что нужно проверить, если существуют два таких сегмента, которые пересекаются, что можно проверить в O(N^2) времени (просто проверяя все возможные пары таких сегментов). Если существует пересечение, это означает, что ваша форма закрыта.
Примечание: вы должны быть внимательны, чтобы не забыть проверить сегмент P[0],P[n-1] либо (то есть первую и последнюю точки в массиве).