A faster circle-sweep Delaunay triangulation algorithm

doi:10.1016/j.advengsoft.2011.09.003

A faster circle-sweep Delaunay triangulation algorithm

2012-01-01

22

PRE

AI

A

Ahmad Biniaz *

G

Gholamhossein Dastghaibyfard

DOI：10.1016/j.advengsoft.2011.09.003

原文链接

原文求助

摘要

En 中文

This paper presents a new way to compute the Delaunay triangulation of a planar set P of n points, using sweep-circle technique combined with the standard recursive edge-flipping. The algorithm sweeps the plane by an increasing circle whose center is a fixed point in the convex hull of P. Empirical results and comparisons show that it reduces the number of in-circle tests and edge-flips, and it is efficient in practice. (C) 2011 Elsevier Ltd. All rights reserved.

Keyword:

Computational geometry

Delaunay triangulation

In-circle test

Recursive edge-flipping

Sweep-line

Sweep-circle

A faster circle-sweep Delaunay triangulation algorithm

摘要

期刊

机构