基本形状,多边形,三角
计算机越来越多地被用来解决几何问题。几何物体,如点、线和多边形,是各种重要应用的基础,并产生一系列有趣的问题和算法。几何算法在设计和分析系统建模物理对象、图形设计、医学和游戏开发中都很重要。一个设计物体的设计师有一种几何直觉。然而,这是几何编程的困难的一部分,因为某些“明显”的操作,你用铅笔做,如找到两条线的交点,需要非平凡的编程,以正确地用计算机来做。几何算法是一个有趣的研究领域,因为它具有很强的历史背景;几何是经典数学课题中最有价值的。甚至在柏拉图学院的大门上方也有这样的铭文:“不懂几何学的人,勿入此门。”
外科计算几何:
几何问题出现在医学物体建模,人体组织结构,医学成像,甚至计算机辅助手术。下图是人类皮层的表面模型。
线条和点
大多数较大尺度的几何规划依赖于在二维空间中定义的简单几何对象。基本对象是一个点,我们认为它是一对整数——“坐标”是通常的笛卡尔坐标系(尽管其他系统也有可能)。线段仅仅是两点之间最短的距离。然而,与线段不同,直线在两个方向上都是无限长的。这里我们只讨论平面上的线。
表示:
直线可以用点表示,也可以用方程表示。每条线都可以用一对点来完全描述 和 .它也可以用这种形式的方程来描述 ,在那里 是直线的斜率,也就是。 , 是 拦截。
然而,垂直线是一个问题,因为它们不能用这样的方程来描述,因为要除以零。这个方程 表示穿过的垂线 轴在点上 .这个问题可以用更一般的公式来避免
因此,我们可以设想线的两种可能的表示方式:点的表示方式或 上面的方程表示。让我们从表示代码中的一个点开始:
1 2 3 4 5 6 7 8 9 |
|
我们可以着手制定一个两点线的表示:
1 2 3 4 5 6 7 8 9 |
|
我们也可以很容易地实现a, b, c的形式。让我们称之为类么
:
1 2 3 4 5 6 7 8 9 |
|
这些方程和点形式可以使用如下函数进行转换:
1 2 3 4 5 6 7 8 9 |
|
多边形
多边形是由非相交线段组成的闭合链的一组点。闭合的意思是链的第一个顶点也是链的最后一个顶点。“不相交”的意思是两个线段只在它们的端点处接触。
多边形是描述大多数平面形状的基本要素。我们可以使用line类将多边形表示为一组直线。但这是不必要的,因为它们可以很容易地表示为一组坐标点。然后我们可以假设在
和
链中的点。因此,我们将它实现为一个简单的数组点
对象。
1 2 3 4 5 6 7 8 9 10 11 |
|
例如,我们可以把下面的三角形表示为
1 2 3>>>三角形=多边形([点(-1,3.),点(5,5),点(4,-2)))>>>打印(三角形)(-1,3.),(5,5),(4,-2)
欧几里得最短路径
欧几里得最短路径问题是计算几何中的一个问题:在欧几里得空间中给定一组多面体障碍和两个点,找出与任何障碍不相交的点之间的最短路径。
我们得到了出发位置 以及目标位置 ,我们假设它们在自由空间中。我们的目标是计算出最短的无碰撞路径 来 ,即不与任何障碍物内部相交的最短路径。注意,我们不能说最短路径,因为它不一定是唯一的。对于最短路径的存在,重要的是障碍是开放的集合;如果它们是封闭的,那么最短路径就不存在,因为总是可以通过靠近障碍物来缩短路径。
这并不一定是一条很短的路径,因为有些弧线是在距离很远的节点之间,而有些弧线则是在距离很近的节点之间。一个明显的改善会给每个弧对应的欧几里得长度重量段连接事件节点,并使用图中找到最短路径搜索算法加权图,如迪杰斯特拉算法或传播的波前从一个点,直到遇到另一个。虽然这可能会增加路径长度,但我们仍然没有得到最短路径。现在我们将在可见性图上讨论Dijkstra算法。
在三维(及更高维度)中,问题通常是NP-hard,但存在有效的近似算法,运行时间为多项式,基于在障碍边缘找到合适的点样本,并使用这些样本点执行可见性图计算的想法。
的能见度图 , ,障碍集是一个顶点为的图 , ,障碍顶点,顶点 和 由一条边连接,如果 和 是相互可见还是如果 是某种障碍的边缘。由此可知,最短路径的计算方法是先计算可见性图,然后用欧几里得长度标记每条边,再用Dijkstra算法计算最短路径。注意,可见性图不是平面的,因此可能包括 边缘。
Dijkstra(G,start)找到所有最短路径 最短路径(G,Li,Lf)使用Dijkstra算法来查找最短路径 来 .
12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
|