Здравствуйте MadMax, Вы писали:
MM>Есть массив точек (POINT) представляющий замкнутый контур. Надо определить направление его обхода (по/против часовой стрелки). Любые идеи хороши.
Возьми любую точку O.
Построй все вектора O-P(0), O-P(1), ... O-P(N-1). P(i) — это точки твоего контура.
Посчитай сумму всех векторных произведений
[O-P(i), O-P(i+1)], i = 0... n-1; + [O-P(N-1), O-P(0)] — надо замкнуть.
Посмотри знак z координаты получившейся суммы.
Если он положителен, то контур против часовой стрелки.
Если контур с самопересечениями,
то можно получить некое "среднее" направление обхода.
Здравствуйте MadMax, Вы писали:
MM>Есть массив точек (POINT) представляющий замкнутый контур. Надо определить направление его обхода (по/против часовой стрелки). Любые идеи хороши.
Ты скажи, контур на плоскости, в пространстве или вообще в криволинейных координатах какой-нибудь поверхности ?
Здравствуйте surgeon, Вы писали:
S>Здравствуйте MadMax, Вы писали:
MM>>Есть массив точек (POINT) представляющий замкнутый контур. Надо определить направление его обхода (по/против часовой стрелки). Любые идеи хороши.
S>Ты скажи, контур на плоскости, в пространстве или вообще в криволинейных координатах какой-нибудь поверхности ?
А почему тогда не спрашиваешь "с какой стороны смотреть?"
Ведь если с одной, то может быть по часовой, а если с противоположной, то совсем наоборот...
Надеюсь, что контур в этом вопросе состоит из точек на экране, а смотреть надо на него снаружи...
Здравствуйте MadMax, Вы писали:
MM>Есть массив точек (POINT) представляющий замкнутый контур. Надо определить направление его обхода (по/против часовой стрелки). Любые идеи хороши.
Мда, Господа. Вы чегото тут такого написали... Я так понимаю есть произвольный массив точек, и не понятно в каком порядке его так сказать выводить. Так вот ниже решение. (Первый абзац я написал после того, как прочитал чего вы понаписали.)
Я вот тут посмотрел на замкнутый контур из n точек, всмысле на выпуклый замкнутый контур (в случае невыпуклого — не знаю что делать, думаю задача нерешабельна, ну может и решабельна но не так просто, надо пораскинуть морщинами на лбу, ну всмысле теми извилинами, которые в мозгу не уместились) и мне пришла в голову такая идея: Сортируем массив точек по X (по возрастанию, хотя это пофиг как, кому как нравится). Первый елемент массива это та точка, от которой мы будем отталкиваться. Ее порядковый номер 0. Позначим Y1=Y2=Y; i1=i2=1. Теперь перебираем все оставшиеся точки по одной и смотрим ежили у ней Y меньше Y2, то ее номер n-i2; Y2=Y; i2++, ежели нет то ее номер i1; Y1=Y; i1++. В результате получим обход против часовой стрелки.
Вот собственно и весь алгоритм.
ЗЫ Если я непонятно пояснил (думаю оно так и есть), то пишите на мыло, накидаю пример.
В те далекие времена, когда байты были еще битами...
Здравствуйте Рек, Вы писали:
Рек>Здравствуйте surgeon, Вы писали:
S>>Здравствуйте MadMax, Вы писали:
MM>>>Есть массив точек (POINT) представляющий замкнутый контур. Надо определить направление его обхода (по/против часовой стрелки). Любые идеи хороши.
S>>Ты скажи, контур на плоскости, в пространстве или вообще в криволинейных координатах какой-нибудь поверхности ?
Рек>А почему тогда не спрашиваешь "с какой стороны смотреть?" Рек>Ведь если с одной, то может быть по часовой, а если с противоположной, то совсем наоборот... :)
Рек>Надеюсь, что контур в этом вопросе состоит из точек на экране, а смотреть надо на него снаружи... :)))
Если контур выпуклый — вычисляешь габаритный прямоугольник его, находишь точку центра О.
Допустим, контур состоит из N — точек (С1, С2, ... СN-1). V1 = C1-O, V2 = C2-O (векторное вычитание). Затем — arccos (V1*V2),где V1*V2 — скалярное произведение. Это — угол между векторами. Если он больше нуля — направление одно, меньше — противоположное.
Тут конечно важно, чтобы точки С1 и С2 не совпадали и в контуре не было петель и перехлестов, да — и чтоб контур не был вогнутым. Эти алгоритмы сложны, я их не знаю.
Здравствуйте Бадян, Вы писали:
Б>Здравствуйте MadMax, Вы писали:
MM>>Есть массив точек (POINT) представляющий замкнутый контур. Надо определить направление его обхода (по/против часовой стрелки). Любые идеи хороши.
Постараюсь по-подробнее объяснить свой способ.
Задача нахождения направнения обхода контура сводится к вычислению его площади.
Это может показаться странным, но вам будет достаточно вспомнить что площадь охваченная контуром это вектор! О направлении обхода контура можно судить по направлению его площади.
Если непонятно, вспомните правило буравчика из школьной электротехники?
Вот направление контура простейшей формы отределяется по этому правилу.
Если вектор площади направлен за экран, то контур по часовой, если нам вглаз, то против. (Буравчик!) Именно это я имел ввиду, когда говорил, что нас интересует только знак Z координата площади.
Если контур сложный, с самопересечениями (невыпуклость пустяк — никаких сложностей из-за неё нет), то направление (по/против часовой стрелки) может быть различным на различных участках контура. Именно поэтому в простейшем смысле направление обхода какого контура смысла не имеет (оно разное на разных участках!), но если вспомнить что контур характеризуется векторной площадью, направление которой зависит от направления обхода, то можно характеризовать "направление обхода конрута" именно этой площадью (вектором). Направление этой площади будет характеризовать в какую сторону контур одходился "в основном". Именно это я и имел ввиду, когда говорил про "среднее направление обхода".
Теперь давайте научимся считать эту площадь.
Вспомним, что векторное произведение двух векторов — по величине совпадает с площадью параллелограмма, построенного на этих векторах. Этим и воспользуемся.
Пусть наш контур — это выпуклый многоугольник возьмём любую его внутреннюю точку, и соединим с каждой вершиной многоугольника. Получим N векторов.
Потом составим N пар соседних векторов и сосчитаем векторное произведение для каждой пары. Каждое векторное произведение(вектор!) это площадь(тоже вектор!) одного <B>сегментика</B>, сложив все сегментики получим площадь моногоугольника (вектор!).
То что мы считали площадь как векторное произведение, гарантирует, что мы получим правильное направление площади (по правилу буравчика!).
Если контур не выпуклый. Действуем точно также!
Просто теперь некоторые векторные произведения в нашей сумме будут иметь противоположный знак (направление обратное по отношению к общей массе). Это нормально.
Площадь сосчитается правильно. Нарисуйте рисунок, нарисуйте сегментики, проставьте каждому сегмерту знак с каким его площадь будет учтена в сумме — и вы всё поймёте.
Если вы согласитесь со мней в предыдущем абзаце, то немного поразмыслив поймёте,
что точку O можно взять где угодно. Для определённости её можно взять как первую точку контура, или центр boundbox'а — принципиального значения не имеет.
Вот собственно и всё. Спасибо за внимание.
Кстати, это отличный пример плоской задачи, решение которой требует выхода в третье измерение, в объём! Это всегда интересно.
Простой способ такой — работает и для невыпуклых контуров.
Итак, берем вектор, образованый 1 и 2 точками. Поворачиваем его на 90 градусов. Смещаемся в полученном направлении от 1-й точки на мааааельнькую величину. например 1е-5. Получаем тестовую точку. Далее для нее вызывам процедуру pnpoly из comp.graphics.algorithms FAQ — она определяет (быстро) лежит ли точка внутри заданого контура.
Ну и если лежит — то контур по часовой — если нет — то против.
Appendix1
int pnpoly(const dvector *pArr, const int npol, const dvector& vect)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++)
{
if ((((pArr[i].y <= vect.y) && (vect.y < pArr[j].y)) ||
((pArr[j].y <= vect.y) && (vect.y < pArr[i].y))) &&
(vect.x < (pArr[j].x - pArr[i].x) *
(vect.y - pArr[i].y) / (pArr[j].y - pArr[i].y) + pArr[i].x))
c = !c;
}
return c;
}
Здравствуйте Sasparella, Вы писали:
S>Итак, берем вектор, образованый 1 и 2 точками. Поворачиваем его на 90 градусов. Смещаемся в полученном направлении от 1-й точки на мааааельнькую величину. например 1е-5. Получаем тестовую точку. Далее для нее вызывам процедуру pnpoly из comp.graphics.algorithms FAQ — она определяет (быстро) лежит ли точка внутри заданого контура. S>Ну и если лежит — то контур по часовой — если нет — то против.
А если в начале первого отрезка острый угол?
Тогда алгоритм не сработает — проверяемая точка всегда будет снаружи контура.
Например равносторонний треугольник будет всегда считаться завёрнутым против часовой стрелки...
Поворот на 90 градусов в этом случае многоват будет.
А на сколько?
Как тебе вот такое усовершенствование?
1. Берём два соседних отрезка [ab] и [bc]
2. Считаем две точки
b + (ba+bc)* 1e-5
и
b — (ba+bc)* 1e-5
3. Выбираем из них ту, что справа от отрезка [ab].
4. Проверяем внутренняя ли она?
Здравствуйте Рек, Вы писали:
Рек>Здравствуйте Sasparella, Вы писали:
S>>Итак, берем вектор, образованый 1 и 2 точками. Поворачиваем его на 90 градусов. Смещаемся в полученном направлении от 1-й точки на мааааельнькую величину. например 1е-5. Получаем тестовую точку. Далее для нее вызывам процедуру pnpoly из comp.graphics.algorithms FAQ — она определяет (быстро) лежит ли точка внутри заданого контура. S>>Ну и если лежит — то контур по часовой — если нет — то против.
Рек>А если в начале первого отрезка острый угол? Рек>Тогда алгоритм не сработает — проверяемая точка всегда будет снаружи контура. Рек>Например равносторонний треугольник будет всегда считаться завёрнутым против часовой стрелки... Рек>Поворот на 90 градусов в этом случае многоват будет. Рек>А на сколько?
Рек>Как тебе вот такое усовершенствование? Рек>1. Берём два соседних отрезка [ab] и [bc] Рек>2. Считаем две точки Рек>b + (ba+bc)* 1e-5 Рек>и Рек>b — (ba+bc)* 1e-5
Рек>3. Выбираем из них ту, что справа от отрезка [ab]. Рек>4. Проверяем внутренняя ли она?
Рек>Подойдёт?
Можно наверное и так — но уж слишком ресурсоемко — IMHO просто достаточно смещаться не от ПЕРВОЙ точки — а от СЕРЕДИНЫ первого отрезка. Кстати, у себя в проге я так и делаю — видимо просто вчера чегото приглючило — как никак пол второго ночи было...
Здравствуйте, Рек, Вы писали:
Рек>Постараюсь по-подробнее объяснить свой способ.
Здорово. А если схватить ломаную за хвост (вектор площади начинается из первой точки), то можно прикинуть «примерно» в какую сторону наклонена незамкнутая ломаная. Промежуточные векторы вроде должны всегда смотреть на вектор площади, так?
