Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Направление ввода полигона
Форум на CrossPlatform.RU > Библиотеки > Другие библиотеки
Алексей1153
Имеется вот такая задача: определить направление (по ЧС или против ЧС), в котором были введены вершины полигона. Собственно, нужено чётко различить знак, а само понятие направления тут довольно условно. Вводится полигон так: мышью щёлкаем по окну, вводя последовательно точки-вершины. Я по своим догадкам попытался решить так (но, видимо, неправильно): беру первую вершину в качестве начала всех радиус-векторов, затем считаю сумму векторных произведений для всех смежных пар векторов по очереди. Каждый вектор суммы имеет знак в зависимости от направления вращения первого вектора ко второму, а чтобы не учитывалась длина исходных векторов, вектор-результат для каждой пары делится на произведение их модулей - как-будто полигон состоит из единичных векторов (хотя, не полностью уверен, что правильно так поступать). Все значения векторных произведений суммирую, получается итоговый "момент", по его знаку различаю направление ввода полигона

алгоритм , похоже, неверный, так как правильно знак определяется через раз
опять же, что делать с вершинами, совпавшими с первой. Сейчас я их просто игнорирую при суммировании

вот код:
Раскрывающийся текст
//определить, по часовой стрелке направление или нет 
bool CGrafics::Poligon_GetDirIsClock(CPoint* points,int count)const
{
    if(!points || count<3)return true;

    //считаем первую точку началом радиус-вектора
    
    const LONG& x0=points[0].x;
    const LONG& y0=points[0].y;

    //остальные вершины представляют собой концы радиус-вектора
    // для всех по очереди считаем векторное произведение
    // и суммируем со знаком
    double vecSumm=0;

    LONG x1=points[1].x;
    LONG y1=points[1].y;

    for(int i=2;i<count; i++)
    {
        LONG x2=points[i].x;
        LONG y2=points[i].y;

        if(x1==x0 && y1==y0 || x2==x0 && y2==y0)
        {
            //одна из точек совпала с начальной точкой
        }
        else
        {
            //модуль вектора поворота надо будет разделить на произведения
            //модулей векторов, чтобы не учитывалась длина векторов
            LONG module1=sqrtl((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0));
            LONG module2=sqrtl((x2-x0)*(x2-x0)+(y2-y0)*(y2-y0));

            if(module1 && module2)
            {
                vecSumm+=(x1*y2-y1*x2)*1.0/(module1*module2);
            }
        }

        x1=x2;
        y1=y2;
    }

    //знак суммы покажет направление вращения
    return vecSumm>0;
}

Подскажите, кто знает, по какому алгоритму определить направление ввода полигона
Iron Bug
для вогнутых многоугольников твой метод работать не будет. точнее, не всегда. центр отсчёта векторов должен быть внутри многоугольника
Алексей1153
Iron Bug, арифметический центр тоже не подойдёт, я так понимаю ? Ведь он может оказаться вне полигона. Что посоветуешь ? )
ufna
Вопрос - а что есть "по часовой"? Я понимаю это для выпуклых и там достаточно просто посчитать, но вот "в общем" просто не знаю как это в принципе понимать :)
Алексей1153
ufna, это условно. Главное - знак различить. Например, условно по ЧС - это вокруг некой мысленной точки задаёшь стороны полигона. При этом могут быть и петли, но общий "момент" радиус вектора - всё равно по ЧС

соответственно, против ЧС - всё то же самое, но зеркально

ufna, а зачем это нужно - от направления обхода зависит знак вектора нормали полигона
ufna
Вот изображение в приложении - так по ЧС или против ЧС?
Алексей1153
это ЧС, но с самопересечением. Их быть не должно - это уже два разных полигона

1-2-3-10-1 это ЧС
10-4-5-6-7-8-9-10 это !ЧС
Алексей1153
Вот получил ответ на одном из форумов:

>>
"Математика и САПР", Москва, "Мир", 1988, стр. 15:

Знак площади зависит от направления обхода контура. В правой системе координат положительный знак указывает направление против часовой стрелки.

Площадь полигона

A = ( S(xi*yi+1 - xi+1*yi) + xN*y1 - x1*yN)/2

Знак S означает "сумма по i от 1 до N-1".


PS на первый и второй взгляд - работает :)
Y
Действительно работает! проверено для вогнутых и выпуклых полигонов!
Спасибо!

Цитата(Алексей1153 @ 24.12.2010, 20:50) *
Вот получил ответ на одном из форумов:

>>
"Математика и САПР", Москва, "Мир", 1988, стр. 15:

Знак площади зависит от направления обхода контура. В правой системе координат положительный знак указывает направление против часовой стрелки.

Площадь полигона

A = ( S(xi*yi+1 - xi+1*yi) + xN*y1 - x1*yN)/2

Знак S означает "сумма по i от 1 до N-1".


PS на первый и второй взгляд - работает :)

Алексей1153
да, я тоже уже убедился в этом :)
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2024 IPS, Inc.