| 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
| by YoungTimes | No comments

多边形求并集(Union)

CGAL计算多边形并集

CGAL提供一系列的join函数用于计算两个Polygon的并集(Union)。

Type1和Type2支持的类型如下,简单的说就是,它支持计算任意简单多边形和带洞(hole)多边形求并集。

Type1Type2Polygon_2Polygon_2Pol[……]

继续阅读

Read More
| by YoungTimes | No comments

CGAL实现多边形凸分解

凹多边形的处理往往比较复杂,难以使用,所以我们往往需要将非凸多边形,甚至带空洞(Hole)的多边形拆解为凸多边形。

下图为带空洞的多边形(Polygon With Hole)。

我们的目标是使用CGAL将其分解(decompose)为如下的多个凸多边形。

1. CGAL中的[……]

继续阅读

Read More
| by YoungTimes | No comments

CGAL计算多边形的对称差 (Symmetric difference)

数学上,两个集合的对称差是只属于其中一个集合,而不属于另一个集合的元素组成的集合。 集合论中的这个运算相当于布尔逻辑中的异或运算。

Symmetric Difference实现

下面我们使用两个带空洞(Hole)的多边形为例,看下symmetric difference的具[……]

继续阅读

Read More