Constrained Delaunay Triangulation Using Delaunay Visibility

Yi-Jun Yang; Hui Zhang; Jun-Hai Yong; Wei Zeng; Jean-Claude Paul; Jiaguang Sun

inria-00139015, version 1

Constrained Delaunay Triangulation Using Delaunay Visibility

Yi-Jun Yang ¹, Hui Zhang ¹, Jun-Hai Yong ¹, Wei Zeng^a, Jean-Claude Paul^b^, 1, Jiaguang Sun^a

Advances in Visual Computing, Second International Symposium, ISVC 2006, Proceedings part I 4291 (2006)

Abstract: An algorithm for constructing constrained Delaunay triangulation (CDT) of a planar straight-line graph (PSLG) is presented. Although the uniform grid method can reduce the time cost of visibility determinations, the time needed to construct the CDT is still long. The algorithm proposed in this paper decreases the number of edges involved in the computation of visibility by replacing traditional visibility with Delaunay visibility. With Delaunay visibility introduced, all strongly Delaunay edges are excluded from the computation of visibility. Furthermore, a sufficient condition for DT (CDT whose triangles are all Delaunay) existence is presented to decrease the times of visibility determinations. The mesh generator is robust and exhibits a linear time complexity for randomly generated PSLGs.

a – Chinese Academy of Science
b – INRIA
1: CAD (CAD LIAMA INRIA Paris - Rocquencourt)
Centre de coopération internationale en recherche agronomique pour le développement [CIRAD] – CNRS – Institut national de la recherche agronomique (INRA) – Chinese Academy of Science (CAS) – Institute of Automation, Chinese Academy of Sciences – INRIA

inria-00139015, version 1
http://hal.inria.fr/inria-00139015
oai:hal.inria.fr:inria-00139015
From: Chine Publications Liama <>
Submitted on: Wednesday, 28 March 2007 17:21:18
Updated on: Wednesday, 28 March 2007 17:21:18

See detailed view

Associated documents

DOI: 10.1007/11919476

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00139015"><analytic>
<author><persName><forename>Yi-Jun</forename><surname>Yang</surname></persName>
<affiliation>
<orgName type="laboratory">CAD LIAMA INRIA Paris - Rocquencourt</orgName>
<orgName type="team">CAD</orgName>
<country>CN</country>
<orgName type="institution">Centre de coopération internationale en recherche agronomique pour le développement [CIRAD]</orgName>
<orgName type="institution">CNRS</orgName>
<orgName type="institution">Institut national de la recherche agronomique (INRA)</orgName>
<orgName type="institution">Chinese Academy of Science (CAS)</orgName>
<orgName type="institution">Institute of Automation, Chinese Academy of Sciences</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Hui</forename><surname>Zhang</surname></persName>
<affiliation>
<orgName type="laboratory">CAD LIAMA INRIA Paris - Rocquencourt</orgName>
<orgName type="team">CAD</orgName>
<country>CN</country>
<orgName type="institution">Centre de coopération internationale en recherche agronomique pour le développement [CIRAD]</orgName>
<orgName type="institution">CNRS</orgName>
<orgName type="institution">Institut national de la recherche agronomique (INRA)</orgName>
<orgName type="institution">Chinese Academy of Science (CAS)</orgName>
<orgName type="institution">Institute of Automation, Chinese Academy of Sciences</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Jun-Hai</forename><surname>Yong</surname></persName>
<affiliation>
<orgName type="laboratory">CAD LIAMA INRIA Paris - Rocquencourt</orgName>
<orgName type="team">CAD</orgName>
<country>CN</country>
<orgName type="institution">Centre de coopération internationale en recherche agronomique pour le développement [CIRAD]</orgName>
<orgName type="institution">CNRS</orgName>
<orgName type="institution">Institut national de la recherche agronomique (INRA)</orgName>
<orgName type="institution">Chinese Academy of Science (CAS)</orgName>
<orgName type="institution">Institute of Automation, Chinese Academy of Sciences</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Wei</forename><surname>Zeng</surname></persName></author>
<author><persName><forename>Jean-Claude</forename><surname>Paul</surname></persName>
<affiliation>
<orgName type="laboratory">CAD LIAMA INRIA Paris - Rocquencourt</orgName>
<orgName type="team">CAD</orgName>
<country>CN</country>
<orgName type="institution">Centre de coopération internationale en recherche agronomique pour le développement [CIRAD]</orgName>
<orgName type="institution">CNRS</orgName>
<orgName type="institution">Institut national de la recherche agronomique (INRA)</orgName>
<orgName type="institution">Chinese Academy of Science (CAS)</orgName>
<orgName type="institution">Institute of Automation, Chinese Academy of Sciences</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Jiaguang</forename><surname>Sun</surname></persName></author>
<title type="main" level="a">Constrained Delaunay Triangulation Using Delaunay Visibility</title></analytic><monogr><meeting>Advances in Visual Computing, Second International Symposium, ISVC 2006, Proceedings part I</meeting><imprint><pubPlace><settlement>Lake Tahoe </settlement><country> USA</country></pubPlace><biblScope type="publicationDate">2006-11-06</biblScope><biblScope type="vol">4291</biblScope></imprint></monogr><idno type="doi">10.1007/11919476</idno><idno type="HALid">http://hal.inria.fr/inria-00139015</idno></biblStruct>
</listBibl>
</listBibl>