Имеется вот такая задача: определить направление (по ЧС или против ЧС), в котором были введены вершины полигона. Собственно, нужено чётко различить знак, а само понятие направления тут довольно условно. Вводится полигон так: мышью щёлкаем по окну, вводя последовательно точки-вершины. Я по своим догадкам попытался решить так (но, видимо, неправильно): беру первую вершину в качестве начала всех радиус-векторов, затем считаю сумму векторных произведений для всех смежных пар векторов по очереди. Каждый вектор суммы имеет знак в зависимости от направления вращения первого вектора ко второму, а чтобы не учитывалась длина исходных векторов, вектор-результат для каждой пары делится на произведение их модулей - как-будто полигон состоит из единичных векторов (хотя, не полностью уверен, что правильно так поступать). Все значения векторных произведений суммирую, получается итоговый "момент", по его знаку различаю направление ввода полигона
алгоритм , похоже, неверный, так как правильно знак определяется через раз
опять же, что делать с вершинами, совпавшими с первой. Сейчас я их просто игнорирую при суммировании
вот код:
//определить, по часовой стрелке направление или нет
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, арифметический центр тоже не подойдёт, я так понимаю ? Ведь он может оказаться вне полигона. Что посоветуешь ? )
Вопрос - а что есть "по часовой"? Я понимаю это для выпуклых и там достаточно просто посчитать, но вот "в общем" просто не знаю как это в принципе понимать
ufna, это условно. Главное - знак различить. Например, условно по ЧС - это вокруг некой мысленной точки задаёшь стороны полигона. При этом могут быть и петли, но общий "момент" радиус вектора - всё равно по ЧС
соответственно, против ЧС - всё то же самое, но зеркально
ufna, а зачем это нужно - от направления обхода зависит знак вектора нормали полигона
это ЧС, но с самопересечением. Их быть не должно - это уже два разных полигона
1-2-3-10-1 это ЧС
10-4-5-6-7-8-9-10 это !ЧС
Вот получил ответ на одном из форумов:
>>
"Математика и САПР", Москва, "Мир", 1988, стр. 15:
Знак площади зависит от направления обхода контура. В правой системе координат положительный знак указывает направление против часовой стрелки.
Площадь полигона
A = ( S(xi*yi+1 - xi+1*yi) + xN*y1 - x1*yN)/2
Знак S означает "сумма по i от 1 до N-1".
PS на первый и второй взгляд - работает
Действительно работает! проверено для вогнутых и выпуклых полигонов!
Спасибо!
да, я тоже уже убедился в этом
Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)