| by YoungTimes | No comments

2D多边形切分(2D Polygon Partition)

CGAL提供了一系列多边形切分算法,支持将单个多边形切分成若干个小的多边形,每个多边形之间互不交叉,总和等于原多边形大小。

1.Monotone Partitioning

1.1 什么是单调多边形(monotone polygon)

在几何形状中,如果与L垂直的每条线最多与多边形P[……]

继续阅读

Read More
| by YoungTimes | No comments

任意简单多边形求差集(difference)

在日常开发中会遇到从一个多边形扣除掉部分区域的需求,如下图所示:

CGAL提供了CGAL::difference函数用于实现多边形差集的功能。函数原型如下:

其中type1和type2支持的类型如下:

Type1Type2Polygon_2Polygon_2Polygo[……]

继续阅读

Read More
| by YoungTimes | No comments

判断点在多边形内部、在多边形边界上还是在多边形外部

在网上已经有大量判断点是否在多边形内部的算法介绍。

如何判断一个点是否在多边形内部?
(1)面积和判别法:判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形,相等则在多边形内部。
(2)夹角和判别法:判断目标点与所有边的夹角和是否为360度,为360度则在多边形内部。
(3)引射线法:从目[……]

继续阅读

Read More
| by YoungTimes | No comments

判断多边形为顺时针或者逆时针

CGAL的Polygon函数提供了判断多边形点序列顺序的函数,直接返回多边形是否为顺时针或者逆时针。

下面实现一个检测多边形的点序列顺序是否为逆时针,如果为非逆时针,则旋转点顺序为逆时针。

判断多边形是否为简单多边形

上述多边形点顺序检测需要一个先决条件:Polygon必须[……]

继续阅读

Read More
| by YoungTimes | No comments

判断点位于有向线段的左侧或者右侧

如果r位于有向线段pq的左侧返回CGAL::LEFT_TURN;如果r位于有向线段pq的右侧返回CGAL::RIGHT_TURN;如果r与有向线段pq共线返回CGAL::COLLINEAR。

如果u和v是left turn关系返回CGAL::LEFT_TURN;如果如果u和v是righ[……]

继续阅读

Read More