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

计算几何-凸包(Convex Hull)

凸包(Convex Hull)是计算几何中的一个经典常用的算法。它解决的问题在于给定空间一堆离散的点,计算包含所有点的凸多边形。

凸的定义

凸是指图形内任意两点的连线都不经过图形内部。

计算凸包时要考虑一些特殊情况,比如凸包上多点重叠,凸包上多点共线,通常我们会倾向于用最少[……]

继续阅读

Read More
| by YoungTimes | No comments

计算几何-线扫描算法计算矩形并集面积

本文是扫描线算法的具体的应用。

1.问题描述

给定N个矩形,矩形的边均平行于X坐标轴或者Y坐标轴,矩形之间也可能存在互相压盖重叠,计算矩形并集的面积。

2.问题解法

矩形表示:[左下角点,右上角点]

将矩形按照X坐标排序,想象一个竖直的扫描线从左向右扫描,遇到矩形的左边[……]

继续阅读

Read More
  • 1
  • 2