使用离心点优化Delaunay三角剖分的新型Steiner点

4星 · 超过85%的资源需积分: 10 95 浏览量更新于2024-09-15 收藏 776KB PDF 举报

"这篇文章是关于计算几何领域的一个研究，标题为‘Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations’，作者是Alper Üngör，发表在《Computational Geometry: Theory and Applications》杂志的2009年42期，第109-118页。文章主要讨论了一种新的Steiner点类型——"off-centers"，用于改进二维Delaunay三角剖分的质量。该研究是在P. Agarwal的指导下进行的，并于2008年6月被接受发表，同年7月在线发布。" 在计算几何中，Delaunay三角剖分是一种重要的数据结构，它保证了每个三角形的内切圆不包含任何输入点（也称为站点）。通常，Delaunay三角剖分的优化目标包括提高质量（如确保所有角度的最小值）和最小化边长的差异。Steiner点是一种额外的中间点，它们不来自于原始输入点集，但可以用于改善三角剖分的质量。本文提出的新类型Steiner点——off-center，是作为传统circumcenters（重心）的替代品。Circumcenters是三角形三个顶点的外接圆心，而off-center则可能提供一种更有效的方法来改善三角形的质量。作者设计了一种基于off-center迭代插入的Delaunay细化算法，这种算法在理论上保证了与已知最佳细化算法相同的质量和大小优化保证。在实际应用中，off-center算法表现出优于传统方法的特性：它插入的Steiner点更少，运行速度更快，并且生成的三角剖分更小。这在处理大规模数据或对内存和计算效率有高要求的场景下具有显著优势。此外，减少Steiner点的数量可以降低存储需求，同时保持或甚至提升三角剖分的质量，这对于图形渲染、物理模拟和地理信息系统等应用至关重要。这项工作为计算几何领域提供了一个新的工具，即off-center Steiner点，它有望在Delaunay三角剖分的优化问题上取得突破，同时保持或改善算法的效率。对于需要高效、高质量Delaunay三角剖分的软件开发者和研究人员来说，这是一个重要的进展。

Computational Geometry 42 (2009) 109–118

Contents lists available at ScienceDirect

Computational Geometry: Theory and Applications

www.elsevier.com/locate/comgeo

Off-centers: A new type of Steiner points for computing size-optimal

quality-guaranteed Delaunay triangulations

Alper Üngör

Department of Computer & Information Science & Engineering, University of Florida, USA

article info abstract

Article history:

Received 11 February 2007

Received in revised form 17 June 2008

Accepted 24 June 2008

Available online 3 July 2008

Communicated by P. Agarwal

Keywords:

Delaunay reﬁnement

Computational geometry

Triangulations

We introduce a new type of Steiner points, called off-centers, as an alternative to

circumcenters, to improve the quality of Delaunay triangulations in two dimensions. We

propose a new Delaunay reﬁnement algorithm based on iterative insertion of off-centers.

We show that this new algorithm has the same quality and size optimality guarantees of

the best known reﬁnement algorithms. In practice, however, the new algorithm inserts

fewer Steiner points, runs faster, and generates smaller triangulations than the best

previous algorithms. Performance improvements are signiﬁcant especially when user-

speciﬁed minimum angle is large, e.g., when the smallest angle in the output triangulation

is 30

◦

, the number of Steiner points is reduced by about 40%, while the mesh size is down

by about 30%. As a result of its shown beneﬁts, the algorithm described here has already

replaced the well-known circumcenter insertion algorithm of Ruppert and has been the

default quality triangulation method in the popular meshing software

Triangle.

1. Introduction

Triangulations (meshes consisting of triangles) are heavily used in many applications including engineering simulations,

computer-aided design, solid modeling, computer graphics, and scientiﬁc visualization. Most of these applications require

that the shape of the mesh elements are of good quality and that the size of the mesh is small. An element is said to be

good if its aspect ratio (circumradius over inradius) is bounded from above or its smallest angle is bounded from below.

Mesh element quality is critical in determining interpolation error in the applications and hence is an important factor in

the accuracy of simulations as well as the convergence speed. Mesh size, meaning the number of elements, is also a big

factor in the running time of the applications algorithm. Between two meshes with the same quality bound, the one with

fewer elements is preferred almost exclusively.

Among several types of domain discretizations, unstructured meshes, in particular Delaunay triangulations, are quite

popular due to their theoretical guarantees as well as their practical performance. Earliest algorithms that provide both size

optimality and quality guarantee used balanced quadtrees to generate ﬁrst a nicely spread point set and then the Delaunay

triangulation of these points [1]. Subsequently, Delaunay reﬁnement techniques are developed based on an incremental

point insertion strategy and provide the same theoretical guarantees [10]. Over the last decade, Delaunay reﬁnement has

become much more popular than the quadtree-based algorithms mostly due to its superior performance in generating

smaller meshes. Many versions of the Delaunay reﬁnement is suggested in the literature [2,6,8–11,13]. We attribute the large

amount of research on Delaunay reﬁnement to its impact on a wide range of applications. It is important to generalize the

E-mail address: ungor@cise.uﬂ.edu.

http://www-2.cs.cmu.edu/~quake/triangle.html.

0925-7721/$ – see front matter

doi:10.1016/j.comgeo.2008.06.002

下载后可阅读完整内容，剩余9页未读，立即下载

蜡烛花

粉丝: 3
资源: 56

使用离心点优化Delaunay三角剖分的新型Steiner点

STAR- Steiner-Tree Approximation in Relationship Graphs.pdf

用matlab，导入坐标点，并根据Steiner最短树性质，分解prim算法求出来的最小生成树MT

matlab写出下面代码：对于给定的n个坐标轴上的点A1，A2，……，An，使用Prim算法找出最小生成树MT。 根据Steiner最短树性质，分解MT成为n′棵子树（1≤n′≤n－1）。

用matlab根据Steiner最短树性质，分解prim算法求出来的最小生成树MT

steiner树问题的代码实现

简述一下这篇论文：Construction of All Multilayer Monolithic Rectilinear Steiner Minimum Trees on the 3D Hanan Grid for Monolithic 3D IC Routing

Steiner定理这是什么定理？

用matlab利用Steiner最短树性质，分解MT使之成为n'颗子树

基于C#的泰森多边形算法

python 最小斯坦纳树代码

最新资源

matlab写出下面代码：对于给定的n个坐标轴上的点A1，A2，……，An，使用Prim算法找出最小生成树MT。根据Steiner最短树性质，分解MT成为n′棵子树（1≤n′≤n－1）。