if ( vertices [ij.y > p.y && vertices 0] У > Р-У ) continue;

if ( vertices [ij.y < p.y && vertices [j].y < p.y ) continue;

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

if ( max ( vertices [i].y, vertices [j].y ) == P-y ) count ++;
else
if ( min ( vertices [i].y, vertices [j].y ) == py ) continue;
else {
float t = (p.y - vertices [i].y)/
(vertices [j].y - vertices [i].y); if ( vertices [i].x + t * (vertices [j].x -vertices [i].x) >= p.x )
count ++;
}
}
return count & 1;
}
Polygon * Polygon :: split (int from, int to ) {
Polygon * p = new Polygon; if (to < from )
to += numVertices; for (int i = from; i <= to; i++ )
p -> addVertex ( vertices [i % numVertices]);
if (to < numVertices )
memmove ( vertices+from+1, vertices+to+1,
(numVertices-to-1) * sizeof ( Vector2D ));
else
memmove (vertices, vertices+to,
(numVertices-to) * sizeof (Vector2D));
numVertices -= to - from - 1;
return p;
}
void Polygon :: resize (int newMaxVertices ) {
if ( newMaxVertices < maxVertices ) return;
Vector2D * newVertices = new Vector2D [maxVertices = newMaxVertice
if ( vertices != NULL ) {
memcpy ( newVertices, vertices, numVertices * sizeof (Vector2D)); delete 0 vertices;
}
}

8. Основные алгоритмы вычислительной геометрии

8.6. Вычисление площади многоугольника Для площади 5(Р) многоугольника Р, образованного вершинами V] справедлива следующая формула:

-IV

1 >'п?

Эта формула дает площадь многоугольника со знаком, зависящим от ориентации его вершин. В случае, когда вершины упорядочены в направлении против часовой стрелки,s(P) < 0.

8.7. Построение звездчатого полигона

, Пусть точки р и q лежат внутри некоторого многоугольника. Будем говорить, что точка q видна из точки р, если отрезок, соединяющий эти точки, целиком содержится в заданном многоугольнике.

Совокупность точек многоугольника, из которых видны все точки этого многоугольника, называется его ядром. Многоугольник называется звездчатым, если его ядро не пусто (рис. 8.6).

Отметим, что ядро звездчатого мно▼ Риг Я 6

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