[vtk-developers] [VTK 0012178]: vtkDelaunay2D fails to recover boundary

[Mantis Bug Tracker]

The following issue has been SUBMITTED. 
====================================================================== 
http://www.vtk.org/Bug/view.php?id=12178 
====================================================================== 
Reported By:                Bengt R.
Assigned To:                
====================================================================== 
Project:                    VTK
Issue ID:                   12178
Category:                   (No Category)
Reproducibility:            always
Severity:                   major
Priority:                   high
Status:                     new
====================================================================== 
Date Submitted:             2011-05-10 19:57 EDT
Last Modified:              2011-05-10 19:57 EDT
====================================================================== 
Summary:                    vtkDelaunay2D fails to recover boundary
Description: 
The algorithm which performs the edge recovery does not consider cases where the
edge to recover is collinear with an existing edge of a triangle of the
triangulation. This results in the retriangulation of the left/right side to
fail.

Steps to Reproduce: 
1. Run the code attached. It uses the points defined in the additional
information as the input and the polygon as the constraint.
2. The output will only contain three triangles (one of them seems to be
degenerated to a line) which is obviously wrong.
3. The file output.txt will contain several "Edge not recovered, polygon fill
suspect" warnings.

Additional Information: 
Input:
# vtk DataFile Version 4.2
Exported on 05/10/2011 23:11:38
ASCII
DATASET UNSTRUCTURED_GRID
POINTS 82 double
-10 -10 0
0 0 0
10 -10 0
7.5 0 0
10 10 0
-10 10 0
-10 -10 0
-9.17287301336085 -9.17287301336085 0
-8.34574602672171 -8.34574602672171 0
-7.51861904008256 -7.51861904008256 0
-6.69149205344341 -6.69149205344341 0
-5.86436506680427 -5.86436506680427 0
-5.03723808016512 -5.03723808016512 0
-4.21011109352597 -4.21011109352597 0
-3.38298410688683 -3.38298410688683 0
-2.55585712024768 -2.55585712024768 0
-1.72873013360853 -1.72873013360853 0
-0.901603146969384 -0.901603146969384 0
-0.0744761603302369 -0.0744761603302369 0
0.75265082630891 -0.75265082630891 0
1.57977781294806 -1.57977781294806 0
2.4069047995872 -2.4069047995872 0
3.23403178622635 -3.23403178622635 0
4.0611587728655 -4.0611587728655 0
4.88828575950464 -4.88828575950464 0
5.71541274614379 -5.71541274614379 0
6.54253973278294 -6.54253973278294 0
7.36966671942209 -7.36966671942208 0
8.19679370606123 -8.19679370606123 0
9.02392069270038 -9.02392069270038 0
9.85104767933953 -9.85104767933953 0
9.76738800861033 -9.06955203444131 0
9.48368579272672 -7.93474317090691 0
9.19998357684312 -6.7999343073725 0
8.91628136095952 -5.6651254438381 0
8.63257914507592 -4.5303165803037 0
8.34887692919232 -3.39550771676929 0
8.06517471330872 -2.26069885323489 0
7.78147249742512 -1.12588998970049 0
7.50222971845848 0.00891887383391854 0
7.78593193434208 1.14372773736832 0
8.06963415022568 2.27853660090273 0
8.35333636610928 3.41334546443713 0
8.63703858199288 4.54815432797153 0
8.92074079787648 5.68296319150594 0
9.20444301376008 6.81777205504034 0
9.48814522964368 7.95258091857475 0
9.77184744552729 9.08738978210915 0
9.77096287853561 10 0
8.60122867622574 10 0
7.43149447391587 10 0
6.26176027160599 10 0
5.09202606929612 10 0
3.92229186698625 10 0
2.75255766467638 10 0
1.58282346236651 10 0
0.413089260056637 10 0
-0.756644942253235 10 0
-1.92637914456311 10 0
-3.09611334687298 10 0
-4.26584754918285 10 0
-5.43558175149272 10 0
-6.6053159538026 10 0
-7.77505015611247 10 0
-8.94478435842234 10 0
-10 9.88548143926779 0
-10 8.71574723695792 0
-10 7.54601303464805 0
-10 6.37627883233818 0
-10 5.2065446300283 0
-10 4.03681042771843 0
-10 2.86707622540856 0
-10 1.69734202309869 0
-10 0.52760782078882 0
-10 -0.642126381521052 0
-10 -1.81186058383092 0
-10 -2.9815947861408 0
-10 -4.15132898845067 0
-10 -5.32106319076054 0
-10 -6.49079739307041 0
-10 -7.66053159538028 0
-10 -8.83026579769016 0

Constraint source:
# vtk DataFile Version 4.2
Exported on 05/10/2011 23:11:38
ASCII
DATASET POLYDATA
POINTS 6 double
-10 -10 0
0 0 0
10 -10 0
7.5 0 0
10 10 0
-10 10 0
POLYGONS 1 7
6 0 1 2 3 4 5


====================================================================== 

Issue History 
Date Modified    Username       Field                    Change               
====================================================================== 
2011-05-10 19:57 Bengt R.       New Issue                                    
2011-05-10 19:57 Bengt R.       File Added: delaunay2bug.cpp                    
======================================================================