|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Kothubievski 2:5020/400 31 Oct 2001 14:36:37
To : Oleg Tynianyi
Subject : КАК ОПРЕДЕЛИТЬ HАПРАВЛЕHИЕ ОБХОДА ?????????
--------------------------------------------------------------------------------
Tue Oct 30 2001 18:04, Oleg Tynianyi wrote to All:
OT> Привет знатокам !!
OT> Как-то уже писал, видимо не помогло, рискну еще раз:
OT> Есть массив точек (X,Y) на плоскости. Они образуют замкнутую фигуру.
OT> КАК определить, что они перечислены по часовой или против часовой стрелки
OT> ? Просто сам факт: по или против ????
OT> Если можно, то не слишком в общем виде, а то я x - f(н), где н есть
OT> полиномиальное склонение от интегрального счисления, а далее легко
OT> методом Графов (кто они такие ?!?!) ЛЕГКО HАХОДИМ ..... и т.д.
OT> короче это для меня трудно, если есть - кусочек программки на любом
OT> языке, кроме Perla )))
OT> Олег
Я могу предложить следуюшию идею:
Идея проста и лежит на поверхности . Берутся три точки идущие подряд в массиве
. Эти три точки задают два вектора на плоскости . Первый вектор из первой
точки во вторую , второй вектор из второй точки в третью . Будем считать что
эти вектора лежат в трехмерном пространстве на плоскости (x,y). Для трехмерных
векторов определена , как известно , операция - векторное произведение .
Результирующий вектор в нашем случае будет ортогонален плоскости (x,y) и его
направление зависит от знака синуса угла между двумя исходными векторами . Т.е
если проитись по массиву и вычислять последовательно векторые произведения то
можно определить направлени обхода . Положительные значения соответствуют
обходу против часовой стрелки , отрицательные по часовой стрелке . Если в
процессе обхода знак векторного произведения меняется то значит обходится не
выпуклый контур . А для не выпуклого контура понятие направления обхода ( по
часовой стрелке или против) теряет смысл .
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
