| by msbeta | 2 comments

计算几何-凸包(Convex Hull)

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

凸的定义

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

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

继续阅读

Read More
| by msbeta | No comments

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

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

1.问题描述

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

2.问题解法

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

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

继续阅读

Read More
| by msbeta | No comments

计算几何-最近点对问题

1.问题描述

最近点对问题是指求解平面点集中距离最近的两个点间的问题。

2.蛮力求解法

对平面中的所有点两两计算距离,然后通过比较获取最小距离。在具体的计算过程,可以通过一定的策略优化,比如避免计算A与B的距离和B与A的距离这样的重复计算,计算距离不用开方等。但总体的时间复杂度为O[……]

继续阅读

Read More
| by msbeta | No comments

计算几何-线段集的所有交点

1.问题描述

给定N条线段,计算这些线段彼此之间的所有交点。

2.Bentley Ottmann Algorithm

2.1 算法的前提假设:
a) 不存在两条线段的终点和交点有相同的x坐标;
b) 不存在多于两条的线段相交于一点;
c) 不存在两条线段完全相互重叠;

2.2 关键[……]

继续阅读

Read More
| by msbeta | No comments

计算几何-道格拉斯普克(Douglas-Peuker)算法

Douglas-Peukcer算法由D.Douglas和T.Peueker于1973年提出,是线状要素抽稀的经典算法。用它处理大量冗余的几何数据点,既可以达到数据量精简的目的,有可以在很大程度上保留几何形状的骨架。

算法的基本思路

将待处理曲线的首末点虚连一条直线,求所有中间点与直线的距[……]

继续阅读

Read More