Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

SergeySA © (2004-02-16 10:43:00)
Излазил интернет в поисках алгоритма определения принадлежности точти произвольному (не только выпуклуму) многоугольнику.
Может у кого завалялся?

CyberStorm (2004-03-04 20:31:00) [1]
В какие дебри полезли господа :) все гораздо проще:
проводим лучь вправо от точки и считаем пересечения со сторонами многоугольника, если нечетное количество пересечений то точка внутри, если четное или ноль - то снаружи - функция в 10-15 строчек
А функцию PtinRegion я привел потому что это самый простой вариант, не требующих особых затрат в программировании, хотя и медленно работающий, для скорости можно перед вызовом проверять к примеру попадания точек в описывающий прямоугольник

novice_ (2004-03-04 10:04:00) [2]
попробуй посчитать площадь треугольников которые получаются если соединить точки с вершинами полигона, например взять треугольный полигон и поместить в него точку, дальше провести прямые от точки к его вершинам, получатся три треуголника, дальше считаешь площадь каждого треугольника и сравниваешь полученное с площадью "оригинального" полигона. Если площади равны то точка принадлежит полигону, если нет ... соответственно не принадлежит

John (2004-03-01 15:02:00) [3]

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

CyberStorm (2004-02-20 18:05:00) [4]
В GDI есть стандартная функция PtInRegion для определения принадлежности точки заданной области или вернее заданному региону. Функция универсальная, при помощи ее можно определить принадлежность точик не только многоугольнику, но и эллипсу

Serrrrg (2004-02-19 16:25:00) [5]
http://algolist.manual.ru/maths/geom/belong/poly2d.php

SergeySA (2004-02-17 09:56:00) [6]
Ну, про методы я знаю, а вот алгоритм бы, чтоб долго не мучаться... с неизвестным результатом....

MBo (2004-02-16 12:39:00) [7]
З.Ы.
Winding имеет смысл только для самопересекающихся многоугольников

MBo (2004-02-16 12:07:00) [8]
Луч из этой точки проводишь (для упрощения вычислений - по оси X, например), и считаешь количество пересечений со сторонами.
Если нечетное - внутри.
Есть еще winding-метод - см. описание SetPolyFillMode

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »