Основы программирования

Определить направление обхода вершин невыпуклого многоугольника (по часовой или против часовой стрелки), заданного координатами своих вершин и не имеющего самопересечений (пересечения своих граней).

Один из методов решения данной задачи является исследование по минимальной точке.
Входные данные:
- Циклический однонаправленный список координат многоугольника.
Выходные данные:
- значение «1» если многоугольник задан по часовой стрелке, иначе «-1».
Решение.
1. Находим минимальный элемент списка. ( Ищем минимальное значение по Х ).
2. Пусть А[к] минимальный элемент списка.
- Берем три вершины А[к-1], А[к], А[к+1].
- Проверяем образуют ли вектора (А[к]A[к-1]), (А[к]А[к+1]) левую тройку.
3. Если предыдущее условие выполнено, то возвращаем «1», иначе «-1»

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

Программа:

// Структура  ListPoint определяет один узел списка (вершина)
// и имеет ссылку на следующий узел этого же списка.
typedef struct ListPoint
{
    int x;
    int y;
    ListPoint *next;
};
typedef ListPoint *lpListPoint;
 
 
//функция для определения направления тройки векторов;
// векторное произведение векторов (x2 - x1 , y2 - y1) , ( x3 - x1, y3 - y1) 
long Det( int x1, int y1, int x2, int y2, int x3, int y3 )
{
	return  (long)(x2 - x1)*(y3 - y1) - (long)(y2 - y1)*(x3 - x1);
}
 
int isLeft_or_Right(  lpListPoint List )
{
lpListPoint ptr = List,
 prev = List ,
 min = List,
 min_p = List;
 
	while( prev->next != List )
	{
	     if( ptr->x < min->x )  { min = ptr; min_p = prev; }
	     prev =  ptr;
	     ptr = ptr->next;
	}
	if( min == List )
	   while( min_p->next != min )
	     min_p=min_p->next;
 
	if( Det( min->x, min->y, min_p->x, min_p->y,
		 min->next->x, min->next->y ) > 0 ) return 1;
	else return -1;
}