MantisBT - VTK
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0012178VTK(No Category)public2011-05-10 19:572016-08-12 09:55
ReporterBengt R. 
Assigned ToDave DeMarle 
PriorityhighSeveritymajorReproducibilityalways
StatusclosedResolutionmoved 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Project
Type
Summary0012178: vtkDelaunay2D fails to recover boundary
DescriptionThe 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 Reproduce1. 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 InformationInput:
# 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

TagsvtkDelaunay2D
Relationships
related to 0011102closed Dave DeMarle vtkDelaunay2D with some pairs of datasets and transforms crashes 
related to 0004422closed Will Schroeder bug about vtkDelaunay2D (sourcecode) 
Attached Filescpp delaunay2bug.cpp (1,544) 2011-05-10 19:57
https://www.vtk.org/Bug/file/8863/delaunay2bug.cpp
? points.vtk (2,560) 2011-05-10 19:59
https://www.vtk.org/Bug/file/8864/points.vtk
? constraints.vtk (190) 2011-05-10 19:59
https://www.vtk.org/Bug/file/8865/constraints.vtk
Issue History
Date ModifiedUsernameFieldChange
2011-05-10 19:57Bengt R.New Issue
2011-05-10 19:57Bengt R.File Added: delaunay2bug.cpp
2011-05-10 19:58Bengt R.Tag Attached: vtkDelaunay2D
2011-05-10 19:59Bengt R.File Added: points.vtk
2011-05-10 19:59Bengt R.File Added: constraints.vtk
2011-05-10 20:00Bengt R.Note Added: 0026487
2011-05-10 20:41David GobbiRelationship addedrelated to 0011102
2011-05-10 20:44David GobbiRelationship addedrelated to 0004422
2011-05-11 15:31Cory QuammenNote Added: 0026496
2011-05-11 16:53Bengt R.Note Added: 0026497
2011-05-11 17:45Cory QuammenNote Added: 0026498
2013-07-22 18:18Dave DeMarleNote Added: 0031194
2013-07-22 18:18Dave DeMarleStatusbacklog => expired
2013-07-22 18:18Dave DeMarleAssigned To => Dave DeMarle
2016-08-12 09:55Kitware RobotNote Added: 0037234
2016-08-12 09:55Kitware RobotStatusexpired => closed
2016-08-12 09:55Kitware RobotResolutionopen => moved

Notes
(0026487)
Bengt R.   
2011-05-10 20:00   
I uploaded the input (points.vtk) and the constraints (constraints.vtk) as attachements.
(0026496)
Cory Quammen   
2011-05-11 15:31   
Your constraint polygon is not convex, which may be causing the error message.

In any case, your constraint polygon will not work to enforce a triangulation that has edges aligned along a longer constraint lines. This feature does not exist in the vtkDelaunay2D filter, but it would be nice to have.

If you want the triangulation to have edges aligned with your constraint polygon, I suggest that you cut each constraint polygon edge wherever one of the points in the set you are trying to triangulate lines on that edge. I know, it's a pain. Also, you need to make sure the point IDs in the constraint polygon are the same as the point IDs in the input point set, otherwise edge recovery will not work.
(0026497)
Bengt R.   
2011-05-11 16:53   
Thanks for the reply.
The error message is exactly due to the fact that some triangle edges are collinear with some constraint edges, which results in degenerated cavity polygons being collected. I think non-convex polygons as the boundary are supported, aren't they?

Anyways, we investigated the issue further and this paper suggests a solution to the contraint edge on triangle edge problem:
http://www.cg.tuwien.ac.at/hostings/cescg/CESCG-2004/web/Domiter-Vid/CDT.pdf [^]

The solution is to split the constraint edge at the points being on the constraint edge and to recursively recover each sub-edge.

It should be quite easy to change the existing method to support this. I may do that.
(0026498)
Cory Quammen   
2011-05-11 17:45   
> The solution is to split the constraint edge at the points being on the constraint edge and to recursively recover each sub-edge.

That's what I was suggesting. Sorry if I didn't express it clearly.

If you implement this feature, I will gladly test it as I have an application that could use it. I'm currently using the splitting approach.
(0031194)
Dave DeMarle   
2013-07-22 18:18   
If the bug is still present in 6.0.0, please reopen this report.
(0037234)
Kitware Robot   
2016-08-12 09:55   
Resolving issue as `moved`.

This issue tracker is no longer used. Further discussion of this issue may take place in the current VTK Issues page linked in the banner at the top of this page.