Re: [AD] Triangulator broken

[Trent Gamblin <trent@xxxxxxxxxx>]

On 2011-03-13, at 1:13 AM, Trent Gamblin wrote:
> I ran into this bug in the polygon triangulator. Due to the way it's written,
> I think it may be a difficult fix, but maybe Michal would be able to do it more
> easily... Here's the situation.
[snip]

Here's a test program with some data that I used. You'll need to set POLY_DEBUG
in triangulator.c to 1 for this to work. The problem hole is the last one in
the data here (splits are marked with -1, -1). If you remove that it triangulates
correctly.

Trent

outline0 = {
	2,
	1087, 1510,
	1476, 1511,
	1475, 1407,
	1409, 1408,
	1410, 1341,
	1474, 1340,
	1474, 770,
	1404, 770,
	1404, 738,
	1472, 740,
	1472, 513,
	1408, 513,
	1408, 481,
	1472, 481,
	1472, 209,
	1308, 209,
	1307, 193,
	896, 193,
	896, 423,
	1217, 423,
	1217, 472,
	1281, 473,
	1280, 511,
	896, 511,
	896, 447,
	832, 447,
	832, 255,
	704, 255,
	704, 447,
	641, 447,
	641, 511,
	577, 511,
	577, 479,
	626, 479,
	627, 390,
	639, 391,
	639, 192,
	65, 195,
	65, 384,
	388, 383,
	387, 479,
	448, 480,
	448, 511,
	63, 510,
	64, 726,
	257, 726,
	258, 771,
	64, 770,
	63, 1307,
	319, 1307,
	319, 1343,
	140, 1343,
	141, 1390,
	194, 1391,
	193, 1407,
	128, 1407,
	129, 1343,
	64, 1344,
	64, 1509,
	512, 1509,
	512, 1342,
	448, 1342,
	448, 1310,
	512, 1310,
	512, 766,
	384, 766,
	384, 734,
	704, 734,
	704, 766,
	832, 766,
	832, 734,
	1281, 733,
	1281, 765,
	1089, 765,
	1089, 925,
	1153, 925,
	1153, 957,
	1089, 957,
	1090, 1033,
	1154, 1034,
	1155, 1088,
	1087, 1089,
	1087, 1249,
	1347, 1248,
	1346, 1279,
	1088, 1280,
	-1, -1,
	470, 1450,
	470, 1425,
	493, 1425,
	493, 1450,
	-1, -1,
	396, 1173,
	382, 1114,
	436, 1102,
	452, 1160,
	-1, -1,
	140, 1174,
	126, 1117,
	181, 1102,
	196, 1161,
	-1, -1,
	266, 1045,
	254, 987,
	310, 973,
	325, 1029,
	-1, -1,
	139, 917,
	126, 860,
	180, 845,
	196, 904,
	-1, -1,
	397, 918,
	378, 859,
	436, 845,
	452, 901,
	-1, -1,
	130, 316,
	129, 264,
	194, 264,
	195, 317,
	-1, -1,
	126, 253,
	127, 202,
	195, 200,
	194, 250,
	-1, -1,
	257, 253,
	257, 201,
	321, 201,
	320, 250,
	-1, -1,
	257, 315,
	257, 263,
	322, 263,
	323, 317,
	-1, -1,
	385, 318,
	384, 265,
	448, 264,
	448, 316,
	-1, -1,
	385, 251,
	384, 201,
	449, 200,
	448, 254,
	-1, -1,
	513, 252,
	513, 199,
	576, 200,
	576, 250,
	-1, -1,
	513, 317,
	512, 262,
	577, 264,
	578, 316,
	-1, -1,
	1342, 220,
	1367, 220,
	1367, 246,
	1342, 246,
	-1, -1,
	964, 374,
	964, 328,
	1026, 328,
	1027, 380,
	-1, -1,
	962, 311,
	961, 263,
	1027, 264,
	1026, 316,
	-1, -1,
	966, 249,
	966, 199,
	1026, 199,
	1026, 250,
	-1, -1,
	1087, 251,
	1086, 200,
	1152, 199,
	1151, 251,
	-1, -1,
	1087, 315,
	1087, 262,
	1154, 263,
	1153, 318,
	-1, -1,
	1087, 380,
	1088, 328,
	1153, 328,
	1154, 379,
	-1, -1,
	1215, 379,
	1215, 326,
	1282, 327,
	1281, 379,
	-1, -1,
	1217, 316,
	1217, 262,
	1283, 262,
	1282, 314,
	-1, -1,
	1151, 1146,
	1153, 1095,
	1216, 1095,
	1216, 1144,
	-1, -1,
	1280, 960,
	1280, 928,
	1344, 928,
	1344, 960,
	-1, -1,
	1216, 254,
	1216, 201,
	1281, 200,
	1281, 252,
	-1, -1,
}

Attachment: draw_poly.cpp
Description: Binary data