ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Tarasevich                    2:5020/400     31 Oct 2001  21:48:41
 To : Alexander Kothubievski
 Subject : Re: КАК ОПРЕДЕЛИТЬ HАПРАВЛЕHИЕ ОБХОДА ?????????
 -------------------------------------------------------------------------------- 
 

 Alexander Kothubievski wrote:
 
 > ...
 
 Если в
 
 > процессе обхода знак векторного произведения меняется то значит обходится не
 > выпуклый контур . А для не выпуклого контура понятие направления обхода ( по
 > часовой стрелке или против) теряет смысл .
 > ...
 
 Hет не теряет. Для самопересекающегося - теряет, для остальных - имеет
 прекрасный смысл, независимл от того, выпуклый контур или нет.
 
 Векторное произведение - правильный ответ. Hадо найти нижнюю правую
 точку полигона и вычислить векторное произведение соседних ребер. Знак
 векторного произведения однозначно даст направление обхода.
 
 Другой способ - вычислить ориентированную площадь полигона. Оба способа
 имеют сложность O(n), но в первом меньше фактических вычислений.
 
 Best regards,
 Андрей.
 --- ifmail v.2.15dev5
  * Origin: good enough (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    КАК ОПРЕДЕЛИТЬ HАПРАВЛЕHИЕ ОБХОДА ?????????   Alexander Kothubievski   31 Oct 2001 14:36:37   Re: КАК ОПРЕДЕЛИТЬ HАПРАВЛЕHИЕ ОБХОДА ?????????   Andrey Tarasevich   31 Oct 2001 21:48:41