Привет всем!
Скажите, пожалуйста, как определить направление обхода многоугольника?
Я делаю при помощи скалярных произведений смежных ребер, но пока что-то оно неверно определяется..
Подскажите, если не сложно!
Здравствуйте Zakhar, Вы писали:
Z>Скажите, пожалуйста, как определить направление обхода многоугольника? Z>Я делаю при помощи скалярных произведений смежных ребер, но пока что-то оно неверно определяется..
Ничего не понял. Направление обхода определяешь ты сам. Или тебе интересно выснить получилось оно по- или против часовой стрелки?
Здравствуйте Zakhar, Вы писали:
Z>Привет всем! Z>Скажите, пожалуйста, как определить направление обхода многоугольника? Z>Я делаю при помощи скалярных произведений смежных ребер, но пока что-то оно неверно определяется.. Z>Подскажите, если не сложно!
Для этого имхо надо использовать векторное, а не скалярное произведение. Смысл в том, что векторное произведение двух смежных ребер даст тебе вектор. Далее относительно нормали к своему прямоугольнику ты можешь говорить о направлении обхода.
Если ты такой умный, почему ты такой бедный?
Re[2]: Направление обхода многоугольника
От:
Аноним
Дата:
24.05.02 08:28
Оценка:
Здравствуйте Lexey, Вы писали:
L>Ничего не понял. Направление обхода определяешь ты сам. Или тебе интересно выснить получилось оно по- или против часовой стрелки?
Именно так. Мне задан многоугольник — необходимо выяснить — как он задан. Это нужно для алгоритма Вейлера-Азертона отсечения многоугольников.
С уважением,
Захар.
Re[2]: Направление обхода многоугольника
От:
Аноним
Дата:
24.05.02 08:30
Оценка:
Здравствуйте ppp, Вы писали:
ppp>Для этого имхо надо использовать векторное, а не скалярное произведение. Смысл в том, что векторное произведение двух смежных ребер даст тебе вектор. Далее относительно нормали к своему прямоугольнику ты можешь говорить о направлении обхода.
Пардон! Ошибочка. Я использую именно векторное :-)
А как определять направление нормали? И что будет в случае невыпуклого многоугольника?
Здравствуйте Аноним, Вы писали:
А>Здравствуйте ppp, Вы писали:
ppp>>Для этого имхо надо использовать векторное, а не скалярное произведение. Смысл в том, что векторное произведение двух смежных ребер даст тебе вектор. Далее относительно нормали к своему прямоугольнику ты можешь говорить о направлении обхода.
А>Пардон! Ошибочка. Я использую именно векторное А>А как определять направление нормали? И что будет в случае невыпуклого многоугольника?
Выпуклый-невыпуклый многоугольник — нам без разницы
Изначально ты задаешь направление нормали. Т.е. представляешь себе этот многоугольник в пространстве и говоришь — с этой стороны мы видим многоугольник, а вот с этой не должны видеть.
Нормаль ты вычисляешь как векторное произведение любых двух ребер, далее (исходя из своего представления многоугольника в пространстве) ты поворачиваешь ее в сторону от тела (опять же если она у тебя оказалась направленной внутрь тела).
Далее направление обхода вычисляется очевидно, я тебе уже писал:
1) Берешь любые два ребра, идущие подряд.
2) Вычисляешь их векторное произведение.
3) Смотришь, направлен-ли полученный вектор в одну сторону с нормалью или в другую сторону. Зная эти данные, можешь сказать, обходишь-ли ты многоугольник по часовой стрелке или против.
ВАЖНО: Все точки ребер в массиве у тебя должны быть заданы именно подряд. В принципе некоторые представления фигур в пространстве требуют задания точек в массиве, как если бы ты смотрел со стороны нормали на многоугольник и перечислял их против часовой стрелки. (это уже условности). Если ты таким образом задаешь все многоугольники в пространстве, то потом можно очень легко отсекать невидимые грани и избавляться от глюков
Здравствуйте Zakhar, Вы писали:
Z>Привет всем! Z>Скажите, пожалуйста, как определить направление обхода многоугольника? Z>Я делаю при помощи скалярных произведений смежных ребер, но пока что-то оно неверно определяется.. Z>Подскажите, если не сложно!
Спасибо большое! Но к сожалению, я не все понял: ppp>Изначально ты задаешь направление нормали. Т.е. представляешь себе этот многоугольник в пространстве и говоришь — с этой стороны мы видим многоугольник, а вот с этой не должны видеть. ppp>Нормаль ты вычисляешь как векторное произведение любых двух ребер,
А разве не надо просмотреть все ребра и проверить знаки всех векторных произведений? Как по двум ребрам можно заключить обо всем многоугольнике? ppp>далее (исходя из своего представления многоугольника в пространстве) ты поворачиваешь ее в сторону от тела (опять же если она у тебя оказалась направленной внутрь тела).
Что значит _задать_ направление нормали? И что означает "поворачиваю"?
Здравствуйте Zakhar, Вы писали:
Z>Здравствуйте ppp
Z>Спасибо большое! Но к сожалению, я не все понял: ppp>>Изначально ты задаешь направление нормали. Т.е. представляешь себе этот многоугольник в пространстве и говоришь — с этой стороны мы видим многоугольник, а вот с этой не должны видеть. ppp>>Нормаль ты вычисляешь как векторное произведение любых двух ребер, Z>А разве не надо просмотреть все ребра и проверить знаки всех векторных произведений? Как по двум ребрам можно заключить обо всем многоугольнике? ppp>>далее (исходя из своего представления многоугольника в пространстве) ты поворачиваешь ее в сторону от тела (опять же если она у тебя оказалась направленной внутрь тела). Z>Что значит _задать_ направление нормали? И что означает "поворачиваю"?
Z>Прошу прощения за тугодумство
A
/ / / \ F
B/ D /
\ /\ /
\/ \/
C E
Вот у тебя есть невыпуклый многоугольник ABCDEF. Допустим, что нормаль этого многоугольника смотрит тебе прямо в глаз Т.е. со своей стороны ты должен видеть этот многоугольник, а если смотреть с другой стороны монитора, то не должен. Направление нормали вычисляем как векторное произведение AB * BC В этом случае нормаль будет смотреть как раз тебе в левый глаз.
Выбираешь любую точку многоугольника (например A) и заносишь точки в свой массив по направлению против часовой стрелки. получается ты последовательно заносишь точки ABCDEF.
Далее чтобы понять, в какую сторону ты обходишь многоугольник, ты вычисляешь векторное произведение двух последовательных ребер. Например, ты начал обход с точки E, следующие точки у тебя EDCBAF.
Вычисляешь векторное произведение DE*DC (это вариант через среднюю точку, есть еще варианты через начальную точку обхода типа ED*DC, в принципе все одинаковы). Если полученный вектор направлен в сторону нормали, то направление обхода против часовой стрелки. Если в противоположную от нормали сторону, то обход по часовой стрелке.
Здравствуйте ppp, Вы писали:
ppp>Здравствуйте Zakhar, Вы писали:
Z>>Здравствуйте ppp
Z>>Спасибо большое! Но к сожалению, я не все понял: ppp>>>Изначально ты задаешь направление нормали. Т.е. представляешь себе этот многоугольник в пространстве и говоришь — с этой стороны мы видим многоугольник, а вот с этой не должны видеть. ppp>>>Нормаль ты вычисляешь как векторное произведение любых двух ребер, Z>>А разве не надо просмотреть все ребра и проверить знаки всех векторных произведений? Как по двум ребрам можно заключить обо всем многоугольнике? ppp>>>далее (исходя из своего представления многоугольника в пространстве) ты поворачиваешь ее в сторону от тела (опять же если она у тебя оказалась направленной внутрь тела). Z>>Что значит _задать_ направление нормали? И что означает "поворачиваю"?
Z>>Прошу прощения за тугодумство ppp>
ppp> A
ppp> / / / \ F
ppp> B/ D /
ppp> \ /\ /
ppp> \/ \/
ppp> C E
ppp>
А на предосмотре многоугольник был в нормальном состоянии Непорядочек
ppp> A / \ F
ppp> / /
ppp> B/ D /
ppp> \ /\ /
ppp> \/ \/
ppp> C E
ppp>
ppp>Вот у тебя есть невыпуклый многоугольник ABCDEF. Допустим, что нормаль этого многоугольника смотрит тебе прямо в глаз Т.е. со своей стороны ты должен видеть этот многоугольник, а если смотреть с другой стороны монитора, то не должен. Направление нормали вычисляем как векторное произведение AB * BC В этом случае нормаль будет смотреть как раз тебе в левый глаз. ppp>Выбираешь любую точку многоугольника (например A) и заносишь точки в свой массив по направлению против часовой стрелки. получается ты последовательно заносишь точки ABCDEF. ppp>Далее чтобы понять, в какую сторону ты обходишь многоугольник, ты вычисляешь векторное произведение двух последовательных ребер. Например, ты начал обход с точки E, следующие точки у тебя EDCBAF. ppp>Вычисляешь векторное произведение DE*DC (это вариант через среднюю точку, есть еще варианты через начальную точку обхода типа ED*DC, в принципе все одинаковы). Если полученный вектор направлен в сторону нормали, то направление обхода против часовой стрелки. Если в противоположную от нормали сторону, то обход по часовой стрелке.
Вот, изначально тоже думал всех перехитрить, проверял векторное произведение векторов, определяемых тремя последними точками. Не перехитрил, иногда выходит 0 — и начинаются проблемы. После думал считать индексы самой левой, самой правой, верхней и нижней точек, а по ним определить направление обхода — тоже плохо:
___
\ \
\__\
получается 2 "экстремума" — и ничего не поделаешь, определить невозможно.
Во время написания пришла ещё одна идея для выпуклых многоугольников (А меня многоугольники именно выпуклые):
Запоминать — шли вниз влево, влево...
Или — вправо, вправо вверх.
Первого изменения направления — достаточно.
Думаю, как быстро определить это. Может, массив?
Что скажете?
С уважением,
fAX.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
ppp>Далее направление обхода вычисляется очевидно, я тебе уже писал: ppp>1) Берешь любые два ребра, идущие подряд. ppp>2) Вычисляешь их векторное произведение.
НЕВЕРНО! Не надо брать два ребра, идущие подряд.
Надо брать ТОЧКИ, идущие подряд, а не РАЗНОСТИ точек.
Иными словами надо взять сумму по всем вершинам величин x[i]*y[i+1]-x[i+1]*y[i]
Знак получившейся суммы даёт направление обхода.
А модуль — удвоенную площадь.
Здравствуйте, Zakhar, Вы писали:
Z>Скажите, пожалуйста, как определить направление обхода многоугольника? Z>Я делаю при помощи скалярных произведений смежных ребер, но пока что-то оно неверно определяется..
Во-первых, не скалярное произведение тебе нужно, а векторное (cross-product).
Во-вторых, перемножать надо не произвольную пару смежных ребер, а пару смежных ребер, выходящих из самой нижней из самых левых вершин многоугольника (или из самой левой из самых верхних, иди еще какую комбинацию можно взять — неважно).
Знак векторного произведения даст тебе направление обхода.
Непорядочек
