FIST:高效、可靠且易实现的多边形三角化算法

需积分: 18 17 浏览量更新于2024-07-28 收藏 391KB PDF 举报

FIST是一种专为工业级应用设计的快速三角剖分算法，其核心思想是基于对多边形边缘（ears）的反复修剪。该算法由Martin Held在萨尔茨堡大学计算机科学研究所开发，目标是实现高度可靠、易于实现且在实际应用中具有高效性能。算法的关键特性包括： 1. 完全可靠性：FIST算法着重于确保处理任何类型多边形数据的稳定性，无论输入几何形状如何复杂，包括简单的几何体或不规则的多边形。为了增强算法的健壮性，它采用了一套备份策略，当标准的耳修剪过程遇到输入缺陷时，这些策略会介入并修复问题。 2. 易于实施：FIST算法的实现基于ANSI C语言，并利用浮点数运算，这使得它易于程序员理解和实现。开发者在编写过程中考虑了代码的清晰性和可读性，以降低学习曲线。 3. 实践中的速度优化：FIST算法注重实际性能，通过结合多种策略来提升效率。其中，几何哈希技术被用于快速定位和剪切合适的耳朵，而边界体积树则被用来加速空间查询，减少不必要的计算。这些技术的应用使得算法在处理大量数据时展现出显著的速度优势。 FIST的代码经过精心调优，旨在提供一个既高效又稳定的三角剖分解决方案，适用于各种工业级场景，如计算机图形学、GIS（地理信息系统）、游戏开发等，其中对三角化精度和性能有高要求的领域。该算法不仅理论上有深度，而且在实际应用中经受住了考验，是提高复杂几何模型处理能力的重要工具。

predicates that rely on an adaptive oating-p oint arithmetic, cf. [42]. This co de is also

available publicly [41].

The issues of exact computation versus oating-p oint arithmetic are discussed in detail

in a survey by Yap and Dube [49]. Recent work includes papers by Avnaim et al. [3] and

Bronnimann and Yvinec [13] on the exact evaluation of integer determinants, Bronnimann

et al. [12] on exact geometric predicates with single-precision arithmetic, and Shewchuk's

design and implementation [42] of four predicates based on adaptive oating-point arith-

metic. See the recent survey pap ers by Yap and Dube [49, 48]. Exact arithmetic is oered

by the geometric software packages LEDA [14, 32] and CGAL [23, 37].

Recently, Silva et al. [44] have used an approach similar in spirit to the one described

in this pap er for ensuring reliability. While not addressing the robustness issue directly,

they also describ e how a carefully tailored ear-clipping algorithm, combined with some

additional heuristics, has yielded a fairly reliable and practical algorithm for generating

triangular irregular networks (TINs).

2 Triangulation Algorithm

2.1 Basic Algorithm

This subsection describ es the basic ear-clipping algorithm. We will rst assume that

a truly simple p olygon which does not exhibit any degeneracies. Also,

shall be oriented

counter-clo ckwise.

As usual, a vertex

is called

convex

if the internal angle of

is less than

180

, and

reex

otherwise. Reex vertices with an internal angle equal to 180

are also

called

tangential

. Two vertices

form a

diagonal

if the relative interior of the

line segment [

; v

] is completely contained in the interior of

. For a convex vertex

the

cone

dened by the three consecutive vertices

; v

, denoted by

(

; v

is the set of p oints that are strictly right of the oriented line

; v

and strictly left of

the oriented line

; v

. Similarly, if

is reex then the cone dened by

; v

the complement of the union of the cone dened by

; v

and the two rays from

through

and

Recall that three consecutive vertices

; v

form an

ear

; v

is a

diagonal of

. Obviously, for

; v

to form an ear,

has to b e a convex vertex.

Also, [

; v

] can only b e a diagonal if it is locally inside

. That is,

has to lie in

(

; v

), and

has to lie in

(

; v

). Finally,

; v

must not intersect

the b oundary of

except in the edges (

; v

) and (

; v

), or, equivalently, the triangle

(

; v

) must not contain any reex vertex of

. (Note that these two conditions

are only equivalent for simple p olygons.)

Thus, we have the following two sets of conditions for

; v

to form an ear

[31, 47, 36]. Both sets of conditions are necessary and sucient.

Fact 2.1 (CE1)

Three consecutive vertices

; v

form an ear of

i

is a convex vertex;

(

; v

) and

(

; v

);

3. the segment [

; v

] do es not intersect any edge of

except in

or in

Fact 2.2 (CE2)

Three consecutive vertices

; v

form an ear of

i

is a convex vertex;

(

; v

) and

(

; v

);

3. the closure of the triangle (

; v

) do es not contain any reex vertex of

We have implemented ear clipping according to b oth CE1 and CE2. Both have a

straightforward implementation that checks Condition (3) by a brute-force scan of all

segments, respectively of all reex vertices. For a

-gon with

reex vertices, the time

complexity of this check is

(

) for CE1, and

(

) for CE2. In Subsection 3.1, we will

discuss heuristics for decreasing the practical complexity of checking Condition (3).

The actual triangulation algorithm works as follows: After classifying the vertices of

as convex or reex, we check for every triple of consecutive vertices of

whether they

form an ear. Ears are marked and stored. (In Subsection 3.2 we will discuss the storage

and retrieval of ears in more detail.) Then the co de iteratively retrieves one of the stored

ears, clips it, and up dates the information on ears. It is well known that clipping the ear

; v

transforms a

-gon into a

1-gon, for which all previously determined ears

still are valid, except for up to two ears that involve

. (Since

got deleted,

; v

and

; v

cannot b e any ears of the new p olygon.) In addition,

; v

and

; v

could now form ears and have to b e checked. The algorithm iteratively cuts

ears until the original

-gon has b een transformed into a 3-gon (i.e., a triangle), and the

last triangle of the triangulation is trivially known.

The correctness of the algorithm is established similar to other published ear-clipping

algorithms, cf. [31, 36]. As analyzed in [31, 47, 36], the worst-case complexity of this

algorithm is

(

) if CE1 is used for determining ears, and

(



(

+ 1)) if CE2 is used.

2.2 Ensuring Consistency

Before the ear-clipping pro cess starts, we sort the vertices of the polygon lexicographically,

rst according to

-co ordinates, and second according to

-co ordinates. A simple scan

through the array of sorted vertices reveals all true duplicates

, which are discarded in the

array. Then, by means of a binary search, every vertex of the p olygon gets assigned its

index in the sorted array of vertices. As a result, vertices that have identical coordinates

have the same index. (If desired by the application, we can now also delete any edge whose

start and end vertices are identical, i.e., zero-length edges.) In the sequel, whenever we

sp eak of the index of a vertex we will refer to its index in this sorted array.

A close insp ection of the computations required by the ear-clipping algorithm reveals

that one basic primitive op eration suces: all we need to do is to check whether some

vertex

is left of, on, or right of the oriented line through two other vertices

and

. As

usual, this primitive is implemented as the evaluation of the sign of a 3



3 determinant.

Care is taken that the evaluations are consistent. We always compute determinants

such that the index of the rst vertex is less than the index of the second vertex, which

in turn is less than the index of the third vertex. If this causes a change of the cyclic

order of the vertices then the sign of the resulting determinant is inverted. (Trivially, the

determinant is zero if any two indices of the vertices are identical.)

I.e., vertices which have identical co ordinates.

剩余30页未读，继续阅读

mycug

粉丝: 3
资源: 24

FIST:高效、可靠且易实现的多边形三角化算法

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

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

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

exam-flutter-fist-parcial

fist-child

Goliat Fist-开源

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

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

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

Fist-Fighting-Animals:使用node.js express和mongoDB构建的网络游戏

最新资源