гоугольника всегда выпукло.
Рассмотрим следующую задачу: на плоскости задан набор точек s0, s\, ^потребуется построить "минимальный" звездчатый многоугольник так, чтобы его ядро содержало точку.%
Алгоритм работает итеративно, последовательно формируя из точек набора текущий многоугольник. Вначале многоугольник состоит из единственной точки s о, и на каждой итерации в него добавляется очередная точка набора. По окончании обхода всех точек мы получим искомый звездчатый многоугольник. ' Для определения того, в какое место границы текущего многоугольника нужно вставить точку 5„ заметим, что все вершины звездчатого многоугольника должны быть радиально упорядочены вокруг любой точки его ядра, а значит, и относительно Т^очки s0i принадлежащей ядру. Будем обходить границу многоугольника по часовой Стрелке начиная с точки sq, сравнивая каждый раз вставляемую точку и очередную Точку границы. Функцию сравнения вершин polarCmp определим, основываясь на вычислении полярных координат (г, в) точки относительно полюса % Введем следующее правило сравнения: точка р(Кр, вр) считается меньше точки q(\\, вч), если Ц>< Qq или 0р - ßq и Fp < Fq. При таком упорядочении, обход текущего многоугольника по часовой стрелке будет производиться от больших точек к меньшим. Реализация алгоритма приводится ниже.
W // File star.cpp
include "polygon.h"
Vector2D originPt;Компьютерная графика. Полигональные модели
int polarCmp ( Vector2D * р, Vector2D * q ) {
Vector2D vp = *p - originPt; Vector2D vq = *q - originPt; float pAngle = vp.polarAngle (); float qAngle = vq.polarAngle (),*
if ( pAngle < qAngle ) return -1;
if ( pAngle > qAngle ) return 1.;
float pLen = vp.length (); float qLen = vq.length ();
if ( pLen < qLen ) return -1;
if ( pLen > qLen ) return 1;
return 0;
}
Polygon * starPolgon (Vector2D s [], int n ) {
Polygon * p = new Polygon ( s, 1 );
originPt = s [0];
for (int i = 1; i < n; i++ ) {
for (int j = 1; polarCmp ( &s [i], &p->vertices [j]) < 0;) if ( ++j >= p -> numVertices )