TriangulateEC needs modification

[davideberly]

Over several years, I have had reports that when an outer-polygon vertex is visible to multiple inner-polygon vertices, the x-sort is necessary to choose the first inner polygon to combine with the outer polygon. However, combining the remaining inner polygons using decreasing x-value does not always work. No reproducers were provided to me, apparently because the reporters implemented the algorithm from the PDF. In the Geometric Tools implementation, the problem does not occur with 2 inner polygons. It is possible to choose a configuration of 3 inner polygons to demonstrate the need for the additional sorting. This step requires a sort of the inner-polygon extreme vertices in a circular manner about the outer-polygon vertex. I had previously added SortPointsOnCircle.h to support this. The TriangulateEC code needs to include this sort.

[owai1980]

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

[davideberly]

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.

[davideberly]

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.

[owai1980]

Thank you!! 👍

Indeed I have some problems with the EC, and i was going to test the other method CDT

Good luck! 👍

Le lun. 9 oct. 2023 à 04:57, David Eberly @.***> a écrit :

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.

— Reply to this email directly, view it on GitHub https://github.com/davideberly/GeometricTools/issues/56#issuecomment-1752281259, or unsubscribe https://github.com/notifications/unsubscribe-auth/AG3BAQMSN5QS3Z2AJA5UTBLX6NR2LAVCNFSM6AAAAAAVYNRY3KVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTONJSGI4DCMRVHE . You are receiving this because you commented.Message ID: @.***>

[davideberly]

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.

[owai1980]

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

[davideberly]

Thanks. Any dataset is better than none :)

[owai1980]

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

[davideberly]

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.

[owai1980]

Wow ... It seems perfect!

My problem was a memory error, program stopped working... I tried many times, using embarcadero c++ builder. I did not investigate more...

Right now, I'm working with the triangulateCDT, and it works perfect for me!

Le sam. 14 oct. 2023 à 23:31, David Eberly @.***> a écrit :

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.

[image: Polygons] https://user-images.githubusercontent.com/70985517/275289493-08c608d0-2c1e-4ae4-848a-ba902f47e78e.png [image: PolygonsAndTriangles] https://user-images.githubusercontent.com/70985517/275289491-5524cb85-a942-4c64-b514-d0f66fc8c0c5.png

— Reply to this email directly, view it on GitHub https://github.com/davideberly/GeometricTools/issues/56#issuecomment-1763186183, or unsubscribe https://github.com/notifications/unsubscribe-auth/AG3BAQNJV3DYPJ7ZAFV42QDX7MAEPANCNFSM6AAAAAAVYNRY3I . You are receiving this because you commented.Message ID: @.***>

[davideberly]

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