float t = ((py-clipPoly.vertices [edge].y)*dx -(px-clipPoly.vertices [edge].x)*dy) / denominator;
float tx, ty; // point of intersection
if (t <= 0.0 ) {
tx = px; ty = py;
}
else
if (t>= 1.0 ) {
tx = cx; ty = cy;
}
else
{
tx = px + t*(cx - px); ty = py + t*(cy - py);
}
addVertexToOutPolygon (outPolygon, outVertices,lastVertex, tx, ty);
}
if ( ++intersectionCount >= 2 ) {
if (fabs (denominator) < 1 ) intersectionCount = 0;
else
{ // drop out, after adding all vertices left in input polygon if (curVertexInside)
r
\
memcpy ( &outPolygon [outVertices], &inPolygon [i], (inVertices - i)* sizeof (Vector2D ) );
outVertices += inVertices - i;
}
break;
}
}
}
px = cx; Py = cy;
prevVertexInside = curVertexInside;
}8. Основные алгоритмы вычислительной геометрии
// if polygon is wiped out, break
if ( outVertices < 3 ) break;
// switch input/output polygons inVertices = outVertices; inPolygon = outPolygon; if ( outPolygon == outPoly2 ) outPolygon = outPolyl;
else
outPolygon = outPoly2;
}
if ( outVertices < 3 ) return NULL;
return new Polygon ( outPolygon, outVertices )
}Следует заметить, что приведенный алгоритм не является оптимальным по времени выполнения: доказано, что пересечение многоугольников р и q можно выполнить за время 0(пр + nq), где пр и nq - количество вершин многоугольников р и q, соответственно (см. [15]).
< 8.10. Построение триангуляции Делоне Рассмотрим задачу триангуляции набора точек S на плоскости. Все точки набора S можно разбить на граничные - точки, лежащие на границе выпуклой оболочки convS, и внутренние - лежащие внутри convS. Ребра, полученные в результате триангуляции S, разбиваются на ребра оболочки и внутренние ребра. К ребрам оболочки относятся ребра, расположенные вдоль границы convS, а к внутренним - все остальные.
Любой набор точек (за исключением некоторых тривиальных случаев) допускает более одного способа триангуляции. Однако при этом выполняется следующее.
Утверждение. Пусть набор S содержит п ^ 3 точек и не все из них коллинеарны. Пусть, кроме того, i из них являются внутренними (лежат внутри выпуклой оболочки convS). Тогда при любом способе триангуляции набора S будет получено п + i - 2 треугольников.