Принадлежит ли точка области (полигону)

← →
SergeySA (2004-02-16 10:43) [0]

Излазил интернет в поисках алгоритма определения принадлежности точти произвольному (не только выпуклуму) многоугольнику.
Может у кого завалялся?

← →
MBo © (2004-02-16 12:07) [1]

Луч из этой точки проводишь (для упрощения вычислений - по оси X, например), и считаешь количество пересечений со сторонами.
Если нечетное - внутри.
Есть еще winding-метод - см. описание SetPolyFillMode

← →
MBo © (2004-02-16 12:39) [2]

З.Ы.
Winding имеет смысл только для самопересекающихся многоугольников

← →
SergeySA (2004-02-17 09:56) [3]

Ну, про методы я знаю, а вот алгоритм бы, чтоб долго не мучаться... с неизвестным результатом....

← →
Serrrrg (2004-02-19 16:25) [4]

http://algolist.manual.ru/maths/geom/belong/poly2d.php

← →
CyberStorm (2004-02-20 18:05) [5]

В GDI есть стандартная функция PtInRegion для определения принадлежности точки заданной области или вернее заданному региону. Функция универсальная, при помощи ее можно определить принадлежность точик не только многоугольнику, но и эллипсу

← →
John (2004-03-01 15:02) [6]

> В GDI есть стандартная функция PtInRegion...
very slow function

← →
novice_ (2004-03-04 10:04) [7]

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

← →
CyberStorm (2004-03-04 20:31) [8]

В какие дебри полезли господа :) все гораздо проще:
проводим лучь вправо от точки и считаем пересечения со сторонами многоугольника, если нечетное количество пересечений то точка внутри, если четное или ноль - то снаружи - функция в 10-15 строчек
А функцию PtinRegion я привел потому что это самый простой вариант, не требующих особых затрат в программировании, хотя и медленно работающий, для скорости можно перед вызовом проверять к примеру попадания точек в описывающий прямоугольник

Принадлежит ли точка области (полигону) Найти похожие ветки