下载文档原格式
自相交多边形的三角剖分-概述说明以及解释1.引言1.1 概述【概述】自相交多边形是指一个多边形内部的边与其他边相交或重叠的特殊情况。
与传统的凸多边形或凹多边形相比，自相交多边形具有更复杂的拓扑结构和几何特征。
在计算机图形学、计算几何和计算机辅助设计等领域，对于自相交多边形的处理一直是一个重要而具有挑战性的问题。
本文旨在探讨自相交多边形的三角剖分方法，即将自相交多边形分解为一系列三角形，以便于后续的计算和应用。
三角剖分是将一个多边形或多维几何体划分为若干个互不相交的三角形或四面体的过程，广泛应用于计算机图形学、有限元分析、三维建模等领域。
本文将首先介绍自相交多边形的定义及其与传统多边形的区别。
然后，我们将详细探讨三角剖分的概念及其在几何计算中的重要性。
接下来，我们会讨论自相交多边形的三角剖分方法，并对不同的算法进行比较和分析。
最后，我们将总结自相交多边形的三角剖分在实际应用中的意义，并展望未来的研究方向。
通过本文的阅读，读者将对自相交多边形的三角剖分有一个全面的了解，并能够应用相关算法解决类似问题。
本文的研究对于计算机图形学、计算几何和计算机辅助设计等领域的研究人员和从业者具有一定的参考价值。
1.2 文章结构文章结构部分的内容可以包括以下内容：本文主要分为三个部分：引言、正文和结论。
在引言部分，首先对文章的主题进行了概述，介绍了自相交多边形的三角剖分的主要内容。
然后，对整篇文章的结构进行了说明，明确了各个章节的主题和内容。
最后，介绍了本文的目的，即为了讨论自相交多边形的三角剖分的重要性和相关方法。
正文部分将详细介绍自相交多边形的定义以及三角剖分的概念。
首先，会给出自相交多边形的准确定义，并解释该定义的意义和应用。
然后，会介绍三角剖分的基本概念，包括如何将自相交多边形划分为一组不相交的三角形，以及如何选择合适的三角形进行剖分。
在结论部分，将强调自相交多边形的三角剖分的重要性，指出该方法对于解决自相交多边形相关问题的有效性和实用性。
基于点集凸包的Delaunay三角剖分实时算法研究作者：倪敏敏王会方来源：《价值工程》2015年第09期摘要：凸包作为计算几何的一种基本的数据结构，在计算几何设计方面有着十分重要的应用。
本文采用坐标及单映射的算法来构建平面散乱点集的凸包。
而点集的Delaunay三角化对三维曲面重构有着十分重要的应用，由于Voronoi图和Delaunay三角化的对偶性，一般通过构建点集的Voronoi图来构建Delaunay三角网，本文直接构建Delaunay三角剖分，该算法原理简单，稳定，易实现，尤其适合数据点较少的点集。
关键词：单映射；对偶性；凸包；Delaunay三角剖分中图分类号：TP306.1 文献标识码：A 文章编号：1006-4311（2015）09-0317-020 引言凸包，就是包含点集中所有点的封闭的最小凸多边形，使得点集中任意两个点的连线都在该多边形内部。
构建凸包通常要解决两个问题：其一，是要从大量的离散点中判断出哪些点是要求的凸包的顶点；其二，是要解决这些凸包顶点的链接关系。
要解决这两个问题所需的时间复杂度至少为O（n logn），其中n为参加构建凸包离散点的个数。
显而易见，要提高计算速度就必须减少参加构建凸包的离散点的数目[1]。
二维平面最简单的几何体是三角形，而三维空间最简单的是四面体。
Delaunay网由于其独特的数学性质，是数学分析的有力工具，是GIS 中DTM模型的一个重要表示方法和分析处理手段[2]。
1 平面凸包构建算法在通常情况下，平面点集的凸包只是由其中的一部分点构成的，而其余的大部分点都是存在于凸包的内部，这就使得可以通过减少参加构建凸包的离散点数目来提高计算速度，即快速凸包法[3]，从而避免了逐点插入法构建点集凸包的冗余繁琐，尤其是在有大量数据点的情况下并且在确定凸包顶点的同时也能判断出非凸包顶点。
1.1 判断点在多边形内外的法则判断一个点与一已知多边形的位置关系可以根据待判断点与多边形各个顶点之间的夹角矢量和来判断[4]。
点云重建与三角剖分在计算机图形学中，点云重建和三角剖分都是非常重要的概念。
点云重建是指将一组离散的点云数据转化为连续的三维模型，而三角剖分则是将三维模型分割成许多小的三角形，以便进行三维建模、渲染等操作。
本文主要介绍这两个概念的基本原理及应用。
一、点云重建1.1 点云数据点云数据是由许多个三维坐标点组成的数据集。
在数字化采集现实物体的过程中，我们通常使用光学扫描、激光雷达等技术来获取物体表面上的点云数据。
点云数据虽然能够精确的描述物体表面的形状、大小等信息，但是这些点云数据通常是非常稀疏的，不连续的。
1.2 点云重建原理点云重建是将离散的、不连续的点云数据转化为连续的三维模型的过程。
常用的点云重建方法包括基于体素的重建、基于网格的重建和基于光滑曲面的重建等。
基于体素的重建：将点云数据以立方体体素的形式进行离散化处理，再通过光滑、修补等处理方式，将其转化为连续的三维模型。
基于网格的重建：将点云数据经过网格化处理，形成一个三角网格，再通过网格修补、平滑等技术，将其转化为连续的三维模型。
基于光滑曲面的重建：通过对点云数据点之间的距离、法向、曲率等特征进行分析，生成光滑曲面，再通过形成曲面网格的方式，将其转化为三维模型。
1.3 点云重建应用点云重建通常被应用于数字艺术、虚拟现实、医学图像处理、三维打印等领域。
例如，在虚拟现实游戏中，点云重建技术可以将真实的场景通过点云数据转化为三维模型，使得玩家更加沉浸在游戏中。
二、三角剖分2.1 三角剖分定义三角剖分是将多边形分割为许多小的三角形的过程。
由于三角形是计算机图形学中最基本的图形，因此将多边形分割为三角形可以更好地进行三维建模、渲染、检测碰撞等操作。
2.2 三角剖分算法常用的三角剖分算法包括离散点三角化算法、Delaunay 三角剖分算法等。
离散点三角化算法：将多边形上的各个顶点对应的离散坐标映射到一个坐标系中，再通过三角剖分算法将整个多边形进行分割。
Delaunay 三角剖分算法：该算法是目前应用最广泛的三角剖分算法之一，其主要思路是依据一组点云数据生成一个最大化的空圆内部的三角剖分，从而满足三角形的最优性和连通性。
delaunay三角剖分算法流程下载温馨提示:该文档是我店铺精心编制而成，希望大家下载以后，能够帮助大家解决实际的问题。
文档下载后可定制随意修改，请根据实际需要进行相应的调整和使用，谢谢!并且，本店铺为大家提供各种各样类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，如想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by theeditor.I hope that after you download them,they can help yousolve practical problems. The document can be customized andmodified after downloading,please adjust and use it according toactual needs, thank you!In addition, our shop provides you with various types ofpractical materials,such as educational essays, diaryappreciation,sentence excerpts,ancient poems,classic articles,topic composition,work summary,word parsing,copy excerpts,other materials and so on,want to know different data formats andwriting methods,please pay attention!Delaunay三角剖分算法的流程详解Delaunay三角剖分是一种在二维空间中将点集划分为三角形的方法，使得没有任何一个点位于其相邻三角形的内切圆内。
通用点线面集Delaunay三角剖分与动态编辑丁圣陶;王磊;殷勇;李成名【摘要】This paper summarizes and presents a kind of universal algorithm of generic points,lines and polygon Delaunay triangulation and dynamic editing. Discrete points, constrained line, polygon, polygon features with zone constraints (including point, line, polygon) Delaunay triangulation can be achieved. The outer boundary of Delaunay triangulation in generalis the convex bumps of discrete points, and the inner islands generally do not dig out. The algorithm in process of the Delaunay triangulation , realized the inner and outer boundary processing.%总结并提出了一种通用点线面集Delaunay三角剖分与动态编辑的统一算法.可以实现离散点的Delaunay 三角剖分,约束线、面的Delaunay三角剖分,任意多边形内带特征约束(包括点、线、面)的三角剖分,一般Delaunay三角剖分的外边界都是其离散点集的凸包,且内岛屿一般没有挖掉,本算法实现了Delaunay三角剖分时内、外边界的保界处理.【期刊名称】《遥感信息》【年(卷),期】2011(000)003【总页数】5页(P108-111,115)【关键词】Delaunay;三角剖分;编辑;保界处理【作者】丁圣陶;王磊;殷勇;李成名【作者单位】中国测绘科学研究院,北京100039;中国矿业大学,徐州221000;中国矿业大学,徐州221000;中国测绘科学研究院,北京100039;中国测绘科学研究院,北京100039【正文语种】中文【中图分类】P2081 引言目前Delaunay不规则三角网(Delaunay Triangular Irregular Network,D-TIN)广泛用来实现二维离散数据域的剖分与建模。
三角布点法在计算机图形学中的应用三角布点法，也被称为Delaunay三角剖分，是一种在计算机图形学领域中常用的算法。
它被广泛应用于计算机图形学、计算机视觉、地理信息系统、计算机辅助设计等领域。
什么是三角布点法？三角布点法是一种将给定的点集进行三角剖分的方法。
它通过连接点集中的各个点，生成一组不相交的三角形，这些三角形的顶点正好是原始点集中的点。
在三角布点法中，通常会使用一些准则来选择最优的三角剖分结果。
其中最著名的准则是Delaunay准则。
Delaunay准则Delaunay准则是三角布点法中最重要的准则之一。
基于Delaunay准则进行三角剖分时，要求连接每个三角形的外接圆不包含任何其他点。
也就是说，在Delaunay三角剖分中，构成每个三角形的三个点的外接圆不应包含点集中的其他点。
这样的剖分结果被视为最优的结果，因为它们能够最大限度地保持三角形的质量。
三角布点法的操作步骤三角布点法的操作步骤相对简单直观，主要包括以下几个步骤：1.点集准备：收集和准备要进行三角剖分的点集。
2.边界处理：根据实际需求，对点集的边界进行处理，以确保剖分结果满足外部边界的要求。
3.三角剖分：基于Delaunay准则，进行三角剖分操作。
可以使用不同的算法实现三角剖分。
4.结果优化：对剖分结果进行优化操作，以获得更好的剖分质量。
5.结果应用：根据具体需求，将获得的三角剖分结果应用于相关领域，例如计算机图形学中的形状重建、地理信息系统中的地形建模等。
三角布点法的应用领域三角布点法在计算机图形学领域有着广泛的应用。
它可以用于生成网格模型，进行形状重建、地形建模、物理模拟等操作。
此外，三角布点法还能够用于处理离散数据，例如医学影像数据的处理和分析。
在计算机视觉领域，三角布点法可以用于图像配准、三维重建、特征提取等任务。
其能够将离散的像素点或特征点进行连续的拟合和插值生成三角形网格，从而实现图像的处理和分析。
在地理信息系统中，三角布点法可以用于地形建模和地理数据可视化。
用VC语言实现任意多边形的Delaunay完全三角剖分算法①涂治红 桑农(华中科技大学图像识别与人工智能研究所,图像识别与智能控制国家教委重点实验室 武汉 430074)摘 要多边形三角剖分是计算几何的一个几何基元,它可以简化问题规模,在计算机图形学、模式识别等方面有重要的应用。
本文针对已有的Delaunay三角剖分算法的不足,提出新算法,并采用Visual C语言MFC类进行链表的管理,使得编程容易实现。
整个算法简洁通用。
最后给出了在实际中的应用。
关键词:任意多边形 Delaunay三角剖分 链表 MFC类中图分类号:TP301.6Delaunay T riangulation Algorithm of Arbitrary Polygons with Visual C LanguageTu Zhihong S ang N ong(Institute for Pattern Recognition and Artificial Intelligence,HUST,State Education Committee K ey Lab for Image Processing and Intelligent Control,Wuhan430074)Abstract:Triangulation of arbitary polygons is geometric primitives of computational geometry.It can predigest,dimensions. There are so many applications in graphics,pattern recognition and so on.This paper proposes an improved algorithm of Delaunay triangulation of the arbitrary polygon.The programming with Visual C language is relatively simple by using the MFC function to manage the lists.This algorithm is concise and general.The application of this algorithm is presented.K ey w ords:arbitrary polygon,Delaunay triangulation,list,MFCClass number:TP301.61 引言在计算机三维曲面造型,有限元计算和模式识别等领域里,经常要解决平面多边形的三角剖分问题。
计 算 机 与 现 代 化2004年第 5期JISUANJI YU XIANDAIHUA总第 105期文章编号 :100622475(2004)0520007203基于点的三角形构网算法及等值线自动生成方法郑盛贵 ,颜七笙 ,黄临平(东华理工学院 ,江西 抚州 344000)摘要 :总结了各种等值线生成的方法及特点 ,详细阐述直接利用三角形网格生成等值线的原理、实现方法 ,独立开发出基 于 VC γγ的 Contour 绘图类 ,并嵌入电磁资料处理系统软件 ,为电磁资料的等值线可视化表示提供了便利。
关键词 :三角网 ;等值线 ;程序实现 中图分类号 :TP31 文献标识码 :AAlgorithm of Triangle Constructed Grid Based on Points andMethod of Automatically Establishment ContourZHENG Sheng 2gui ,QAN Qi 2sheng ,HUANGLin 2ping(East China Institute of Technology ,Fuzhou 344000 ,China)Abstract :The characteristics and approaches of generating contour are summarized ,the theory and approache of using triangle grid gener 2 ating contour directly are described in detail. The Visual C γγ contour plot class is developed and is embedded in the system of electromagnetic data processing ,thus it provides great convenience for the visualization of contour of electromagnetic data. Key words :triangular grid;contour tracing;programming realization绘制等值线是对大量离散的、又具有一定规律的几何 1 概 述量值或物理量值 ,用数学的方法插值变换成图的过 1. 1 基于点的构网算法程。
一种平面区域散乱点集的三角剖分方法
陈慧群
【期刊名称】《机械》
【年(卷),期】2006(0)S1
【摘要】基于 Delaunay 三角化技术,提出一种对任意平面区域生成三角网格的全自动生成算法。
此算法具有运行快速,构造网格质量好、区域适应性强等优点。
算法包括对散乱数据点排序、三角剖分及网格优化处理等,最后给出的实例也证明了该算法的可靠性和实用性。
【总页数】2页(P59-60)
【关键词】平面区域;散乱点纂;Delaunay;三角剖分
【作者】陈慧群
【作者单位】汕头大学机械电子工程系
【正文语种】中文
【中图分类】TP391.7
【相关文献】
1.平面散点集Delaunay三角剖分的一种高效方法 [J], 周杰;丁贤荣;汪德爟
2.三维稀疏散乱点集的直接三角剖分新方法 [J], 史松伟;任秉银
3.一种新的平面点集三角剖分算法 [J], 周知;刘润涛
4.平面散乱点集的Delaunay三角剖分算法 [J], 唐琦;达飞鹏
因版权原因，仅展示原文概要，查看原文内容请购买。
三角剖分插值
三角剖分插值是将给定的二维平面点集按照一定的规则划分成一系列的三角形，并根据这些三角形的特性进行插值操作。
三角剖分插值常用于地理信息系统、计算机图形学等领域。
三角剖分插值的步骤如下：
1. 构建三角剖分：根据给定的二维平面点集，按照一定的规则（例如Delaunay三角剖分）构建一系列的三角形。
构建三角剖分的目标是保证任意两个不相邻三角形的外接圆不包含其他点。
2. 插值计算：对于给定的待插值点，找出其所在的三角形，并根据该三角形的顶点的属性值进行插值计算。
插值方法可以使用线性插值、双线性插值、三次插值等方法。
3. 绘制结果：根据插值计算的结果，将插值点和原始点一起绘制在二维平面上，形成一张插值网格或等值线图。
三角剖分插值的优点是可以在不规则的点集上进行插值计算，并能够较好地保持原始数据的特性。
缺点是对于大规模点集的计算性能要求较高，并且插值结果可能存在一些不可避免的误差。
因此，在实际应用中需要根据具体的需求和数据特点选择合适的插值方法和算法。
第24卷 第2期2004年2月北京理工大学学报T r ansactions of Beijing Instit ute o f T echnolog y V ol.24 N o.2F eb.2004 文章编号:1001-0645(2004)02-0129-04平面点线集三角剖分的扫描算法周培德(北京理工大学信息科学技术学院计算机科学工程系,北京 100081)摘 要:提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O (N lb N ),其中N 是点线集中点的数目与线段端点数之和.关键词:散乱点线集;三角剖分;平面扫描;算法;时间复杂性中图分类号:T P 301.6 文献标识码:ASweeping Algorithm for Triangulation of Plane Point -Line SetZHOU Pei-de(Depar tment of Co mputer Science and Engineer ing ,School o f Infor matio n Science and T echno lo gy ,Beijing Instit ut e ofT echno lo gy ,Beijing 100081,China)Abstract :Sw eeping alg orithm is presented fo r the tr iangulation of plane point -line set .T he algor ithm m akes use of the idea of plane sw eeping .When the sw eep -line reaches it ,the event -po int w ill be dealt w ith,viz.,the event-point is connected w ith so me points sw ept and thus the sw ept regions are triang ulated.When the sw eep-line r eaches the leftmost event-point,the point w ill be dealt w ith ,and the triang ulation of the plane point -line set is accom plished .It is prov ed in detail that the time co mplex ities o f the alg orithm is O (N lb N ),w here N is the sum of the num ber of points and the num ber of line-seg ment endpoints w ithin the point-line set.Key words :debunching point-line set;triang ulation;plane sw eep;alg orithm;tim e co mplex ity 收稿日期:20030321作者简介:周培德(1941-),男,教授. 平面点集三角剖分问题是计算几何中的一个重要问题,它是从许多实际问题中提出来的,至今,人们已研究了求解该问题的许多算法,其中以Delaunay 算法最为著名.将平面点集中的某些点组成点对并满足某些特殊关系,比如它们为平面线段的两个端点,而另外一些点仍为孤立点,这样便构成点线集.平面点集三角剖分问题可以转换为平面点线集的三角剖分问题,并且它们具有相同的时间复杂性下界.平面点线集三角剖分问题要求三角形的三条边或为点线集中的线段,或为点线集中不同线段端点的连线,或为点线集中点与线段端点的连线,或为点线集中点与点的连线.三角形的顶点为点线集中的点或线段端点.另外还要求连线与连线,连线与点线集中线段均不相交.给定的平面点线集中线段互不相交(线段端点处相交除外).不难看出,平面散乱点线集三角剖分问题是平面点集三角剖分问题的一个特殊情况.按照常规,求解平面点集三角剖分的算法(比如Delaunay 三角剖分算法)可以用于平面散乱点线集的三角剖分.但在平面点集三角剖分的算法中如何保证点线集中的线段必是三角形的一条边,以及连线与点线集中线段不相交.只要解决这个问题就可以实现点线集的三角剖分.目前解决这个问题的算法就是先将点(端点)集三角剖分,然后逐条线段进行调整,即删去与线段相交的连线,再添加某些新连线.Lo S.H.提出的方法适用于平面非凸封闭域[1].其思想是,在平面域内先生成内部结点,然后将内部结点与边界结点连接生成一组三角形,并不断向前推进,直至整个内域被三角剖分.近几年来,国内一些学者提出了求解有约束条件的Delaunay三角剖分算法[2,3],其思想与Lo S.H.提出的算法类似,也是解决平面非凸封闭域三角剖分问题.作者提出的算法不是针对平面非凸封闭域,而是针对平面任意点线集.利用平面扫描技术设计求解该问题的一种新算法,可以用来解决平面任意点线集的三角剖分问题.此外,作者为求解平面散乱线段集三角剖分问题设计了两个算法[4],这些算法也可求解这里的问题.与平面点集三角剖分问题类似,对平面散乱点线集三角剖分问题可以提出一些附加条件,比如要求三角形的最小内角最大化;三角剖分边长之和最小化,即最小权三角剖分.1 概念与算法思想用y轴自右向左移动的方法可以对平面上的散乱点线集建立全序关系集T[5,6].开始时T为空集, y轴左移遇到线段s1的右端点s1R或者p1时,将s1或p1加入T(也可以用二叉树表示y轴的移动过程[6]).y轴左移遇到线段s1的左端点s1L时,从T中删去s1.T中s1的上、下相邻线段的概念.设s1,s2,s3是平面上的3条线段,s1上存在一点a,过点a作垂线l,l与s2,s3分别交于b,c,并且b y<a y<c y,则称s3,s2为s1在a点处的上、下相邻线段,如图1所示.如果s1收缩成一点p,则同样定义s3,s2为点p的上、下相邻线段.断层折线的概念.图2中,s1,s2,…,s6是给定的线段,虚线是线段端点的连线,则连线f a,ab,bc,cd 与de构成扫描过程中的断层折线,用E表示.点a 是s1的右端点,并将E划分为两个子断层折线:其中1条折线由f a组成,另一条折线由ab,bc,cd与de 组成.点a是线段s1的端点,s1称为a的顶点线段.线段s6的右端点g与第2条线折线中顶点连接时,要求连线与第2条折线中线段不相交,此条件称为不相交条件,记为NI.点p与E中顶点连接时,也要求满足条件NI.图1 相邻线段Fig.1 Ad jacent segmen ts图2 断层折线Fig.2 Fault b roken line算法的思想.首先将点线集中线段的端点及点线集中的点按其x,y坐标排序.然后设想有一条垂直x轴的直线l(即y轴)由右向左扫描,当l达到线段s右端点s R或点p(称为事件点)时,将该线段s 或点p插入数据结构T中,并判定T中与s或p相邻的线段s1(上相邻)、s2(下相邻),连接s的右端点s R或p与s1,s2的右端点,这些连线构成断层折线E.类似处理l达到线段s左端点s L(事件点)时的情况.随着l的左移,E不断被修改,扫过的区域被三角剖分.当l达到最左线段的左端点或最左的点p 时,连接该左端点或点p与E的某些顶点,便完成了点线集三角剖分的工作.这种方法的优点是只考虑当前事件点能与E中哪些点连接,减少了运算次数,从而降低了时间复杂性.2 算法描述算法(平面点线集三角剖分的扫描算法).输入 平面上点线集S={s1,s2,…,s n,p1,p2,…,p m},线段s i的左、右端点s i L,s i R的x,y坐标,i= l,n.点p i的x,y坐标,i=l,m.输出 平面三角形集合T1={t1,t2,…,t k},各三角形的顶点为线段s i的端点(i=l,n)或点p i(i=130北京理工大学学报第24卷 l,m).边为s i或者s j(i,j=l,n,i≠j)端点的连线,端点与点p j(j=l,m)的连线,点p j与p k(j,k=l,m, j≠k)的连线.边与边之间不相交(顶点处相交除外).步1 将m个点p j及n条线段端点按其x,y 坐标排序.步2 断层折线E←§,F←§.F为存储扫描过程中已产生的连线.步3 垂直扫描线l由右向左移动,遇到线段s 的右端点同时又是另一条线段s″左端点时,s插入T,并从T中删去s″.转步3.垂直扫描线l由右向左移动,当遇到线段s的右端点s R或点p时,E←s R∨p,s或p插入数据结构T.在T中寻找s或p的上、下相邻线段.从T中删去p.如果s或p在T中没有上、下相邻线段∧E= s R∨p,则转步3或步4.如果s或p在T中没有上、下相邻线段∧E=1个s R1个点p∨两个s R∨两个点p,则连接E中点,修改E和F.转步3或步4.如果s或p在T中没有上、下相邻线段∧E中至少有一条边,则将s R或p与E的顶点连接(满足NI条件),修改E和F.转步3或步4.如果(s1,s2是s或p的上、下相邻线段∨E=s′)∧(s R x<s i R x∨p x<s i R x),则连接s R与s i R或p与s i R (NI成立),i=1,2.s R或p与E的顶点连接(NI成立).修改E和F.转步3、步4或步5.步4 当遇到s的左端点s L或点p时,E←s L∨p,s′←s,E←s′,F←s′.在T中寻找s的上、下相邻线段.从T中删去s或p.如果s或p在T中没有上、下相邻线段∧E= s′,则转步3或步4.如果s或p在T中没有上、下相邻线段∧E中至少有一条边,则将s L或p与E的顶点连接(NI成立).修改E和F.转步3、步4或步6.如果(上、下相邻线段是s′1,s′2)∧(s L x<s′i R x∨p x<s′i R x),则连接s L与s′i R或p与s′i R(NI成立),修改E和F.连接s L或p与E的顶点(NI成立),修改E 和F.转步4或步5.如果(上、下相邻线段是s′1,s′2)∧(s L x<s′i L x∨p x<s′i L x),则连接s L与s′i L或p与s′i L(NI成立),修改E和F.连接s L或p与E的顶点(NI成立),修改E 和F.转步4或步5.步5 遇到线段s的右端点s R或点p时,将s 或p插入T,在T中寻找s或p的上、下相邻线段,设为s1,s2.连接s R或p与E的顶点(NI成立).修改E和F.转步4或步5.步6 当l移出点线集时,输出F′,F′=F∪{s1,s2,…,s n}.终止.说明:“转步3或步4”意为:满足步3条件则转步3,满足步4条件则转步4.其它类似情况含义相同.算法中,修改E和F时采用四边形取较短对角线的方法,可以使三角剖分的各三角形边长之和(1条边的长度只计数1次)优化.3 正确性与复杂性平面扫描算法将m个点和n条线段端点按其x,y坐标排序.扫描线l采用由右向左的方向进行移动,遇到事件点(点或线段端点)便停止移动.在事件点s R或p处,算法在找到线段或点p的上、下相邻线段s1,s2,并且判断s R x<s i R x或p x<s i R x成立时,连接s R与s i R或p与s i R,并且满足NI条件.算法类似处理事件点s L.每处理一次事件点,算法便修改相应的子断层折线.断层折线E被右端点为E顶点的线段,分割为若干个子断层折线,E=E1∪E2∪…∪E r+1,其中r为右端点是E顶点的线段数目.扫描线l达到s R(s L)或点p时,连接s R(s L)或点p与E的相应顶点,即s R(s L)或p只与s1,s2(s′1,s′2)之间的E顶点连接,并且NI条件成立.然后修改由s1与s2或者s′1与s′2所界定的子断层折线.这时,算法已将s1与s2或者s′1与s′2所界定的部分区域三角剖分.随着扫描线l的左移,由s1与s2或者s′1与s′2所界定的区域均被三角剖分.由于事件点是由点p i和线段端点(i=l,m)构成的,所以算法无一遗漏地划分相关区域,即点线集凸壳所围区域.并且由算法的执行过程,可知每个三角形的顶点都是点线集中的点或线段端点,而三角形的边不是点线集中线段就是点线集中线段端点的连线,或者端点与点、点与点的连线.因此算法正确地产生了所需要的三角剖分.定理 设点线集中点与线段端点数之和为N,则算法的时间复杂性是O(N lb N).证明 算法的步1耗费O(N lb N)时间进行排序;步2用常数时间;步3中扫描线停于右端点或点p i时,利用线段端点及点的x,y坐标已排序的结果和二叉树搜索技术,至多在O(lb N)时间内可以找到上、下相邻线段s1与s2.为了分析算法其它步骤的131 第2期周培德:平面点线集三角剖分的扫描算法时间耗费,假设点和线段分布在k 层上(k <N ),每层点数与线段端点数之和分别为m 1,m 2,…,m k ,并且∑ki =1m i =N ,1≤m i ≤n -1.如图3所示.图3 复杂性证明示意图Fig .3 Illu strative diagram for a proof of complexity算法处理第k 层的时间耗费为(m k -1)+m k lb N .算法处理第k -1层的时间耗费至多为m k +m k -1lb N +2(m k -1-1).算法处理第k -2层的时间耗费至多为m k -1+m k -2lb N +2(m k -2-1).…算法处理第1层的时间耗费至多为m 2+m 1lb N +2(m 1-1).上述表达式求和得到2m k +m k -1+…+m 2+(m k +m k -1+…+m 1)lb N +2[(m k -1+m k -2+…+m 1)-k ]=N -m 1+N lb N +2[N -m k -k ]≤3N +N lb N =O (N lb N ).算法的时间复杂性为O (N lb N )+O (N lb N )=O (N lb N ).图4 例1Fig.4 Example 14 应用举例图4中,n =6,m =4,即点线集由6条线段和4个点组成.应用作者给出的算法得到点线集的三角剖分,其中粗线是给定的线段,细线为增加的连线.图5中,n =6,m =32,即点线集由6条线段和32个点组成,并且6条线段构成一条折线.应用本文中算法得到该点线集的三角剖分,图中粗线是给定的线段,细线为增加的连线.图5 例2Fig.5 Ex amp le 2作者利用平面扫描思想设计求解平面散乱点线集三角剖分问题的算法,其优点是时间复杂性低,易于编程,且对大输入数据N 不易出错.本文中提出的算法为平面散乱点线集三角剖分问题的解决提供了一条新的途径.参考文献:[1] L o S H.Delaunay t riang ulat ion o f non-co nvex pla nardo mains [J ].Inter nat ional Jo urnal for N umerical M etho ds in Engineer ing ,1989,28:2695-2707.[2] 闵卫东,唐泽圣.二维任意域内点集的Delaunay 三角剖分的研究[J].计算机学报,1995,18(5):357-364.M inW eido ng ,T angZesheng .T heD elav na ytr iang ulatio n of a po int set w ithin an arbit rar y 2D domain [J].Chinese Jo ur nal of Computers,1995,18(5):357-364.(in Chinese)[3] 周晓云,刘慎权.实现约束D elaunay 三角剖分的健壮算法[J].计算机学报,1996,19(8):615-624.Zho u Xiao yun,L iu Shenquan.A r obust alg or ithm for constr ained D elaunay t ria ng ulation [J ].ChineseJournal o f Co mputer s ,1996,19(8):615-624.(inChinese)[4] 周培德.平面线段集三角剖分的算法[J].计算机工程与科学,2003,25(1):20-22.Zhou P eide .A lg or ithms for the tr iangulatio n of plane line-segment stes [J ].Computer Eng ineer ing &Science ,2003,25(1):20-22.(in Chinese )[5] 周培德.计算几何[M ].北京:清华大学出版社,2000.Zhou P eide .Computatio nal geo metr y [M ].Beijing :T sing hua U niver sity P ress,2000.(in Chinese)[6] 周培德.算法设计与分析[M ].北京:机械工业出版社,1992.Zhou Peide .T he desig n and analysis o f alg or ithms[M ].Beijing :China M achine Pr ess,1992.(inChinese )132北京理工大学学报第24卷 。
