FIST-一种新的三角剖分算法资源-CSDN文库

需积分: 18 155 浏览量 2012-07-28 13:44:34 上传评论收藏 391KB PDF 举报

### FIST—一种新的三角剖分算法 #### 概述 FIST（Fast Industrial-Strength Triangulation）是一种专门用于多边形三角化的算法。它由Martin Held在奥地利萨尔茨堡大学计算机科学研究所开发，并在2003年提交至Algorithmica期刊。该算法的核心思想是通过反复“削耳”（Ear Clipping）来将多边形分解成一系列三角形，这些三角形共同构成原始多边形的三角剖分。 #### FIST的特点与优势 FIST的设计重点在于确保算法的可靠性、易于实现性和实际运行速度。为了达到这些目标，开发者采取了以下措施： 1. **完全可靠**：FIST能够处理任何类型的多边形输入数据，无论是简单的还是复杂的多边形。算法中内置了一系列启发式策略，当检测到输入多边形存在缺陷时，这些策略可以作为标准削耳过程的备份方案。 2. **易于实现**：FIST采用了ANSI C语言进行编写，这使得它能够轻松地被移植到不同的平台和环境中。此外，算法本身的设计简洁明了，便于理解和实现。 3. **实际运行速度快**：为了提高算法的实际运行效率，FIST还采用了几种加速技术，例如几何哈希（Geometric Hashing）和边界体积树（Bounding Volume Trees），这些技术可以显著加快削耳过程的速度。经过优化后，FIST的运行速度通常比其他流行的三角化代码更快。 #### FIST的工作原理 FIST的基本工作原理是通过不断识别并移除多边形中的凸角（即所谓的“耳朵”），逐步将多边形分割成三角形。具体步骤如下： 1. **初始化**：读入一个多边形作为输入。 2. **削耳过程**：寻找多边形中的“耳朵”，即一个凸角，其两边形成的角度小于180度。一旦找到一个耳朵，就将其对应的顶点移除，并用剩下的两个顶点与下一个或上一个顶点形成一个新的三角形。 3. **异常处理**：如果在削耳过程中遇到问题（例如输入多边形不是简单多边形或者存在重叠等），则激活预先设定的启发式策略来解决问题。 4. **优化**：为了提高效率，FIST还采用了几何哈希和边界体积树等技术，帮助快速定位耳朵位置，从而加速整个削耳过程。 5. **终止条件**：当多边形不能再找到可削除的耳朵时，三角化过程结束。 #### FIST的应用 FIST算法因其高效性和稳定性而被广泛应用于多个领域，尤其是在计算机图形学和三维建模中。例如，在工业图形包中用于三角化三维多面体的表面，以及被集成到Sun Microsystems的Java 3D实现中。此外，由于其可靠性和易于实现性，FIST也被广泛应用于教学和研究领域。 #### 结论 FIST作为一种新型的三角剖分算法，以其高效、稳定和易于实现的特点在多边形三角化领域占据了一席之地。通过采用先进的优化技术和启发式策略，FIST能够有效地解决各种复杂多边形的三角化问题，为计算机图形学和其他相关领域的应用提供了强大的支持。

资源推荐

资源详情

资源评论

FIST: Fast Industrial-Strength Triangulation

of Polygons



Martin Held

Institut f ur Computerwissenschaften

Universitat Salzburg

A-5020 Salzburg

Austria

[submitted to: Algorithmica] [March 25, 1998]

Abstract

We discuss a triangulation algorithm that is based on rep eatedly clipping ears of a

p olygon. The main fo cus of our work was on designing and engineering an algo-

rithm that is (1) completely reliable, (2) easy to implement, and (3) fast in practice.

The algorithm was implemented in ANSI C, based on oating-p oint arithmetic. Due

to a series of heuristics that get applied as a back-up for the standard ear-clipping

pro cess if the code detects deciencies in the input p olygon, our triangulation co de

can handle any typ e of p olygonal input data, be it simple or not. Based on our im-

plementation we rep ort on dierent strategies (geometric hashing, b ounding-volume

trees) for sp eeding up the ear-clipping pro cess in practice. The co de has b een tuned

accordingly, and cpu-time statistics do cument that it tends to b e faster than other

p opular triangulation co des. All engineering details that ensure the reliability and

eciency of the triangulation co de are describ ed in full detail. We also rep ort ex-

p erimental data on how dierent strategies for avoiding sliver triangles eect the

cpu-time consumption of the algorithm. Our co de, named FIST as an acronym for

fast industrial-strength triangulation, forms the core of a package for triangulating

the faces of 3D p olyhedra, and it has been successfully incorp orated into several

industrial graphics packages, including an implementation for Java 3D by Sun Mi-

crosystems.

Key words:

Polygon, triangulation, ear clipping, geometric hashing, reliability,

robustness, exp erimental analysis.



A preliminary version of this pap er is to appear as an extended abstract at CGI'98.

Email: held@cosy.sbg.ac.at. Most of this work was carried out while working at the Computational

Geometry Lab of SUNY Stony Bro ok, and was supported by grants from Sun Microsystems, and by NSF

Grant CCR-9504192.

1 Intro duction

1.1 Motivation

The triangulation of a p olygon is a basic building blo ck for many graphics applications.

For instance, high-sp eed rendering typically relies on polygonal and curved surfaces b eing

sub divided into triangles that can b e handled eciently by the graphics hardware. Tri-

angulating a p olygon also is a fundamental operation in computational geometry, and it

has received wide-spread interest over the last two decades, see Bern and Eppstein's recent

survey [11].

Through a series of improvements, the worst-case complexity of triangulating a p olygon

with

vertices has b een brought down from

(

) to the optimal

(

), achieved by

a seminal algorithm designed by Chazelle [16]. Algorithms with a slightly sup er-linear

exp ected complexity also are known, cf. Seidel's [40] randomized algorithm.

Virtually all published triangulation algorithms assume that the polygon is simple,

i.e., that the vertices of the p olygon are the only p oints of the plane that b elong to two

edges, and that no p oint of the plane b elongs to more than two edges. Due to the Jordan

curve theorem, a simple p olygon divides the plane into a well-dened interior and exterior.

Obviously, the requirement to b e simple prevents a p olygon from having self-intersections.

However, it also excludes so-called \degenerate" situations, such as an edge passing through

another vertex, zero-length edges, and edges that partially overlap.

While avoiding the hassles involved with handling \degenerate" or \illegal" cases, the

restriction to truly simple p olygons constitutes a ma jor road-blo ck for the practical appli-

cation of triangulation algorithms. Unfortunately, real-world polygons cannot b e assumed

to be truly simple p olygons that are in general p osition. Rather, real-world p olygons tend

to exhibit all types of deciencies, such as self-intersections, or island contours that overlap

with each other or with the outer b oundary.

We note that exact arithmetic do es not really help with the practical handling of

p olygons that are not simple. For a triangulation co de that tessellates the faces of a

p olyhedron and sends them to the subsequent rendering hardware it do es not matter

whether a polygon is classied as nearly degenerate but still simple, or as slightly self-

intersecting | in any case, the co de must not crash or lo op, and a reasonable triangulation

has to b e computed. And, of course, this triangulation has to b e computed without human

intervention.

This pap er presents an ecient triangulation algorithm that is able to cop e with any

form of p olygonal input data, be it simple or not. Sp ecically,



we described a

triangulation algorithm based on ear clipping

;



we give a

detailed discussion of reliability issues

related to the handling of \degen-

erate" or \illegal" p olygonal input, and explain how a robust and reliable code has

b een engineered; and



we provide a

thorough experimental analysis

of how to use geometric hashing in order

to make the algorithm competitive with algorithms that exhibit a better worst-case

b ehavior.

1.2 Survey of the Algorithm

In the sequel, a p olygon is denoted by

, and

stands for the number of its vertices.

As a convention, we include the interior of a polygon when referring to

. Unless stated

otherwise, we will assume that

is a simply-connected area, i.e., b ounded by one single

lo op of straight-line segments. The vertices are numbered in counter-clo ckwise orientation

and denoted by

; : : : ; v

. As usual, all vertex indices are taken mo dulo

We present an algorithm that triangulates a p olygon by searching for \ears" and \clip-

ping" them. As usual, three consecutive vertices

; v

are said to form an

ear

; v

is a diagonal of

. According to Meisters [33], every simple p olygon that

is not a triangle has at least two non-overlapping ears.

A straightforward implementation of a triangulation algorithm based on rep eatedly

clipping ears runs in

(

) time, with

(

) time sp ent on checking whether three subse-

quent vertices form an ear. A simple re-organization of the ear-nding pro cess allows to

check only

(

) ears, thus nding all ears in

(

) time, see [31, 36]. However, this com-

plexity still is to o high for practical applications. Whereas faces of a p olyhedron typically

have rather few vertices, applications in GIS may involve p olygons with several tens of

thousands of vertices.

We try to reduce the practical complexity of nding one ear by p erforming only lo cal

searches. Bounding-volume trees, as successfully used in our work on collision detection [30,

26], or, alternatively, regular grids are used for registering the p olygon under triangulation

and for pruning the search while testing for earity

. While any form of geometric hashing

do es not reduce the worst-case complexity, it helps a lot to reduce the practical running

time of the triangulation algorithm, as witnessed by our exp eriments.

The algorithm rst determines the orientation of the p olygon. Then it rep eatedly

clips ears of the p olygon until the polygon has b een transformed to a triangle and the

entire triangulation is known. The actual core of the algorithm is based on one predicate:

we only need to check the sidedness of three p oints. (In addition, a lexicographical sort

of the vertices of the p olygon is used.) We make sure that this primitive is always used

consistently. Furthermore, care has b een taken to ensure that degenerate cases are handled

correctly.

If the algorithm cannot nd any valid ear to clip | e.g., due to deciencies of the input

p olygon, or due to numerical errors | then it tries to restart the triangulation pro cess

by applying several heuristics. For instance, it checks whether subsequent edges of the

p olygon intersect, and applies a sp ecial rule in order to by-pass this deciency. Then, the

standard ear-clipping process is resumed again. Similarly, it tries to nd a diagonal that

splits the p olygon into two sub-p olygons, which are then again sub jected to the standard

ear-clipping process.

If everything fails, and no heuristic helps to reduce the number of vertices of the

p olygon, then the algorithm (temp orarily) go es into \desp erate mo de". It randomly picks

a convex vertex, and clips the corresponding \ear". If no convex vertex exists then a reex

vertex is chosen randomly. Thus, the more desp erate the co de gets the more aggressive

means are used for \nding" an ear or a diagonal, thereby always reducing the numb er of

vertices of

by at least one. This strategy allows the co de to produce triangulations that

degrade gracefully as the deciencies of the input p olygon get more serious. Of course, at

\Earity test" is the common nickname for the pro cess that tests whether a triple of consecutive vertices

forms an ear.

some p oint the old principle of \garbage in, garbage out" applies. However, the co de will

always output a triangulation that is top ologically valid.

The algorithm has b een implemented in C, and extended to handle multiply-connected

p olygons. The resulting software, called FIST as acronym for \Fast Industrial-Strength

Triangulation", has b een tested extensively, and we present statistics on a series of test

runs. Using synthetic test data generated by means of RPG [1, 2], we compared the cpu-

time consumption of FIST and to those of other p opular C co des: we compared it to

Narkhede and Mano cha's implementation [34, 35] of Seidel's algorithm [40], Shewchuk's

\Triangle" [43, 41], Sloan's implementation [45] of an ear-clipping algorithm, and to Saade's

implementation [39] of Toussaint's algorithm [47]. As witnessed by our tests, FIST is

comp etitive with the other co des, and even outperformed them in most tests.

This paper is accompanied by several color plates available on the WWW. Point your

browser to the WWW home-page [27] of FIST.

The remainder of this pap er is organized as follows. We discuss prior and related work

in the following subsection. Section 2 contains a presentation of the basic triangulation

algorithm. The next two sections, Section 3 and Section 4 discuss enhancements of the

basic algorithm for improving its sp eed and its reliability. Exp erimental results are given

in Section 5, and Section 6 rep orts on tests and experiments for determining the practical

reliability of the co de. The paper is concluded in Section 7.

1.3 Prior and Related Work

Most early triangulation algorithms try to nd a diagonal of the p olygon and then recurse

on the two resulting sub-polygons. Meisters [33] proved that every simple p olygon that is

not a triangle has at least two non-overlapping ears. Since nding an ear takes

(

) time in

the worst case, ear-clipping algorithms need at least

(

) time in the worst case. Several

(

) algorithms based on ear clipping have b een prop osed recently, see [31, 22, 36].

Garey et al. [25] were the rst to publish an

(

log

) triangulation algorithm. They

used a regularization scheme in order to partition a p olygon in

(

log

) time into mono-

tone sub-p olygons. Monotone sub-p olygons are afterwards triangulated in linear time by

rep eatedly clipping o convex corners (i.e., ears) of the polygon. See also the work by

Fournier and Montuno [24]. A completely dierent algorithm by Chazelle [15], based on

divide-and-conquer, also achieves an

(

log

) worst-case b ound.

The rst triangulation algorithm that is sensitive to the shap e of the p olygon was given

by Hertel and Mehlhorn [28]. Their algorithm achieves a complexity of

(

log

), where

denotes the number of reex vertices of the p olygon. See also the simple algorithm by

Kong et al. [31] which runs in

(



(

+ 1)) time.

The algorithm by Chazelle and Incerpi [17] also takes advantage of the shap e of the

p olygon. Their algorithm, which is based on trap ezoidal decompositions, runs in time

(

log

), where

is the sinuosity of the p olygon. (Roughly, the sinuosity of a p olygon

gives the numb er of times the p olygon's b oundary alternates b etween spirals of opp osite

direction.)

Toussaint's algorithm [47] is another algorithm that is shap e-dep endent. It runs in

time

(

), where

is the number of triangles of the triangulation that have three

neighb ors (i.e., that share no edge with the p olygon).

Seidel [40] describ ed a simple randomized incremental algorithm for triangulating p oly-

gons. Its exp ected complexity is

(

log

). Thus, its exp ected complexity is almost linear

for any simple p olygon. This algorithm rst incrementally computes a trap ezoidal decom-

p osition of the p olygon, by taking a random permutation of the edges of the p olygon and

inserting one segment at a time into this decomp osition. The numb er of trap ezoids is linear

, and Seidel proved that computing this trap ezoidal decomp osition takes

(

log

)

exp ected time if each p ermutation of the edges of the p olygon is equally likely. Based

on the trap ezoidal decomp osition a set of monotone p olygonal chains is obtained in lin-

ear time. Finally, these chains are triangulated in linear time by using the algorithm by

Fournier and Montuno [24].

An earlier randomized triangulation algorithm, also with

(

log

) expected com-

plexity, was published by Clarkson et al. [19]. See also the work by Devillers [20].

Tarjan and Van Wyk [46] were the rst to break the

(

log

) worst-case b ound.

Their algorithm runs in

(

log log

) time. A simpler algorithm that achieves the same

worst-case time b ound was later published by Kirkpatrick et al. [29].

Finally, Chazelle [16] ended the quest for a worst-case optimal triangulation algorithm.

His ingenious construction, based on coarse approximations of visibility maps, runs in

(

)

time. However, it seems to b e to o complicated to b e implemented successfully.

The situation is quite dierent when dealing with polygons in 3D. Call a 3D p olygon

triangulable if it has a triangulation which is not self-intersecting and which denes a

simply-connected 2-manifold. Then, Barequet et al. [6] show that the problem of deciding

whether a 3D p olygon is triangulable is

N P

-complete. Also, they give an

(

) algorithm

for determining a plane on which a pro jection of a given polygon is simple.

Related to the triangulation of a 3D p olygon is the linear interpolation of p olygonal

slices in 3D. Barequet and Sharir [8] use dynamic programming for determining a minimum-

area triangulation b etween two p olygonal slices. As is well known, dynamic programming

requires

(

) time and

(

) space. See also the work by Barequet et al. [9, 10, 7], and

Choi and Park [18].

A planar multiply-connected p olygon with

islands and a total of

edges can b e

triangulated in time

(

log

) by applying any of the standard techniques, such as plane

sweep or regularization. The b est b ound known for the worst-case complexity is achieved

by an algorithm due to Bar-Yehuda and Chazelle's [5], which runs in (near-optimal) time

(

log



Ronfard and Rossignac [38] describ e a nite-state machine that is able to handle p oly-

gons with islands. Their algorithm, called \o o ding", is similar in spirit to sweep-line

algorithms, but it sweeps only subparts (\gorges") of the p olygon at a time. This algo-

rithm was implemented at IBM, and the authors rep ort an average complexity of

(

with a worst-case complexity of

(

There seem to b e far more theoretical studies of triangulation algorithms than published

rep orts on actual implementations, anyway. Seidel's algorithm [40] got implemented by

Narkhede and Mano cha [34], and their co de is available publicly [35]. (Since its rst

publication, this co de has b een extended to handle p olygons with islands, and has b een

tuned in order to reduce its start-up cost.) An implementation of Toussaint's algorithm

[47] was carried out by Saade [39].

Sloan [45] implemented an

(

) triangulation algorithm based on ear clipping. His

algorithm also is able to swap diagonals in order to avoid skinny triangles, and can group

triangles into quadrangles.

Shewchuk [43] implemented \Triangle", a ne co de that computes Delaunay triangula-

tions and is able to p erform guaranteed-quality meshing. \Triangle" is based on geometric

剩余30页未读，继续阅读

评论收藏

内容反馈

mycug

粉丝: 3
资源: 24

FIST-一种新的三角剖分算法

简单多边形的三角剖分算法

三角剖分技术算法

2D三角剖分算法

VC实现三角剖分算法

平面三角剖分算法

三角剖分算法 ，采用分治法

三角剖分 算法

算法 最优三角剖分 Optimal Triangulation

Delaunay三角剖分算法的python实现

Delaunay三角剖分算法

Deaulay三角剖分算法(C#).zip

快捷方式：适用于您的WebGL应用程序的最快和最小JavaScript多边形三角剖分库

Delaunay三角剖分算法（三维）

FIST快速迭代收缩最经典的文献，目前最流行的优化算法之一

Goliat Fist-开源

H3C FIST-2.00.16版本说明书.docx

cpp-Fist是一个快速轻量级的全文搜索和索引服务器

三角网格化的一种新算法

fist-fistlabs_unit_serial:帮助进行串行执行的 Fist 插件

H3C-FIST部署.docx

FIST快速迭代收缩源代码

Fist-of-Vim:对 vim 的超级简单和很棒的要点支持

fist-fistlabs_unit_incoming:拳头的身体解析器

Earcut-Triangulation.zip

利用 First Fit 和 Best fit 算法解决物流3D bin packing问题 Python实现

fist-detector:网络摄像头拳头检测

exam-flutter-fist-parcial

mapbox_earcut_python:将Python绑定到Mapbox Earcut C ++库

最新资源

三角剖分算法，采用分治法

三角剖分算法

算法最优三角剖分 Optimal Triangulation