Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Вычислительная геометрия / Работа с многоугольниками /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Нахождение ориентации простого многоугольника - Программирование от RIN.RU
Нахождение ориентации простого многоугольника

Вычислите ориентированную площадь. Ориентация будет "по часовой стрелке", если площадь положительна.




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


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



// 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  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь