ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yurij Zabelyshynskij                 2:5020/400     28 May 2001  21:24:48
 To : All
 Subject : Re: Как определить направление обхода ?!?
 -------------------------------------------------------------------------------- 
 

 Hi, All.
 Извините за большое письмо, но, по-моему, обсуждение пошло по 2-му
 кругу.
 
 Oleg Tynianyi wrote 18.05.01
 
 OT> Есть на плоскости набор точек (в виде массива), образующих
 OT> замкнутый
 OT> многоугольник. Hужно выяснить, следуют ли точки
 OT> в массиве против часовой стрелки вокруг воображаемого центра
 OT> многоугольника или по часовой
 
 Oleg Polubasoff wrote 19.05.01 (цитируя Aleksey Smirnov и
 предполагая, что многоугольник несамопересекающийся)
 
 OPAS> Hаходим самую левую точку. Если мы пришли в неё снизу
 OPAS> или ушли из неё наверх, то многоугольник обходится по
 OPAS> часовой стрелке. Если мы пришли
 OPAS> в неё cверху или ушли вниз, то против.
 
 Заметим, что для самопересекающегося многоугольника направление
 обхода не  имеет смысла, но для невыпуклого - имеет и совсем не
 шаткое.
 
 Yurij Zabelyshynskij wrote 22.05.01
 
 YZ> В приведенной формулировке, если приходить и уходить вниз, то
 YZ> направление может быть любым.
 YZ> Тут, видимо, надо уточнить. Если для самой левой точки ребро, по
 YZ> которому мы пришли, ниже ребра, по которому ушли, то - по часовой
 YZ> стрелке, иначе - против.
 
 Oleg Tynianyi wrote 25.05.01
 
 OT> Если точки следуют друг за другом в массиве, а это подразумевается
 OT> в практическом приложении
 
 Заметим, что если заранее знать порядок точек, то их можно переставить
 именно в таком порядке, а если нет, то эта задача не имеет решения.
 
 OT> достаточно 3 точек, вторая (2) из которых является одной
 OT> из самых нижних. Исходя из этого предлагается вычислить
 OT> два угла между соответственно: 1) прямая через точки 1 и 2 и
 
 прямая,
 
 OT> проведенная из точки 2 горизонтально влево
 OT> 2) прямая через точки 3 и 2 и прямая, проведенная из точки 2
 OT> горизонтально влево
 OT> Если угол 2) больше угла 1) - против часовой, и наоборот.
 
 Этот способ - просто переформулировка предыдущего для самой нижней
 точки.
 Он тоже правильный, и для невыпуклого многоугольника в том числе.
 Все способы, основанные на вычислении площади, очевидно, более
 трудоемкие.
 
 Serge Kanilo wrote
 
 SK> Попробуй свой алгоритм на таком корявом пятиугольнике
 SK>  х  y
 SK>  1  0
 SK>  1  1
 SK>  0 -1
 SK> -1  1
 SK> -1  0
 SK> здесь 3-я точка нижняя (по y).
 
 Здесь самопересекающийся многоугольник.
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

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