8.5. Проверка принадлежности точки многоугольнику

Введем класс Polygon для представления многоугольников на плоскости. Ниже приводится h-файл, описывающий этот класс.

0 // File Polygon.h
#ifndef __POLYGON_ #define __POLYGON__
#include <mem.h> include "vector2d.h"
class Polygon
{
public:
int numVertices; // current # of vertices
int maxVertices; // size of vertices array
Vector2D * vertices;
Polygon () {
numVertices = maxVertices = 0; vertices = NULL;
}
Polygon ( const Vector2D * v, int size ) {
vertices = new Vector2D [numVertices = size]; maxVertices = size];
memcpy ( vertices, v, size * sizeof (Vector2D ));
}
Polygon ( const Polygon& p ) {
vertices = new Vector2D [p.maxVertices]; numVertices = p.numVertices; maxVertices = p.maxVertices;

Компьютерная графика. Полигональные модели

memcpy ( vertices, p.vertices,
numVertices * sizeof ( Vector2D ));
}
-Polygon ()
{
int
}
if (vertices != NULL ) delete [] vertices;
addVertex ( const Vector2D& v ) return addVertex ( v, numVertices );

int addVertex ( const Vector2D& v, int after); int delVertex (int index ); int islnside ( const Vector2D& ); Polygon * split (int from, int to );
protected:
void resize (int newMaxVertices );
};
#endif

Одним из методов класса Polygon является islnside, служащий для проверки принадлежности точки многоугольнику (рис. 8.4).

Рис. 8.4

Для решения этой задачи выпустим из точки А(х, у) произвольный луч и найдем количество точек пересечения этого луча с границей многоугольника. Если отбросить случай, когда луч проходит через вершину многоугольника, то решение задачи тривиально - точка лежит внутри, если общее количество точек пересечения нечетно, и снаружи, если четно.

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

⇐ Предыдущая| |Следующая ⇒