TriangulateEC needs modification about geometrictools HOT 11 CLOSED

i'm starting to use this function a lot... so ... i'll report what i find... good or bad news!

from geometrictools.

I know what the problem is and how to fix it. I just have not had time to get back to it. You might want to use TriangulateCDT for now.

from geometrictools.

I am nearly at a point I now have time for finishing the work I had already done on this. I hope this will not take too long.

from geometrictools.

from geometrictools.

If you have time, send me a sample dataset for which TriangulateEC is not working correctly. I want to verify either that your dataset has the sorting problem I posted about or that this is a new problem. Thank you.

from geometrictools.

Hello

First i must say that i'm not sure that the problem comes from you! Maybe i did something wrong!!!

I use data imported from a dxf, then converted inside my code, then passed to your triangulateEC(...)
I managed to export the values of the "outer", and the 16 "inners". sorry for the bad formatting... i hope you can do something with it.

this is basically the code:

std::vector< gte::Vector2< double > > pointsPolygone;
gte::TriangulateEC< double, double > triangulator(pointsPolygone.size(), pointsPolygone.data());
triangulator(outer, inners);  // this throws a c++ exception

this is the data contained in "pointsPolygone":

outer :
n=0 : x= 81,00000000 y= 62,70000000
n=1 : x= 81,70000000 y= 62,00000000
n=2 : x= 85,00000000 y= 62,00000000
n=3 : x= 82,82283800 y= 74,34729700
n=4 : x= 80,85322300 y= 76,00000000
n=5 : x= 0,00000000 y= 76,00000000
n=6 : x= 0,00000000 y= 72,20000000
n=7 : x= 1,00000000 y= 71,20000000
n=8 : x= 2,00000000 y= 71,20000000
n=9 : x= 2,00000000 y= 72,80000000
n=10 : x= 2,50000000 y= 73,30000000
n=11 : x= 7,50000000 y= 73,30000000
n=12 : x= 8,50000000 y= 72,30000000
n=13 : x= 8,50000000 y= 65,70000000
n=14 : x= 8,00000000 y= 65,20000000
n=15 : x= 2,50000000 y= 65,20000000
n=16 : x= 2,00000000 y= 65,70000000
n=17 : x= 2,00000000 y= 67,20000000
n=18 : x= 1,00000000 y= 67,20000000
n=19 : x= 0,20000000 y= 66,40000000
n=20 : x= 0,20000000 y= 60,00000000
n=21 : x= 1,00000000 y= 59,20000000
n=22 : x= 2,00000000 y= 59,20000000
n=23 : x= 2,00000000 y= 60,70000000
n=24 : x= 2,50000000 y= 61,20000000
n=25 : x= 8,00000000 y= 61,20000000
n=26 : x= 8,50000000 y= 60,70000000
n=27 : x= 8,50000000 y= 46,11547000
n=28 : x= 8,70000000 y= 46,00000000
n=29 : x= 8,50000000 y= 45,88453000
n=30 : x= 8,50000000 y= 15,30000000
n=31 : x= 8,00000000 y= 14,80000000
n=32 : x= 2,50000000 y= 14,80000000
n=33 : x= 2,00000000 y= 15,30000000
n=34 : x= 2,00000000 y= 16,80000000
n=35 : x= 1,00000000 y= 16,80000000
n=36 : x= 0,20000000 y= 16,00000000
n=37 : x= 0,20000000 y= 9,60000000
n=38 : x= 1,00000000 y= 8,80000000
n=39 : x= 2,00000000 y= 8,80000000
n=40 : x= 2,00000000 y= 10,30000000
n=41 : x= 2,50000000 y= 10,80000000
n=42 : x= 8,00000000 y= 10,80000000
n=43 : x= 8,50000000 y= 10,30000000
n=44 : x= 8,50000000 y= 3,70000000
n=45 : x= 7,50000000 y= 2,70000000
n=46 : x= 2,50000000 y= 2,70000000
n=47 : x= 2,00000000 y= 3,20000000
n=48 : x= 2,00000000 y= 4,80000000
n=49 : x= 1,00000000 y= 4,80000000
n=50 : x= 0,00000000 y= 3,80000000
n=51 : x= 0,00000000 y= 0,00000000
n=52 : x= 64,00000000 y= 0,00000000
n=53 : x= 64,00000000 y= 4,00000000
n=54 : x= 62,00000000 y= 4,00000000
n=55 : x= 61,25464401 y= 3,66666667
n=56 : x= 59,76393200 y= 3,00000000
n=57 : x= 58,00000000 y= 3,00000000
n=58 : x= 56,00000000 y= 5,00000000
n=59 : x= 56,00000000 y= 8,50000000
n=60 : x= 57,00000000 y= 9,50000000
n=61 : x= 57,50000000 y= 9,50000000
n=62 : x= 58,50000000 y= 8,50000000
n=63 : x= 58,50000000 y= 8,00000000
n=64 : x= 63,80000000 y= 8,00000000
n=65 : x= 63,80000000 y= 11,50000000
n=66 : x= 61,25881900 y= 10,81909300
n=67 : x= 60,00000000 y= 11,78501900
n=68 : x= 60,00000000 y= 52,75000000
n=69 : x= 57,59226900 y= 60,39953200
n=70 : x= 59,69134998 y= 62,99082525
n=71 : x= 70,00000000 y= 62,00000000
n=72 : x= 77,10000000 y= 62,00000000
n=73 : x= 77,80000000 y= 62,70000000
n=74 : x= 77,80000000 y= 63,50000000
n=75 : x= 77,00000000 y= 63,50000000
n=76 : x= 76,50759612 y= 64,08682409
n=77 : x= 76,78739600 y= 65,67364800
n=78 : x= 77,77220400 y= 66,50000000
n=79 : x= 81,33657600 y= 66,50000000
n=80 : x= 82,32138375 y= 65,67364818
n=81 : x= 82,60118300 y= 64,08682400
n=82 : x= 82,10877900 y= 63,50000000
n=83 : x= 81,00000000 y= 63,50000000
inner 0 :
n=84 : x= 26,70000000 y= 54,50000000
n=85 : x= 11,20000000 y= 54,50000000
n=86 : x= 10,70000000 y= 55,00000000
n=87 : x= 10,70000000 y= 64,70000000
n=88 : x= 11,20000000 y= 65,20000000
n=89 : x= 26,70000000 y= 65,20000000
n=90 : x= 27,20000000 y= 64,70000000
n=91 : x= 27,20000000 y= 55,00000000
inner 1 :
n=92 : x= 57,80000000 y= 24,70000000
n=93 : x= 57,30000000 y= 24,20000000
n=94 : x= 56,80000000 y= 24,20000000
n=95 : x= 56,80000000 y= 23,20000000
n=96 : x= 57,30000000 y= 23,20000000
n=97 : x= 57,80000000 y= 22,70000000
n=98 : x= 57,80000000 y= 18,40000000
n=99 : x= 57,30000000 y= 17,90000000
n=100 : x= 11,20000000 y= 17,90000000
n=101 : x= 10,70000000 y= 18,40000000
n=102 : x= 10,70000000 y= 53,00000000
n=103 : x= 11,20000000 y= 53,50000000
n=104 : x= 57,09072300 y= 53,50000000
n=105 : x= 57,56765600 y= 53,15011700
n=106 : x= 57,80000000 y= 52,41194400
n=107 : x= 57,80000000 y= 48,70000000
n=108 : x= 57,30000000 y= 48,20000000
n=109 : x= 56,80000000 y= 48,20000000
n=110 : x= 56,80000000 y= 47,20000000
n=111 : x= 57,30000000 y= 47,20000000
n=112 : x= 57,80000000 y= 46,70000000
inner 2 :
n=113 : x= 47,40000000 y= 16,40000000
n=114 : x= 47,40000000 y= 10,00000000
n=115 : x= 46,90000000 y= 9,50000000
n=116 : x= 28,50000000 y= 9,50000000
n=117 : x= 28,00000000 y= 10,00000000
n=118 : x= 28,00000000 y= 16,40000000
n=119 : x= 28,50000000 y= 16,90000000
n=120 : x= 46,90000000 y= 16,90000000
inner 3 :
n=121 : x= 8,50000000 y= 12,10000000
n=122 : x= 8,00000000 y= 11,60000000
n=123 : x= 2,50000000 y= 11,60000000
n=124 : x= 1,52500000 y= 11,15986965
n=125 : x= 1,00000000 y= 11,35830100
n=126 : x= 1,00000000 y= 14,24170000
n=127 : x= 1,52500000 y= 14,44013083
n=128 : x= 2,50000000 y= 14,00000000
n=129 : x= 8,00000000 y= 14,00000000
n=130 : x= 8,50000000 y= 13,50000000
inner 4 :
n=131 : x= 10,70000000 y= 8,20000000
n=132 : x= 11,20000000 y= 8,70000000
n=133 : x= 26,70000000 y= 8,70000000
n=134 : x= 27,20000000 y= 8,20000000
n=135 : x= 27,20000000 y= 3,70000000
n=136 : x= 26,20000000 y= 2,70000000
n=137 : x= 11,70000000 y= 2,70000000
n=138 : x= 10,70000000 y= 3,70000000
inner 5 :
n=139 : x= 48,20000000 y= 3,70000000
n=140 : x= 48,20000000 y= 8,20000000
n=141 : x= 48,70000000 y= 8,70000000
n=142 : x= 53,30000000 y= 8,70000000
n=143 : x= 53,80000000 y= 8,20000000
n=144 : x= 53,80000000 y= 7,40000000
n=145 : x= 53,30000000 y= 6,90000000
n=146 : x= 53,20000000 y= 6,90000000
n=147 : x= 52,70000000 y= 6,40000000
n=148 : x= 52,70000000 y= 5,60000000
n=149 : x= 53,20000000 y= 5,10000000
n=150 : x= 53,30000000 y= 5,10000000
n=151 : x= 53,80000000 y= 4,60000000
n=152 : x= 53,80000000 y= 3,70000000
n=153 : x= 52,80000000 y= 2,70000000
n=154 : x= 49,20000000 y= 2,70000000
inner 6 :
n=155 : x= 28,50000000 y= 65,20000000
n=156 : x= 42,10000000 y= 65,20000000
n=157 : x= 42,60000000 y= 64,70000000
n=158 : x= 42,60000000 y= 55,00000000
n=159 : x= 42,10000000 y= 54,50000000
n=160 : x= 28,50000000 y= 54,50000000
n=161 : x= 28,00000000 y= 55,00000000
n=162 : x= 28,00000000 y= 64,70000000
inner 7 :
n=163 : x= 57,17216400 y= 65,19337300
n=164 : x= 55,33729917 y= 72,04118095
n=165 : x= 56,30322500 y= 73,30000000
n=166 : x= 79,84630300 y= 73,30000000
n=167 : x= 80,33870700 y= 72,88682400
n=168 : x= 80,97348488 y= 69,28682409
n=169 : x= 80,48108100 y= 68,70000000
n=170 : x= 77,77220400 y= 68,70000000
n=171 : x= 74,62081900 y= 66,05567400
n=172 : x= 74,36646788 y= 64,61317591
n=173 : x= 73,87406400 y= 64,20000000
n=174 : x= 70,10548400 y= 64,20000000
n=175 : x= 59,90183497 y= 65,18073303
n=176 : x= 57,85139006 y= 64,86291157
inner 8 :
n=177 : x= 28,00000000 y= 66,50000000
n=178 : x= 28,00000000 y= 72,30000000
n=179 : x= 29,00000000 y= 73,30000000
n=180 : x= 41,60000000 y= 73,30000000
n=181 : x= 42,60000000 y= 72,30000000
n=182 : x= 42,60000000 y= 66,50000000
n=183 : x= 42,10000000 y= 66,00000000
n=184 : x= 28,50000000 y= 66,00000000
inner 9 :
n=185 : x= 10,70000000 y= 72,30000000
n=186 : x= 11,70000000 y= 73,30000000
n=187 : x= 26,20000000 y= 73,30000000
n=188 : x= 27,20000000 y= 72,30000000
n=189 : x= 27,20000000 y= 66,50000000
n=190 : x= 26,70000000 y= 66,00000000
n=191 : x= 11,20000000 y= 66,00000000
n=192 : x= 10,70000000 y= 66,50000000
inner 10 :
n=193 : x= 43,90000000 y= 54,50000000
n=194 : x= 43,40000000 y= 55,00000000
n=195 : x= 43,40000000 y= 64,47063900
n=196 : x= 44,05450800 y= 64,94616800
n=197 : x= 54,95504750 y= 61,40436826
n=198 : x= 55,30048142 y= 60,93640982
n=199 : x= 55,49376500 y= 59,73901600
n=200 : x= 56,93814575 y= 55,15011714
n=201 : x= 56,46121300 y= 54,50000000
inner 11 :
n=202 : x= 8,00000000 y= 64,40000000
n=203 : x= 8,50000000 y= 63,90000000
n=204 : x= 8,50000000 y= 62,50000000
n=205 : x= 8,00000000 y= 62,00000000
n=206 : x= 2,50000000 y= 62,00000000
n=207 : x= 1,52500000 y= 61,55986965
n=208 : x= 1,00000000 y= 61,75830100
n=209 : x= 1,00000000 y= 64,64170000
n=210 : x= 1,52500000 y= 64,84013083
n=211 : x= 2,50000000 y= 64,40000000
inner 12 :
n=212 : x= 57,30000000 y= 16,90000000
n=213 : x= 57,80000000 y= 16,40000000
n=214 : x= 57,80000000 y= 12,20000000
n=215 : x= 57,30000000 y= 11,70000000
n=216 : x= 57,00000000 y= 11,70000000
n=217 : x= 54,07476150 y= 9,79729730
n=218 : x= 53,61769300 y= 9,50000000
n=219 : x= 48,70000000 y= 9,50000000
n=220 : x= 48,20000000 y= 10,00000000
n=221 : x= 48,20000000 y= 16,40000000
n=222 : x= 48,70000000 y= 16,90000000
inner 13 :
n=223 : x= 26,70000000 y= 16,90000000
n=224 : x= 27,20000000 y= 16,40000000
n=225 : x= 27,20000000 y= 10,00000000
n=226 : x= 26,70000000 y= 9,50000000
n=227 : x= 11,20000000 y= 9,50000000
n=228 : x= 10,70000000 y= 10,00000000
n=229 : x= 10,70000000 y= 16,40000000
n=230 : x= 11,20000000 y= 16,90000000
inner 14 :
n=231 : x= 44,40000000 y= 4,40000000
n=232 : x= 44,40000000 y= 3,50000000
n=233 : x= 43,40000000 y= 3,50000000
n=234 : x= 43,40000000 y= 4,40000000
n=235 : x= 42,20000000 y= 4,40000000
n=236 : x= 42,20000000 y= 3,70000000
n=237 : x= 41,20000000 y= 2,70000000
n=238 : x= 29,00000000 y= 2,70000000
n=239 : x= 28,00000000 y= 3,70000000
n=240 : x= 28,00000000 y= 8,20000000
n=241 : x= 28,50000000 y= 8,70000000
n=242 : x= 46,90000000 y= 8,70000000
n=243 : x= 47,40000000 y= 8,20000000
n=244 : x= 47,40000000 y= 5,50000000
n=245 : x= 47,03636364 y= 5,01895483
n=246 : x= 46,60000000 y= 4,44170000
n=247 : x= 46,60000000 y= 3,50000000
n=248 : x= 45,60000000 y= 3,50000000
n=249 : x= 45,60000000 y= 4,40000000
inner 15 :
n=250 : x= 54,37037800 y= 72,55881900
n=251 : x= 56,56769191 y= 64,35833052
n=252 : x= 56,44805610 y= 63,88541824
n=253 : x= 55,59001265 y= 62,53362377
n=254 : x= 54,97003000 y= 62,24067000
n=255 : x= 43,74549150 y= 65,88774274
n=256 : x= 43,40000000 y= 66,36327100
n=257 : x= 43,40000000 y= 72,30000000
n=258 : x= 44,40000000 y= 73,30000000
n=259 : x= 53,40445200 y= 73,30000000

from geometrictools.

Thanks. Any dataset is better than none :)

from geometrictools.

btw, TriangulateCDT works very well for me, and fast !

from geometrictools.

I wrote a simple program to triangulate your sample dataset and visualize it. The triangulation appears to be correct. What problem were you having? Here are two screen captures, one showing the outer and inner polygons. The other shows the triangulation. I tried this with ComputeType of double and of a rational type. If you want the program project, let me know and I will post it to a temporary folder at my website.

from geometrictools.

from geometrictools.

I posted an update to TriangulateEC.h. The revised documentation is Triangulation by Ear Clipping.

from geometrictools.