Направление ввода полигона. Раздел «Алгоритмы и математические задачи.». Форум программистов «Весельчак У»

Имеется вот такая задача: определить направление (по ЧС или против ЧС), в котором были введены вершины полигона. Собственно, нужено чётко различить знак, а само понятие направления тут довольно условно. Вводится полигон так: мышью щёлкаем по окну, вводя последовательно точки-вершины. Я по своим догадкам попытался решить так (но, видимо, неправильно): беру первую вершину в качестве начала всех радиус-векторов, затем считаю сумму векторных произведений для всех смежных пар векторов по очереди. Каждый вектор суммы имеет знак в зависимости от направления вращения первого вектора ко второму, а чтобы не учитывалась длина исходных векторов, вектор-результат для каждой пары делится на произведение их модулей - как-будто полигон состоит из единичных векторов (хотя, не полностью уверен, что правильно так поступать). Все значения векторных произведений суммирую, получается итоговый "момент", по его знаку различаю направление ввода полигона

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

вот код:

Код:

//определить, по часовой стрелке направление или нет 
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;
}

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

#define EPSYLON ((real) 0.000000001)

typedef double real;

// Множество осей
enum CoordsAxis { xAxis = 0, yAxis, zAxis};

// Направления обхода
enum PolygonDetourMode{ dmAuto = 0, dmCW, dmCCW};

PolygonDetourMode CPolygon::DetectDetour( CoordsAxis a1, CoordsAxis a2) const throw ( EMathsssError*)
{
CVertexPair side;
VERTEX Triangle[3];
real a1_d1, a1_d2, a2_d1, a2_d2, r, minL, t;
bool bCW( false), bCCW( false);

for ( long lIdx = 0; lIdx < m_lCount; lIdx++)
{
for ( long i = 0; i < 3; i++)
Triangle[i] = m_pVertexes[(lIdx + i) % m_lCount];

//Выяснение "масштаба нуля"
side.V[0] = Triangle[0];
side.V[1] = Triangle[1];
minL = side.Length;

side.V[0] = Triangle[1];
side.V[1] = Triangle[2];
t = side.Length;
if ( t < minL) minL = t;

side.V[0] = Triangle[2];
side.V[1] = Triangle[0];
t = side.Length;
if ( t < minL) minL = t;
minL *= EPSYLON;

a1_d1 = Triangle[1].Coords[a1] - Triangle[0].Coords[a1];
a2_d1 = Triangle[1].Coords[a2] - Triangle[0].Coords[a2];

a1_d2 = Triangle[2].Coords[a1] - Triangle[1].Coords[a1];
a2_d2 = Triangle[2].Coords[a2] - Triangle[1].Coords[a2];
r = (a1_d1 * a2_d2) - (a1_d2 * a2_d1);

if ( fabs( r) > fabs( minL)) //Засчитываем попытку
{
if ( r < 0)
{
if ( bCCW)
{
throw new __EMathsssError( ERROR_DETOUR_DETECT_FAILED);
}
bCW = true;
}
else
{
if ( bCW) throw new __EMathsssError( ERROR_DETOUR_DETECT_FAILED);
bCCW = true;
}
}
}
if ( bCW) return dmCW;
else
if ( bCCW) return dmCCW;
throw new __EMathsssError( ERROR_DETOUR_DETECT_FAILED);
}

	Автор	Тема: Направление ввода полигона (Прочитано 63281 раз)
0 Пользователей и 1 Гость смотрят эту тему.