ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Tynianyi                        2:5025/900     25 May 2001  11:29:52
 To : All
 Subject : Re: Как опpеделить напpавление обхода ?!?
 -------------------------------------------------------------------------------- 
 

 
 А что если так, попинайте:
 
 Если точки следуют друг за другом в массиве, а это подразумевается в
 практическом приложении
 данной задачи, следовательно можно не рассматривать все точки, достаточно 3
 точек,
 вторая (2) из которых является одной из самых нижних.
 Исходя из этого предлагается вычислить два угла между соответственно:
 1) прямая через точки 1 и 2 и прямая, проведенная из точки 2 горизонтально
 влево
 2) прямая через точки 3 и 2 и прямая, проведенная из точки 2 горизонтально
 влево
 
 Если угол 2) больше угла 1) - против часовой, и наоборот.
 
 ПИHАЙТЕ ВСЕМ МИРОМ !?!?!?!
 
 Олег
 
 > MB> Добрый день! Есть набор двумерных точек, задающих плоский же
 > многоугольник.
 > MB> Точки заданы своими координатами. Как определить, в какую сторону
 > обходится
 > MB> этот полигон: по часовой стрелке или против?
 >
 > пусть заданы точки V[i], i=1..N
 >
 >                     1 || Ax Ay 1 ||
 > S(A, B, C)= - || Bx By 1 ||                // знаковая площадь
 
 треугольника
 
 > ABC
 >                     2 || Cx Cy 1 ||
 >
 > S[k] = S(V[1], V[k+1], V[k+2]), k=1..N-2   //площади сегментов
 > многоугольника
 >
 > просуммируем S[k]. знак суммы и определит направление обхода:
 
 положительный
 
 > знак соответствует положительному обходу (против часовой стрелки).
 >
 > если сумма нулевая, то точки лежат на одной прямой, либо многоугольник
 > самопересекающийся.
 --- Microsoft Outlook Express 5.50.4133.2400
  * Origin: Comment is superfluous... (2:5025/900@fidonet)
 
 

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