forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Столкновение "точка - многоугольник" (http://forum.boolean.name/showthread.php?t=18101)

IgorOK 18.04.2013 00:06
Столкновение "точка - многоугольник"
 
Знает ли кто нибудь хорошие статьи на определение нахождения точки в многоугольнике?

SBJoker 18.04.2013 02:05
Ответ: Столкновение "точка - многоугольник"
 
в двух словах метод такой:
если луч проведенный через точку пересекает нечетное число сторон многоугольника - точка внутри этого многоугольника, иначе - снаружи.

IgorOK 18.04.2013 09:04
Ответ: Столкновение "точка - многоугольник"
 
А есть ли какие нибудь особенности трассировки луча? Т.е. его можно проводить произвольно?

SBJoker 18.04.2013 12:37
Ответ: Столкновение "точка - многоугольник"
 
Совершенно произвольно проводить, но с точки упрощения расчётов его можно провести параллельно одной из координатных осей

IgorOK 18.04.2013 13:51
Ответ: Столкновение "точка - многоугольник"
 
Цитата:
Сообщение от SBJoker (Сообщение 257282)
Совершенно произвольно проводить, но с точки упрощения расчётов его можно провести параллельно одной из координатных осей
Большое спасибо за помощь! :)

MiXaeL 18.04.2013 20:02
Ответ: Столкновение "точка - многоугольник"
 
Сейчас порисовал на бумажке, и мне кажется, есть хак.
Сумма расстояний от точки до вершин многоугольника внутри него всегда меньше периметра, а снаружи больше. Если у кому-то будет не лень проверить, было бы интересно узнать, так это или нет.
Для треугольника - тривиально.

Бред сказал, да =\. Внутри - всегда меньше, обратно - неверно. Легко проверить точкой на самой границе.

Randomize 19.04.2013 03:56
Ответ: Столкновение "точка - многоугольник"
 
http://geomalgorithms.com/a03-_inclusion.html


Часовой пояс GMT +4, время: 15:42.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Перевод: zCarot