|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5017/13.40 29 May 2001 07:43:10
To : Alexander Nikitin
Subject : Как определить направление обхода ?!?
--------------------------------------------------------------------------------
Hедавно, Суб Май 19 2001 в 15:31, некто Alexander Nikitin
писал pbas@spb.cityline.ru по поводy Re: Как определить направление обхода ?!?
:
>> Hаходим самую левую точку. Если мы пришли в неё снизу или ушли из
>> неё наверх, то многоугольник обходится по часовой стрелке. Если мы
>> пришли в неё сверху или ушли вниз, то против.
AN> Откуда это ты взял такие рассуждения? Мы можем пройти ее снизу и уйти
AN> вниз. Многоугольник-то может быть не выпуклым :-) Вообще-то, совсем не
AN> хочется думать над задачей, ленивый я, но вариант (может и не лучший)
AN> такой: найти площадь многоульника (многоульник без самопересечений,
AN> надеюсь). А по знаку (-,+) значение площади можешь определить
AN> направление обхода. PS: напомню: S=1/2(X1Y2-X2Y1 + X2Y3-X3Y2 + ... +
AN> XnY1-X1Yn).
Очевидно, что в исходном виде алгоритм даже недостоин рассмотрения, но я в
таких случаях предполагаю, что человек просто не сумел сформулировать свою
мысль, а она, как мне кажется, состоит в следующем:
1. Hайти самую левую точку многоугольника.
2. Определить направление обхода по двум отрезкам, выходящим из этой точки.
Алгоритм, как и твой, имеет сложность O(N), только, возможно, одно сравнение
будет быстрее двух умножений.
Hе прощаюсь
Sergey
--- --- Да будет свет ! ---
* Origin: Sergiev Posad <Ferma> Sergey Andrianov (2:5017/13.40)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Как определить направление обхода ?!?