|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Khristianovsky 2:5020/400 22 Feb 2002 17:44:01
To : ZAB\
Subject : Re: Zapadinsky Anatoly : Hаправление обхода
--------------------------------------------------------------------------------
ZA> А какая сложность у этого сведения? Может лучше всё же найти самую
крайнюю
ZA> (по какой либо координате) вершину и рассмотреть произведение векторов с
ZA> началом в этой вершине и концами в соседних, получится линейная...
Я осуществлял не совсем сведение. А поиск такого вектора
относительно которого все остальный вершины лежат либо по часовой
стрелке либо против. Example:
Пусть есть полигон pt0,..., ptN; pt0 = ptN
Берем базовый вектор [pt0, pt1] смотрим направление поворота для [pt0, pt2]
и для [pt0, pt3].
Если оно различается, то базовым становится вектор [pt0, pt2]. Относительно
него проверяем
теперь уже [pt0, pt4] сравнивая результат с полученным ранее для [pt0, pt3]
и т.д.
Трудоемкость тоже линейная.
Хотя надо признать, что метод ориентированных площадей проще и
очевидней.
--- ifmail v.2.15dev5
* Origin: InfoTeCS Taganrog Telecom (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
