Вхождение точки в полигон

← →
Chuck Loon (2006-08-30 12:21) [0]

Кто знает как определить что точка находится внутри или на границе некоего полигона?

← →
Сергей М. © (2006-08-30 13:05) [1]

см. PtInRegion()

← →
Vovan#1 (2006-08-30 19:35) [2]

Из точки выпускай произвольный луч (но не пересекающий вершины). Если он пересекает чётное количество сторон, то значит - вне полигона, если нечётное - то внутри.

← →
Ketmar © (2006-08-30 19:40) [3]

> [2] Vovan#1 (30.08.06 19:35)
это не решает задачи "находится на границе".

← →
Vovan#1 (2006-08-30 20:59) [4]

>это не решает задачи "находится на границе".

В общем случае это не решает и первой задачи - луч может пройти вообще мимо полигона.

← →
palva © (2006-08-30 21:19) [5]

> луч может пройти вообще мимо полигона.
Значит, 0 - четное число.

← →
Vovan#1 (2006-08-30 21:31) [6]

>Значит, 0 - четное число.

Да, не учёл и поэтому ошибся. В общем хотел выразить мысль, что идея проста в формулировке, но имеет ряд сложностей, как, например, работа с вершинами. От готового - далеко, но куда двигаться - ясно.

← →
Ketmar © (2006-08-31 00:04) [7]

> [6] Vovan#1 (30.08.06 21:31)
вершины -- это частный случай "лёжки на ребре". %-) в винде проще создать регион. тем более, что с математикаой даже на таком уровне дружит далеко не все.

← →
DiamondShark © (2006-08-31 00:14) [8]

С лучом там другая проблема: его бы так направить, чтоб вдоль ребра не пошёл ;) А то можно количество пересечений бесконечным насчитать.

Впрочем, можно сначала проверять на принадлежность точки рёбрам, а потом уже, если не принадлежит, смело луч от-балды направлять.

> [8] DiamondShark © (31.08.06 00:14)
ну да. пустить горизонтальный луч потом, например. тогда легко отсекаются горизонтальные же рёбра, которые дают бесконечное множесто решений (еслине ошибаюсь в количестве %-)

> DiamondShark © (31.08.06 00:14) [8]
>
> Впрочем, можно сначала проверять на принадлежность точки
> рёбрам,

Имхо, вообще не возможно!
Для вещественного числа, а координата произвольной точки границы полигона ни чем иным и быть не может, не может быть "точного" сравнения!

> [10] Германн © (31.08.06 01:30)
вот ужас-то. а как же тогда всякие рассчёты пишут? надо срочно сообщить народу, что вещественные числа сравнивать бессмысленно. а сравнения с "допустимостью" -- это бредятина и права на жизнь не имеют.

Вхождение точки в полигон Найти похожие ветки