|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry Kalinin 2:5009/5.43 28 Apr 2001 11:04:56
To : Gleb Belyakov
Subject : Re: Точка внутри полигона.
--------------------------------------------------------------------------------
18 Май 01 06:19, Gleb Belyakov -> Dmitry Kalinin:
GB> ЫЫЫЫ OS/2 М№ello, Dmitry!
GB> Thursday April 19 2001 14:49, you wrote to me:
DK>> Есть два основных способа, узнать принадлженость точки
DK>> контуру:
GB> Ты пpедлагаешь пеpебиpать все точки и для каждой пpовеpять лежит
GB> ли она внутpи? Можно, но некpасиво. :( Или ты плохо пpичитал исходное
GB> письмо?
Пардон, вопрос не так понял. Можно эту задачу решить так. Идея как и при
закраске контура.
Пусть контур идет так.
4 /\1 2/\3
-=-.--.--.--.---- <<- любая скан-линия по Y
/ \/ \
/ \ 4,1,2,3 - точки пересечения скан-линии с ребрами конутра
| | Далее сортируем координаты точек 4,1,2,3 по возврастанияпо
| | X и группируем точки парами (4-1) и (2-3)
|_____________|
Каждая такая пара формирует отрезок, лежащий внутри контура. Выбери любой X из
любого отрезка, это и будет решением задачи.
Dmitry
--- 0f 0f 0e 0e 0e 0e 0c 0c 0a 09 09 06 03 00 00 00 ДВБВДБДДВДДДДДБДДДДД
* Origin: bESt reGUARdS (2:5009/5.43)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
