Вычислите ориентированную площадь. Ориентация будет "по часовой стрелке", если площадь положительна.
Немного быстрее получится, если мы заметим, что вычислять площадь вовсе не обязательно. Найдем нижнюю вершину (если их несколько, то самую правую), а затем возьмем векторное произведение сторон после и перед ней.
Причина, по которой мы берем именно такую точку - в том, что внутренний угол при такой вершине обязательно будет выпуклым и строго меньше пи.
// This program reads in the vertices of a polygon from standard
// input, and determines whether the vertices have been entered in
// cw or ccw order. It finds the lowest and rightmost vertex, and
// computes the cross-product of the vectors along its incident
// edges.
// Written by Joseph O'Rourke, 25 August 1995.
// orourke@cs.smith.edu
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#define NMAX 100 // Maximum number of polygon vertices
#define X 0
#define Y 1
int ReadPoly( void );
int FindLR( int n );
int Ccw( int n, int m );
int poly[NMAX][2];
int main() {
int n, m;
n = ReadPoly();
m = FindLR( n );
if ( Ccw( n, m ) == 1 )
cout << "The polygon is oriented counterclockwise" << endl;
else
cout << "The polygon is oriented clockwise" << endl;
}
int ReadPoly()
{
int i,n;
i = 0;
while( !cin.eof() ) {
cin >> poly[i][X] >> poly[i][Y];
i++;
}
n = i-1;
// Echo polygon coordinates.
cout << "n=" << n << " vertices read." << endl;
for( i=0; i<n; i++ ) {
cout << "i=" << setw(3) << i;
cout << "; x=" << setw(3) << poly[i][X];
cout << "; y=" << setw(3) << poly[i][Y] << endl;
}
return n;
}
// FindLR finds the lowest, rightmost vertex of poly.
int FindLR( int n )
{
int i,m;
int min[2];
min[X] = poly[0][X];
min[Y] = poly[0][Y];
m = 0;
cout << "FindLR:";
for( i = 0; i < n; i++ ) {
if( (poly[i][Y] < min[Y]) ||
( (poly[i][Y] == min[Y]) && (poly[i][X] > min[X]) )
) {
m = i;
min[X] = poly[m][X];
min[Y] = poly[m][Y];
}
//cout << "i=" << i << " m=" << m;
}
8 8 8
| |
*
Обратная связь