[java] Tessellation with hole error

[GoogleCodeExporter]

What steps will reproduce the problem?
Using this polygon as input:
82 87
74 88
74 96
84 96
84 91

84 91
82 95
77 94
79 89
(Second list is hole)

This is a valid polygon:

    Polygon rings must close
    Rings that define holes should be inside rings that define exterior boundaries
    Rings must not self-intersect—they may neither touch nor cross one another
    Rings must not touch other rings except at a point

What is the expected output? What do you see instead?

Expect to have 7 triangles.

Got 13 triangles. The output mesh contains the tail and head points of Sweep 
line algorithm.

What version of the product are you using? On what operating system?

Last version of poly2tri (rev b85d2568420a )

This input polygon is not supported by poly2tri.js

The fix is relatively simple. Just ignore triangles that contains the point 
DTSweepContext._tail or DTSweepContext._head .

Please provide any additional information below.

Original issue reported on code.google.com by nico.de...@gmail.com on 20 Apr 2015 at 9:15

[GoogleCodeExporter]

The thing is that this isn't a strictly simple polygon since both outer ring 
and the hole shares a vertex. So this is a weakly simple polygon.

As long as this shared vertex is a single object the triangulator should have 
no problems triangulating. If your polygon contain multiple shared vertexes 
such that all the internal triangles can't form a single edge connected graph 
the cleanup of external triangles will fail.

So poly2tri assumes that vertexes shared by hole and outer ring isn't shared, 
but can handle it if you make sure they are the same object. Poly2tri's simple 
way of cleaning away outside triangles also assumes that all inner triangles 
are connected by atleast one edge so that they form a single graph.

Original comment by thahlen@gmail.com on 20 Apr 2015 at 12:32

[GoogleCodeExporter]

To clearify in this case your will have to ensure that any shared vertexes are 
the same object in the input to poly2tri.

Original comment by thahlen@gmail.com on 20 Apr 2015 at 12:38

[GoogleCodeExporter]

Hi,

The merge of points instance have to be done in Polygon.prepareTriangulation 
because there is muliple call of tcx.addPoints one for outer ring, one for each 
hole and one for steiner points. And if the same instance of object are added 
in context multiple time then there is neighbors computation errors.

I will make the hashmap in the method and use this hashmap for the single 
tcx.addPoints at the end.

I will give you the fix today or tomorrow.

Regards,

 --

Nicolas Fortin
IRSTV FR CNRS 2488
GIS        http://orbisgis.org
Spatial DB http://h2gis.org
Noise      http://noisemap.orbisgis.org

Original comment by nico.de...@gmail.com on 20 Apr 2015 at 3:04

[GoogleCodeExporter]

Hi,

Here is the patch. If hole and outer ring have the same instance of point it is 
now added only once to the triangulation context.

https://github.com/irstv/poly2tri.java/compare/5951cf51acbd431232c28a2f7a5bbb802
d963a24...nicolas-f:polygon_issue_patch
https://github.com/irstv/poly2tri.java/compare/5951cf51acbd431232c28a2f7a5bbb802
d963a24...nicolas-f:polygon_issue_patch.diff
https://github.com/irstv/poly2tri.java/compare/5951cf51acbd431232c28a2f7a5bbb802
d963a24...nicolas-f:polygon_issue_patch.patch

Thanks,

Regards,

 --

Nicolas Fortin
IRSTV FR CNRS 2488
GIS        http://orbisgis.org
Spatial DB http://h2gis.org
Noise      http://noisemap.orbisgis.org

Original comment by nico.de...@gmail.com on 21 Apr 2015 at 11:23