jts
jts copied to clipboard
Published
20 hours ago •
locationtech
locationtech
Too many splitting iterations while enforcing constraints
I try to use NetTopologySuite to do the triangulation for polygons to make a mesh for unity game. I Use NetTopologySuite.Triangulate.ConformingDelaunayTriangulationBuilder Then I got an error: Too many splitting iterations while enforcing constraints.
Then I try to write a unitest using JTS:
@Test
void CDT() throws ParseException {
String bad_case = "POLYGON((-5.139864348491315 -1.8039338300053203,-4.432009282175666 -1.6631749878758058,-5.5365769064693575 -0.10992007721512209,-5.469725816735179 -1.4281793732546362,-5.139864348491315 -1.8039338300053203))";
Geometry polygon = new WKTReader().read(bad_case);
ConformingDelaunayTriangulationBuilder builder = new ConformingDelaunayTriangulationBuilder();
builder.setSites(polygon);
builder.setConstraints(polygon);
Geometry result = builder.getTriangles(new GeometryFactory());
System.out.println(result);
}
Then I got:
Too many splitting iterations while enforcing constraints. Last split point was at: [ POINT ( -5.536576906469357 -0.10992007721512301 ) ]
org.locationtech.jts.triangulate.ConstraintEnforcementException: Too many splitting iterations while enforcing constraints. Last split point was at: [ POINT ( -5.536576906469357 -0.10992007721512301 ) ]
at org.locationtech.jts.triangulate.ConformingDelaunayTriangulator.enforceConstraints(ConformingDelaunayTriangulator.java:401)
at org.locationtech.jts.triangulate.ConformingDelaunayTriangulationBuilder.create(ConformingDelaunayTriangulationBuilder.java:116)
at org.locationtech.jts.triangulate.ConformingDelaunayTriangulationBuilder.getTriangles(ConformingDelaunayTriangulationBuilder.java:192)
at io.flexgalaxy.iobjcore.MapGeneratorTest.CDT(MapGeneratorTest.java:77)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.base/java.lang.reflect.Method.invoke(Method.java:566)
...
Also I test in C# with NetTopologySuite. The code and error are totally same.
I plot the polygon I think it is a normal convex polygon.
dependencies {
implementation 'org.junit.jupiter:junit-jupiter:5.7.2'
testImplementation 'org.junit.jupiter:junit-jupiter-api:5.6.0'
testRuntimeOnly 'org.junit.jupiter:junit-jupiter-engine'
implementation 'org.wololo:jts2geojson:0.16.1'
implementation 'org.locationtech.jts:jts-core:1.18.2'
implementation 'org.locationtech.jts.io:jts-io-common:1.18.2'
}
If I open the debug property like this:
@Test
void CDT() throws ParseException {
Properties properties = new Properties();
properties.setProperty("jts.debug", "on");
System.setProperties(properties);
String bad_case = "POLYGON((-5.139864348491315 -1.8039338300053203,-4.432009282175666 -1.6631749878758058,-5.5365769064693575 -0.10992007721512209,-5.469725816735179 -1.4281793732546362,-5.139864348491315 -1.8039338300053203))";
Geometry polygon = new WKTReader().read(bad_case);
ConformingDelaunayTriangulationBuilder builder = new ConformingDelaunayTriangulationBuilder();
builder.setSites(polygon);
builder.setConstraints(polygon);
Geometry result = builder.getTriangles(new GeometryFactory());
System.out.println(result);
}
Here is the debug log:
D! Iter: 37 Splits: 2 Current # segments = 78
D! Iter: 38 Splits: 2 Current # segments = 80
D! Iter: 39 Splits: 2 Current # segments = 82
D! Iter: 40 Splits: 2 Current # segments = 84
D! Iter: 41 Splits: 2 Current # segments = 86
D! Iter: 42 Splits: 2 Current # segments = 88
D! Iter: 43 Splits: 2 Current # segments = 90
D! Iter: 44 Splits: 2 Current # segments = 92
D! Iter: 45 Splits: 2 Current # segments = 94
D! Iter: 46 Splits: 2 Current # segments = 96
D! Iter: 47 Splits: 2 Current # segments = 98
D! Iter: 48 Splits: 2 Current # segments = 100
D! Iter: 49 Splits: 2 Current # segments = 102
D! Iter: 50 Splits: 2 Current # segments = 104
D! Iter: 51 Splits: 2 Current # segments = 106
D! Iter: 52 Splits: 3 Current # segments = 109
D! Iter: 53 Splits: 4 Current # segments = 113
D! Iter: 54 Splits: 4 Current # segments = 117
D! Iter: 55 Splits: 3 Current # segments = 120
D! Iter: 56 Splits: 2 Current # segments = 122
D! Iter: 57 Splits: 3 Current # segments = 125
D! Iter: 58 Splits: 2 Current # segments = 127
D! Iter: 59 Splits: 2 Current # segments = 129
D! Iter: 60 Splits: 2 Current # segments = 131
D! Iter: 61 Splits: 2 Current # segments = 133
D! Iter: 62 Splits: 2 Current # segments = 135
D! Iter: 63 Splits: 2 Current # segments = 137
D! Iter: 64 Splits: 2 Current # segments = 139
D! Iter: 65 Splits: 2 Current # segments = 141
D! Iter: 66 Splits: 2 Current # segments = 143
D! Iter: 67 Splits: 2 Current # segments = 145
D! Iter: 68 Splits: 2 Current # segments = 147
D! Iter: 69 Splits: 2 Current # segments = 149
D! Iter: 70 Splits: 2 Current # segments = 151
D! Iter: 71 Splits: 2 Current # segments = 153
D! Iter: 72 Splits: 2 Current # segments = 155
D! Iter: 73 Splits: 2 Current # segments = 157
D! Iter: 74 Splits: 2 Current # segments = 159
D! Iter: 75 Splits: 2 Current # segments = 161
D! Iter: 76 Splits: 2 Current # segments = 163
D! Iter: 77 Splits: 2 Current # segments = 165
D! Iter: 78 Splits: 2 Current # segments = 167
D! Iter: 79 Splits: 2 Current # segments = 169
D! Iter: 80 Splits: 2 Current # segments = 171
D! Iter: 81 Splits: 2 Current # segments = 173
D! Iter: 82 Splits: 2 Current # segments = 175
D! Iter: 83 Splits: 2 Current # segments = 177
D! Iter: 84 Splits: 2 Current # segments = 179
D! Iter: 85 Splits: 2 Current # segments = 181
D! Iter: 86 Splits: 2 Current # segments = 183
D! Iter: 87 Splits: 2 Current # segments = 185
D! Iter: 88 Splits: 2 Current # segments = 187
D! Iter: 89 Splits: 2 Current # segments = 189
D! Iter: 90 Splits: 2 Current # segments = 191
D! Iter: 91 Splits: 2 Current # segments = 193
D! Iter: 92 Splits: 2 Current # segments = 195
D! Iter: 93 Splits: 2 Current # segments = 197
D! Iter: 94 Splits: 2 Current # segments = 199
D! Iter: 95 Splits: 2 Current # segments = 201
D! Iter: 96 Splits: 2 Current # segments = 203
D! Iter: 97 Splits: 2 Current # segments = 205
D! Iter: 98 Splits: 2 Current # segments = 207
D! Iter: 99 Splits: 2 Current # segments = 209
D! ABORTED! Too many iterations while enforcing constraints
GEOMETRYCOLLECTION (POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151408, -5.536576906469357 -0.1099200772151315, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151315, -5.536576906469357 -0.1099200772151268, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151268, -5.536576906469357 -0.1099200772151244, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151244, -5.536576906469357 -0.1099200772151233, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151233, -5.536576906469357 -0.1099200772151233, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151233, -5.536576906469357 -0.1099200772151232, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151232, -5.536576906469357 -0.1099200772151232, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151232, -5.536576906469357 -0.1099200772151232, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151232, -5.536576906469357 -0.1099200772151231, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151231, -5.536576906469357 -0.1099200772151231, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.1099200772151231, -5.536576906469357 -0.109920077215123, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.109920077215123, -5.536576906469357 -0.109920077215123, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.109920077215123, -5.536576906469357 -0.109920077215123, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.5365769064693575 -0.1099200772151221, -5.536576906469357 -0.109920077215123, -5.536576906469356 -0.1099200772151236, -5.5365769064693575 -0.1099200772151221)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.109920077215123, -5.536576906469357 -0.109920077215123, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.109920077215123, -5.536576906469357 -0.109920077215123, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.109920077215123, -5.536576906469357 -0.1099200772151231, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.1099200772151231, -5.536576906469357 -0.1099200772151231, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.1099200772151231, -5.536576906469357 -0.1099200772151232, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.1099200772151232, -5.536576906469357 -0.1099200772151232, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.1099200772151232, -5.536576906469357 -0.1099200772151232, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.1099200772151232, -5.536576906469357 -0.1099200772151233, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.1099200772151233, -5.536576906469357 -0.1099200772151233, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.1099200772151233, -5.536576906469357 -0.1099200772151244, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469357 -0.1099200772151244, -5.536576906469355 -0.1099200772151249, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469355 -0.1099200772151249, -5.5365769064692945 -0.1099200772152104, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.5365769064692945 -0.1099200772152104, -5.536576906469106 -0.1099200772154753, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906469106 -0.1099200772154753, -5.536576906468353 -0.1099200772165348, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906469356 -0.1099200772151236, -5.536576906468353 -0.1099200772165348, -5.536576906467348 -0.1099200772179474, -5.536576906469356 -0.1099200772151236)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.536576906468353 -0.1099200772165348, -5.536576906469236 -0.10992007721752, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.536576906469236 -0.10992007721752, -5.536576906469115 -0.1099200772199179, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.536576906469115 -0.1099200772199179, -5.5365769064653385 -0.1099200772207728, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.5365769064653385 -0.1099200772207728, -5.53657690643721 -0.1099200772603278, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.53657690643721 -0.1099200772603278, -5.536576906212181 -0.1099200775767674, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.536576906212181 -0.1099200775767674, -5.536576905955004 -0.1099200779384128, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.536576905955004 -0.1099200779384128, -5.536576905440649 -0.1099200786617034, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.536576905440649 -0.1099200786617034, -5.536576904411939 -0.1099200801082848, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576906467348 -0.1099200772179474, -5.536576904411939 -0.1099200801082848, -5.536576840631996 -0.1099201697963293, -5.536576906467348 -0.1099200772179474)), POLYGON ((-5.536576840631996 -0.1099201697963293, -5.536576904411939 -0.1099200801082848, -5.536576873550677 -0.1099201235057257, -5.536576840631996 -0.1099201697963293)), POLYGON ((-5.536576840631996 -0.1099201697963293, -5.536576873550677 -0.1099201235057257, -5.536576902484722 -0.1099201557894992, -5.536576840631996 -0.1099201697963293)), POLYGON ((-5.536576840631996 -0.1099201697963293, -5.536576902484722 -0.1099201557894992, -5.536576898500087 -0.1099202343638762, -5.536576840631996 -0.1099201697963293)), POLYGON ((-5.536576840631996 -0.1099201697963293, -5.536576898500087 -0.1099202343638762, -5.536576774794636 -0.1099202623775365, -5.536576840631996 -0.1099201697963293)), POLYGON ((-5.536576774794636 -0.1099202623775365, -5.536576898500087 -0.1099202343638762, -5.5365768905308155 -0.1099203915126303, -5.536576774794636 -0.1099202623775365)), POLYGON ((-5.536576774794636 -0.1099202623775365, -5.5365768905308155 -0.1099203915126303, -5.536576643119915 -0.1099204475399509, -5.536576774794636 -0.1099202623775365)), POLYGON ((-5.536576643119915 -0.1099204475399509, -5.5365768905308155 -0.1099203915126303, -5.536576874592274 -0.1099207058101386, -5.536576643119915 -0.1099204475399509)), POLYGON ((-5.536576643119915 -0.1099204475399509, -5.536576874592274 -0.1099207058101386, -5.536576379770471 -0.1099208178647797, -5.536576643119915 -0.1099204475399509)), POLYGON ((-5.536576379770471 -0.1099208178647797, -5.536576874592274 -0.1099207058101386, -5.53657684271519 -0.1099213344051551, -5.536576379770471 -0.1099208178647797)), POLYGON ((-5.536576379770471 -0.1099208178647797, -5.53657684271519 -0.1099213344051551, -5.536575853071584 -0.1099215585144372, -5.536576379770471 -0.1099208178647797)), POLYGON ((-5.536575853071584 -0.1099215585144372, -5.53657684271519 -0.1099213344051551, -5.536576778961022 -0.1099225915951881, -5.536575853071584 -0.1099215585144372)), POLYGON ((-5.536575853071584 -0.1099215585144372, -5.536576778961022 -0.1099225915951881, -5.53657479967381 -0.1099230398137523, -5.536575853071584 -0.1099215585144372)), POLYGON ((-5.53657479967381 -0.1099230398137523, -5.536576778961022 -0.1099225915951881, -5.5365766514526875 -0.1099251059752541, -5.53657479967381 -0.1099230398137523)), POLYGON ((-5.53657479967381 -0.1099230398137523, -5.5365766514526875 -0.1099251059752541, -5.536572692878261 -0.1099260024123826, -5.53657479967381 -0.1099230398137523)), POLYGON ((-5.536572692878261 -0.1099260024123826, -5.5365766514526875 -0.1099251059752541, -5.536576396436018 -0.1099301347353861, -5.536572692878261 -0.1099260024123826)), POLYGON ((-5.536572692878261 -0.1099260024123826, -5.536576396436018 -0.1099301347353861, -5.5365684792871654 -0.1099319276096431, -5.536572692878261 -0.1099260024123826)), POLYGON ((-5.5365684792871654 -0.1099319276096431, -5.536576396436018 -0.1099301347353861, -5.53657588640268 -0.10994019225565, -5.5365684792871654 -0.1099319276096431)), POLYGON ((-5.5365684792871654 -0.1099319276096431, -5.53657588640268 -0.10994019225565, -5.5365600521049725 -0.1099437780041642, -5.5365684792871654 -0.1099319276096431)), POLYGON ((-5.5365600521049725 -0.1099437780041642, -5.53657588640268 -0.10994019225565, -5.536574866336004 -0.109960307296178, -5.5365600521049725 -0.1099437780041642)), POLYGON ((-5.5365600521049725 -0.1099437780041642, -5.536574866336004 -0.109960307296178, -5.536543197740588 -0.1099674787932062, -5.5365600521049725 -0.1099437780041642)), POLYGON ((-5.536543197740588 -0.1099674787932062, -5.536574866336004 -0.109960307296178, -5.536572826202651 -0.1100005373772339, -5.536543197740588 -0.1099674787932062)), POLYGON ((-5.536543197740588 -0.1099674787932062, -5.536572826202651 -0.1100005373772339, -5.53650948901182 -0.1100148803712903, -5.536543197740588 -0.1099674787932062)), POLYGON ((-5.53650948901182 -0.1100148803712903, -5.536572826202651 -0.1100005373772339, -5.536568745935943 -0.1100809975393457, -5.53650948901182 -0.1100148803712903)), POLYGON ((-5.53650948901182 -0.1100148803712903, -5.536568745935943 -0.1100809975393457, -5.5364420715542835 -0.1101096835274586, -5.53650948901182 -0.1100148803712903)), POLYGON ((-5.5364420715542835 -0.1101096835274586, -5.536568745935943 -0.1100809975393457, -5.536560585402528 -0.1102419178635692, -5.5364420715542835 -0.1101096835274586)), POLYGON ((-5.5364420715542835 -0.1101096835274586, -5.536560585402528 -0.1102419178635692, -5.5363072366392085 -0.1102992898397951, -5.5364420715542835 -0.1101096835274586)), POLYGON ((-5.5363072366392085 -0.1102992898397951, -5.536560585402528 -0.1102419178635692, -5.5365442643356975 -0.1105637585120164, -5.5363072366392085 -0.1102992898397951)), POLYGON ((-5.5363072366392085 -0.1102992898397951, -5.5365442643356975 -0.1105637585120164, -5.536037566809059 -0.1106785024644681, -5.5363072366392085 -0.1102992898397951)), POLYGON ((-5.536037566809059 -0.1106785024644681, -5.5365442643356975 -0.1105637585120164, -5.536511622202038 -0.1112074398089107, -5.536037566809059 -0.1106785024644681)), POLYGON ((-5.536037566809059 -0.1106785024644681, -5.536511622202038 -0.1112074398089107, -5.535498227148759 -0.1114369277138142, -5.536037566809059 -0.1106785024644681)), POLYGON ((-5.535498227148759 -0.1114369277138142, -5.536511622202038 -0.1112074398089107, -5.53644633793472 -0.1124948024026993, -5.535498227148759 -0.1114369277138142)), POLYGON ((-5.535498227148759 -0.1114369277138142, -5.53644633793472 -0.1124948024026993, -5.5344195478281595 -0.1129537782125062, -5.535498227148759 -0.1114369277138142)), POLYGON ((-5.5344195478281595 -0.1129537782125062, -5.53644633793472 -0.1124948024026993, -5.536315769400083 -0.1150695275902764, -5.5344195478281595 -0.1129537782125062)), POLYGON ((-5.5344195478281595 -0.1129537782125062, -5.536315769400083 -0.1150695275902764, -5.5322621891869606 -0.1159874792098904, -5.5344195478281595 -0.1129537782125062)), POLYGON ((-5.5322621891869606 -0.1159874792098904, -5.536315769400083 -0.1150695275902764, -5.53605463233081 -0.1202189779654308, -5.5322621891869606 -0.1159874792098904)), POLYGON ((-5.5322621891869606 -0.1159874792098904, -5.53605463233081 -0.1202189779654308, -5.527947471904563 -0.1220548812046587, -5.5322621891869606 -0.1159874792098904)), POLYGON ((-5.527947471904563 -0.1220548812046587, -5.53605463233081 -0.1202189779654308, -5.5355323581922615 -0.1305178787157395, -5.527947471904563 -0.1220548812046587)), POLYGON ((-5.527947471904563 -0.1220548812046587, -5.5355323581922615 -0.1305178787157395, -5.519318037339769 -0.1341896851941953, -5.527947471904563 -0.1220548812046587)), POLYGON ((-5.519318037339769 -0.1341896851941953, -5.5355323581922615 -0.1305178787157395, -5.534487809915165 -0.1511156802163569, -5.519318037339769 -0.1341896851941953)), POLYGON ((-5.519318037339769 -0.1341896851941953, -5.534487809915165 -0.1511156802163569, -5.502059168210179 -0.1584592931732685, -5.519318037339769 -0.1341896851941953)), POLYGON ((-5.502059168210179 -0.1584592931732685, -5.534487809915165 -0.1511156802163569, -5.532398713360971 -0.1923112832175917, -5.502059168210179 -0.1584592931732685)), POLYGON ((-5.502059168210179 -0.1584592931732685, -5.532398713360971 -0.1923112832175917, -5.467541429951002 -0.2069985091314148, -5.502059168210179 -0.1584592931732685)), POLYGON ((-5.467541429951002 -0.2069985091314148, -5.532398713360971 -0.1923112832175917, -5.528220520252585 -0.2747024892200614, -5.467541429951002 -0.2069985091314148)), POLYGON ((-5.467541429951002 -0.2069985091314148, -5.528220520252585 -0.2747024892200614, -5.398505953432647 -0.3040769410477075, -5.467541429951002 -0.2069985091314148)), POLYGON ((-5.398505953432647 -0.3040769410477075, -5.528220520252585 -0.2747024892200614, -5.519864134035814 -0.4394849012250006, -5.398505953432647 -0.3040769410477075)), POLYGON ((-5.398505953432647 -0.3040769410477075, -5.519864134035814 -0.4394849012250006, -5.260435000395935 -0.498233804880293, -5.398505953432647 -0.3040769410477075)), POLYGON ((-5.260435000395935 -0.498233804880293, -5.519864134035814 -0.4394849012250006, -5.503151361602269 -0.7690497252348791, -5.260435000395935 -0.498233804880293)), POLYGON ((-5.260435000395935 -0.498233804880293, -5.503151361602269 -0.7690497252348791, -4.984293094322512 -0.8865475325454639, -5.260435000395935 -0.498233804880293)), POLYGON ((-4.984293094322512 -0.8865475325454639, -5.503151361602269 -0.7690497252348791, -5.469725816735179 -1.4281793732546362, -4.984293094322512 -0.8865475325454639)), POLYGON ((-4.984293094322512 -0.8865475325454639, -5.469725816735179 -1.4281793732546362, -5.139864348491315 -1.8039338300053203, -4.984293094322512 -0.8865475325454639)), POLYGON ((-4.984293094322512 -0.8865475325454639, -5.139864348491315 -1.8039338300053203, -4.432009282175666 -1.6631749878758058, -4.984293094322512 -0.8865475325454639)), POLYGON ((-5.536576898500087 -0.1099202343638762, -5.536576902484722 -0.1099201557894992, -5.5365769062203185 -0.1099200821260207, -5.536576898500087 -0.1099202343638762)), POLYGON ((-5.5365769062203185 -0.1099200821260207, -5.536576902484722 -0.1099201557894992, -5.536576905971279 -0.1099200870369192, -5.5365769062203185 -0.1099200821260207)), POLYGON ((-5.5365769062203185 -0.1099200821260207, -5.536576905971279 -0.1099200870369192, -5.536576902354522 -0.1099200830014475, -5.5365769062203185 -0.1099200821260207)), POLYGON ((-5.5365769062203185 -0.1099200821260207, -5.536576902354522 -0.1099200830014475, -5.536576904411939 -0.1099200801082848, -5.5365769062203185 -0.1099200821260207)), POLYGON ((-5.5365769062203185 -0.1099200821260207, -5.536576904411939 -0.1099200801082848, -5.536576906344838 -0.1099200796705714, -5.5365769062203185 -0.1099200821260207)), POLYGON ((-5.5365769062203185 -0.1099200821260207, -5.536576906344838 -0.1099200796705714, -5.536576906469115 -0.1099200772199179, -5.5365769062203185 -0.1099200821260207)), POLYGON ((-5.536576906469115 -0.1099200772199179, -5.536576906344838 -0.1099200796705714, -5.536576906438228 -0.1099200778289844, -5.536576906469115 -0.1099200772199179)), POLYGON ((-5.536576906469115 -0.1099200772199179, -5.536576906438228 -0.1099200778289844, -5.536576906453792 -0.1099200775220533, -5.536576906469115 -0.1099200772199179)), POLYGON ((-5.536576906469115 -0.1099200772199179, -5.536576906453792 -0.1099200775220533, -5.536576906465466 -0.1099200772918549, -5.536576906469115 -0.1099200772199179)), POLYGON ((-5.536576906469115 -0.1099200772199179, -5.536576906465466 -0.1099200772918549, -5.536576906468872 -0.1099200772247137, -5.536576906469115 -0.1099200772199179)), POLYGON ((-5.536576906469115 -0.1099200772199179, -5.536576906468872 -0.1099200772247137, -5.5365769064653385 -0.1099200772207728, -5.536576906469115 -0.1099200772199179)), POLYGON ((-5.5365769064653385 -0.1099200772207728, -5.536576906468872 -0.1099200772247137, -5.53657690646132 -0.1099200772264235, -5.5365769064653385 -0.1099200772207728)), POLYGON ((-5.5365769064653385 -0.1099200772207728, -5.53657690646132 -0.1099200772264235, -5.53657690643721 -0.1099200772603278, -5.5365769064653385 -0.1099200772207728)), POLYGON ((-5.53657690643721 -0.1099200772603278, -5.53657690646132 -0.1099200772264235, -5.536576906453284 -0.1099200772377249, -5.53657690643721 -0.1099200772603278)), POLYGON ((-5.53657690643721 -0.1099200772603278, -5.536576906453284 -0.1099200772377249, -5.5365769064674115 -0.1099200772534885, -5.53657690643721 -0.1099200772603278)), POLYGON ((-5.53657690643721 -0.1099200772603278, -5.5365769064674115 -0.1099200772534885, -5.536576906465466 -0.1099200772918549, -5.53657690643721 -0.1099200772603278)), POLYGON ((-5.53657690643721 -0.1099200772603278, -5.536576906465466 -0.1099200772918549, -5.536576906405063 -0.1099200773055334, -5.53657690643721 -0.1099200772603278)), POLYGON ((-5.53657690643721 -0.1099200772603278, -5.536576906405063 -0.1099200773055334, -5.536576906212181 -0.1099200775767674, -5.53657690643721 -0.1099200772603278)), POLYGON ((-5.536576906212181 -0.1099200775767674, -5.536576906405063 -0.1099200773055334, -5.53657690634077 -0.1099200773959448, -5.536576906212181 -0.1099200775767674)), POLYGON ((-5.536576906212181 -0.1099200775767674, -5.53657690634077 -0.1099200773959448, -5.536576906453792 -0.1099200775220533, -5.536576906212181 -0.1099200775767674)), POLYGON ((-5.536576906212181 -0.1099200775767674, -5.536576906453792 -0.1099200775220533, -5.536576906438228 -0.1099200778289844, -5.536576906212181 -0.1099200775767674)), POLYGON ((-5.536576906212181 -0.1099200775767674, -5.536576906438228 -0.1099200778289844, -5.536576905955004 -0.1099200779384128, -5.536576906212181 -0.1099200775767674)), POLYGON ((-5.536576905955004 -0.1099200779384128, -5.536576906438228 -0.1099200778289844, -5.536576906407097 -0.1099200784428467, -5.536576905955004 -0.1099200779384128)), POLYGON ((-5.536576905955004 -0.1099200779384128, -5.536576906407097 -0.1099200784428467, -5.536576905440649 -0.1099200786617034, -5.536576905955004 -0.1099200779384128)), POLYGON ((-5.536576905440649 -0.1099200786617034, -5.536576906407097 -0.1099200784428467, -5.536576906344838 -0.1099200796705714, -5.536576905440649 -0.1099200786617034)), POLYGON ((-5.536576905440649 -0.1099200786617034, -5.536576906344838 -0.1099200796705714, -5.536576904411939 -0.1099200801082848, -5.536576905440649 -0.1099200786617034)), POLYGON ((-5.536576906344838 -0.1099200796705714, -5.536576906407097 -0.1099200784428467, -5.536576906438228 -0.1099200778289844, -5.536576906344838 -0.1099200796705714)), POLYGON ((-5.536576906453792 -0.1099200775220533, -5.53657690634077 -0.1099200773959448, -5.536576906461574 -0.1099200773685877, -5.536576906453792 -0.1099200775220533)), POLYGON ((-5.536576906453792 -0.1099200775220533, -5.536576906461574 -0.1099200773685877, -5.536576906465466 -0.1099200772918549, -5.536576906453792 -0.1099200775220533)), POLYGON ((-5.536576906465466 -0.1099200772918549, -5.536576906461574 -0.1099200773685877, -5.536576906405063 -0.1099200773055334, -5.536576906465466 -0.1099200772918549)), POLYGON ((-5.536576906405063 -0.1099200773055334, -5.536576906461574 -0.1099200773685877, -5.53657690634077 -0.1099200773959448, -5.536576906405063 -0.1099200773055334)), POLYGON ((-5.536576906465466 -0.1099200772918549, -5.5365769064674115 -0.1099200772534885, -5.536576906468385 -0.1099200772343053, -5.536576906465466 -0.1099200772918549)), POLYGON ((-5.536576906465466 -0.1099200772918549, -5.536576906468385 -0.1099200772343053, -5.536576906468872 -0.1099200772247137, -5.536576906465466 -0.1099200772918549)), POLYGON ((-5.536576906468872 -0.1099200772247137, -5.536576906468385 -0.1099200772343053, -5.53657690646132 -0.1099200772264235, -5.536576906468872 -0.1099200772247137)), POLYGON ((-5.53657690646132 -0.1099200772264235, -5.536576906468385 -0.1099200772343053, -5.536576906453284 -0.1099200772377249, -5.53657690646132 -0.1099200772264235)), POLYGON ((-5.536576906453284 -0.1099200772377249, -5.536576906468385 -0.1099200772343053, -5.5365769064674115 -0.1099200772534885, -5.536576906453284 -0.1099200772377249)), POLYGON ((-5.536576904411939 -0.1099200801082848, -5.536576902354522 -0.1099200830014475, -5.536576873550677 -0.1099201235057257, -5.536576904411939 -0.1099200801082848)), POLYGON ((-5.536576873550677 -0.1099201235057257, -5.536576902354522 -0.1099200830014475, -5.536576898239687 -0.109920088787773, -5.536576873550677 -0.1099201235057257)), POLYGON ((-5.536576873550677 -0.1099201235057257, -5.536576898239687 -0.109920088787773, -5.536576890010018 -0.1099201003604239, -5.536576873550677 -0.1099201235057257)), POLYGON ((-5.536576873550677 -0.1099201235057257, -5.536576890010018 -0.1099201003604239, -5.536576904477039 -0.1099201165023106, -5.536576873550677 -0.1099201235057257)), POLYGON ((-5.536576873550677 -0.1099201235057257, -5.536576904477039 -0.1099201165023106, -5.536576902484722 -0.1099201557894992, -5.536576873550677 -0.1099201235057257)), POLYGON ((-5.536576902484722 -0.1099201557894992, -5.536576904477039 -0.1099201165023106, -5.536576905473199 -0.1099200968587164, -5.536576902484722 -0.1099201557894992)), POLYGON ((-5.536576902484722 -0.1099201557894992, -5.536576905473199 -0.1099200968587164, -5.536576905971279 -0.1099200870369192, -5.536576902484722 -0.1099201557894992)), POLYGON ((-5.536576905971279 -0.1099200870369192, -5.536576905473199 -0.1099200968587164, -5.536576898239687 -0.109920088787773, -5.536576905971279 -0.1099200870369192)), POLYGON ((-5.536576905971279 -0.1099200870369192, -5.536576898239687 -0.109920088787773, -5.536576902354522 -0.1099200830014475, -5.536576905971279 -0.1099200870369192)), POLYGON ((-5.536576898239687 -0.109920088787773, -5.536576905473199 -0.1099200968587164, -5.536576890010018 -0.1099201003604239, -5.536576898239687 -0.109920088787773)), POLYGON ((-5.536576890010018 -0.1099201003604239, -5.536576905473199 -0.1099200968587164, -5.536576904477039 -0.1099201165023106, -5.536576890010018 -0.1099201003604239)), POLYGON ((-5.536576906469115 -0.1099200772199179, -5.536576906469236 -0.10992007721752, -5.536576906469342 -0.1099200772154218, -5.536576906469115 -0.1099200772199179)), POLYGON ((-5.536576906469115 -0.1099200772199179, -5.536576906469342 -0.1099200772154218, -5.536576906469357 -0.1099200772151408, -5.536576906469115 -0.1099200772199179)), POLYGON ((-5.536576906469357 -0.1099200772151408, -5.536576906469342 -0.1099200772154218, -5.5365769064693495 -0.109920077215272, -5.536576906469357 -0.1099200772151408)), POLYGON ((-5.536576906469357 -0.1099200772151408, -5.5365769064693495 -0.109920077215272, -5.536576906469353 -0.109920077215197, -5.536576906469357 -0.1099200772151408)), POLYGON ((-5.536576906469357 -0.1099200772151408, -5.536576906469353 -0.109920077215197, -5.536576906469355 -0.1099200772151596, -5.536576906469357 -0.1099200772151408)), POLYGON ((-5.536576906469357 -0.1099200772151408, -5.536576906469355 -0.1099200772151596, -5.536576906469342 -0.1099200772151442, -5.536576906469357 -0.1099200772151408)), POLYGON ((-5.536576906469357 -0.1099200772151408, -5.536576906469342 -0.1099200772151442, -5.5365769064693495 -0.1099200772151331, -5.536576906469357 -0.1099200772151408)), POLYGON ((-5.536576906469357 -0.1099200772151408, -5.5365769064693495 -0.1099200772151331, -5.536576906469357 -0.1099200772151315, -5.536576906469357 -0.1099200772151408)), POLYGON ((-5.536576906469357 -0.1099200772151315, -5.5365769064693495 -0.1099200772151331, -5.536576906469353 -0.1099200772151276, -5.536576906469357 -0.1099200772151315)), POLYGON ((-5.536576906469357 -0.1099200772151315, -5.536576906469353 -0.1099200772151276, -5.536576906469357 -0.1099200772151268, -5.536576906469357 -0.1099200772151315)), POLYGON ((-5.536576906469357 -0.1099200772151268, -5.536576906469353 -0.1099200772151276, -5.536576906469355 -0.1099200772151249, -5.536576906469357 -0.1099200772151268)), POLYGON ((-5.536576906469357 -0.1099200772151268, -5.536576906469355 -0.1099200772151249, -5.536576906469357 -0.1099200772151244, -5.536576906469357 -0.1099200772151268)), POLYGON ((-5.536576906469355 -0.1099200772151249, -5.536576906469353 -0.1099200772151276, -5.536576906469326 -0.1099200772151662, -5.536576906469355 -0.1099200772151249)), POLYGON ((-5.536576906469355 -0.1099200772151249, -5.536576906469326 -0.1099200772151662, -5.5365769064692945 -0.1099200772152104, -5.536576906469355 -0.1099200772151249)), POLYGON ((-5.5365769064692945 -0.1099200772152104, -5.536576906469326 -0.1099200772151662, -5.536576906469353 -0.109920077215197, -5.5365769064692945 -0.1099200772152104)), POLYGON ((-5.5365769064692945 -0.1099200772152104, -5.536576906469353 -0.109920077215197, -5.5365769064693495 -0.109920077215272, -5.5365769064692945 -0.1099200772152104)), POLYGON ((-5.5365769064692945 -0.1099200772152104, -5.5365769064693495 -0.109920077215272, -5.536576906469232 -0.1099200772152987, -5.5365769064692945 -0.1099200772152104)), POLYGON ((-5.5365769064692945 -0.1099200772152104, -5.536576906469232 -0.1099200772152987, -5.536576906469106 -0.1099200772154753, -5.5365769064692945 -0.1099200772152104)), POLYGON ((-5.536576906469106 -0.1099200772154753, -5.536576906469232 -0.1099200772152987, -5.536576906469342 -0.1099200772154218, -5.536576906469106 -0.1099200772154753)), POLYGON ((-5.536576906469106 -0.1099200772154753, -5.536576906469342 -0.1099200772154218, -5.536576906469326 -0.1099200772157216, -5.536576906469106 -0.1099200772154753)), POLYGON ((-5.536576906469106 -0.1099200772154753, -5.536576906469326 -0.1099200772157216, -5.536576906468856 -0.1099200772158284, -5.536576906469106 -0.1099200772154753)), POLYGON ((-5.536576906469106 -0.1099200772154753, -5.536576906468856 -0.1099200772158284, -5.536576906468353 -0.1099200772165348, -5.536576906469106 -0.1099200772154753)), POLYGON ((-5.536576906468353 -0.1099200772165348, -5.536576906468856 -0.1099200772158284, -5.536576906469296 -0.109920077216321, -5.536576906468353 -0.1099200772165348)), POLYGON ((-5.536576906468353 -0.1099200772165348, -5.536576906469296 -0.109920077216321, -5.536576906469236 -0.10992007721752, -5.536576906468353 -0.1099200772165348)), POLYGON ((-5.536576906469236 -0.10992007721752, -5.536576906469296 -0.109920077216321, -5.536576906469342 -0.1099200772154218, -5.536576906469236 -0.10992007721752)), POLYGON ((-5.536576906469342 -0.1099200772154218, -5.536576906469296 -0.109920077216321, -5.536576906469326 -0.1099200772157216, -5.536576906469342 -0.1099200772154218)), POLYGON ((-5.536576906469326 -0.1099200772157216, -5.536576906469296 -0.109920077216321, -5.536576906468856 -0.1099200772158284, -5.536576906469326 -0.1099200772157216)), POLYGON ((-5.536576906469342 -0.1099200772154218, -5.536576906469232 -0.1099200772152987, -5.5365769064693495 -0.109920077215272, -5.536576906469342 -0.1099200772154218)), POLYGON ((-5.536576906469353 -0.109920077215197, -5.536576906469326 -0.1099200772151662, -5.536576906469355 -0.1099200772151596, -5.536576906469353 -0.109920077215197)), POLYGON ((-5.536576906469355 -0.1099200772151596, -5.536576906469326 -0.1099200772151662, -5.536576906469342 -0.1099200772151442, -5.536576906469355 -0.1099200772151596)), POLYGON ((-5.536576906469342 -0.1099200772151442, -5.536576906469326 -0.1099200772151662, -5.5365769064693495 -0.1099200772151331, -5.536576906469342 -0.1099200772151442)), POLYGON ((-5.5365769064693495 -0.1099200772151331, -5.536576906469326 -0.1099200772151662, -5.536576906469353 -0.1099200772151276, -5.5365769064693495 -0.1099200772151331)))
This is the image of the last line WKT of above debug log.
It seems there is a dead loop their. Very interesting!
But How can I solve it?
Does it related to Gabriel graph?
I set the tolerance to 1e-3 and the iteration stop before the upper bound private final static int MAX_SPLIT_ITER = 99; like this:
ConformingDelaunayTriangulationBuilder builder = new ConformingDelaunayTriangulationBuilder();
builder.setSites(polygon);
builder.setConstraints(polygon);
builder.setTolerance(1e-3); // <<<<<<<<
Geometry result = builder.getTriangles(new GeometryFactory());
The C# version of NetTopologySuite also work:
var triBuilder = new ConformingDelaunayTriangulationBuilder();
triBuilder.SetSites(bad_polygon);
triBuilder.Constraints = bad_polygon;
triBuilder.Tolerance = 1e-3;
GeometryCollection result = triBuilder.GetTriangles(new GeometryFactory());
I'm not sure if it is the correct way to solve it. So I leave it open. Hope somebody will share some information about this issue.