Направление ввода полигона Опции

[Алексей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;
}

Подскажите, кто знает, по какому алгоритму определить направление ввода полигона

Сообщение отредактировал Алексей1153 - 24.12.2010, 8:25

[Iron Bug]

для вогнутых многоугольников твой метод работать не будет. точнее, не всегда. центр отсчёта векторов должен быть внутри многоугольника

[Алексей1153]

Iron Bug, арифметический центр тоже не подойдёт, я так понимаю ? Ведь он может оказаться вне полигона. Что посоветуешь ? )

[ufna]

Вопрос - а что есть "по часовой"? Я понимаю это для выпуклых и там достаточно просто посчитать, но вот "в общем" просто не знаю как это в принципе понимать

[Алексей1153]

ufna, это условно. Главное - знак различить. Например, условно по ЧС - это вокруг некой мысленной точки задаёшь стороны полигона. При этом могут быть и петли, но общий "момент" радиус вектора - всё равно по ЧС

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

ufna, а зачем это нужно - от направления обхода зависит знак вектора нормали полигона

Сообщение отредактировал Алексей1153 - 24.12.2010, 10:32

[ufna]

Вот изображение в приложении - так по ЧС или против ЧС?

Эскизы прикрепленных изображений

 

[Алексей1153]

это ЧС, но с самопересечением. Их быть не должно - это уже два разных полигона

1-2-3-10-1 это ЧС
10-4-5-6-7-8-9-10 это !ЧС

[Алексей1153]

Вот получил ответ на одном из форумов:

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

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

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

A = ( S(x_i*y_i+1 - x_i+1*y_i) + x_N*y₁ - x₁*y_N)/2

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


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

Сообщение отредактировал Алексей1153 - 24.12.2010, 20:50

[Гость_Y_*]

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

Вот получил ответ на одном из форумов:

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

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

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

A = ( S(x_i*y_i+1 - x_i+1*y_i) + x_N*y₁ - x₁*y_N)/2

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


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

[Алексей1153]

да, я тоже уже убедился в этом