Polygons do not match MVT specs

[FelixCali]

We experienced problems decoding the delivered MVTiles because they do not conform to the MVT-Specification:

• duplicate points lead to zero length line segments
• { point x, [other points] , point x } leads to illegal self intersections

Disabling checks for these anomalies worked but might cause rendering bugs.

[ARolek]

@FelixCali during mvt encoding, tegola checks if the last point and the first point are the same, and if so, drops the last point. You can see this called here and the logic here.

One thing we don't do is recheck if the first and last point are the same after the last point is dropped, so this is potentially the issue you're encountering. Could you provide the geometry that's causing issues in some way? Maybe wkb? Alternatively you could put together a quick test for the normalizePoints function to demonstrate the issue you're seeing.

If it's helpful, you can also join our slack to talk through this. We're working on updates to geom processing right now so the timing is good.

[FelixCali]

The problem does not seem to be related or at least not limited to what you described.

case 1: Duplicate consecutive points which are neither first nor last point

LINEARRING (-64 -64, 1492 -64, 1492 -59, 1489 -43, 1489 -40, 1486 -7, 1480 57, 1486 61, **1489 63, 1489 63,** 1492 65, 1492 66, 1493 66, 1497 69, 1500 71, 1505 74, 1507 76, 1510 78, 1511 79, 1514 81, 1517 83, 1519 85, 1523 87, 1525 88, 1530 91, 1532 93, 1538 96, 1541 98, 1546 101, 1548 102, 1554 106, 1556 107, 1563 111, 1564 112, 1568 115, 1569 119, 1570 124, 1572 134, 1573 139, 1574 144, 1575 157, 1576 171, 1578 199, 1574 200, 1573 200, 1565 204, 1564 204, 1560 206, 1561 208, 1563 213, 1564 215, 1565 217, 1567 222, 1568 224, 1570 229, 1572 234, 1573 238, 1574 243, 1575 248, 1576 253, 1578 283, 1579 298, 1580 314, 1583 318, 1584 320, 1586 323, 1587 324, 1590 329, 1591 331, 1594 335, 1595 337, 1596 338, 1600 345, 1616 377, 1619 380, 1620 381, 1625 387, 1629 392, 1630 394, 1629 416, 1625 418, 1623 419, 1616 423, 1611 426, 1607 429, 1605 429, 1603 430, 1600 430, 1598 431, 1596 432, 1595 432, 1594 432, 1591 433, 1590 433, 1587 434, 1586 434, 1584 435, 1583 435, 1580 436, 1579 436, 1576 437, 1575 437, 1574 438, 1570 452, 1573 470, 1590 470, 1591 469, 1594 467, 1595 466, 1596 466, 1598 465, 1604 466, 1605 467, 1611 469, 1621 481, 1620 562, 1621 565, 1623 573, 1625 575, 1629 579, 1634 585, 1637 586, 1638 586, 1646 590, 1651 593, 1654 593, 1657 593, 1663 594, 1668 595, 1672 595, 1674 595, 1677 596, 1695 605, 1697 607, 1698 609, 1702 614, 1704 617, 1706 620, 1710 625, 1711 627, 1713 629, 1716 634, 1720 639, 1721 640, 1722 642, 1725 646, 1729 651, 1731 654, 1734 658, 1736 661, 1738 664, 1739 665, 1742 669, 1745 674, 1746 675, 1750 680, 1751 682, 1753 685, 1766 691, 1770 693, 1771 694, 1781 699, 1780 698, 1779 698, 1778 698, 1774 698, 1771 697, 1770 697, 1766 696, 1763 696, 1762 696, 1760 696, 1758 694, 1755 692, 1750 689, 1746 686, 1744 685, 1742 682, 1739 678, 1736 673, 1734 671, 1730 665, 1729 664, 1724 657, 1722 654, 1720 651, 1716 646, 1713 642, 1711 639, 1706 632, 1704 629, 1700 624, 1698 621, 1697 620, 1695 618, 1691 616, 1690 615, 1689 614, 1679 608, 1677 607, 1675 606, 1674 606, 1672 606, 1671 606, 1668 606, 1663 607, 1657 608, 1651 609, 1646 609, 1638 610, 1637 610, 1634 611, 1630 611, 1629 611, 1625 612, 1623 612, 1621 612, 1620 612, 1619 613, 1617 612, 1616 612, 1611 611, 1605 609, 1603 609, 1600 608, 1598 608, 1596 607, 1595 607, 1594 607, 1591 606, 1590 606, 1587 605, 1586 605, 1584 604, 1583 604, 1580 603, 1578 603, 1576 602, 1575 602, 1573 602, 1572 601, 1570 601, 1569 601, 1568 602, 1567 603, 1564 607, 1563 609, 1561 612, 1552 630, 1549 654, 1548 663, 1549 668, 1552 686, 1554 698, 1552 710, 1549 729, 1548 735, 1546 748, 1546 711, 1541 704, 1538 700, 1532 695, 1523 687, 1522 687, 1517 683, 1514 686, 1512 688, 1511 690, 1507 712, 1500 733, 1493 736, 1492 736, 1492 737, 1489 735, 1489 734, 1486 732, 1480 728, 1476 726, 1486 703, 1480 693, 1476 686, 1471 678, 1458 657, 1457 657, 1407 655, 1388 655, 1364 656, 1326 660, 1321 662, 1311 668, 1310 669, 1301 684, 1293 698, 1287 723, 1284 754, 1287 756, 1293 761, 1301 769, 1307 777, 1310 782, 1307 781, 1301 780, 1293 778, 1287 777, 1284 777, 1268 769, 1258 754, 1240 734, 1238 734, 1229 734, 1226 734, 1222 734, 1217 735, 1211 735, 1209 735, 1196 735, 1194 736, 1182 737, 1156 742, 1152 742, 1147 742, 1145 742, 1127 743, 1122 743, 1121 743, 1113 743, 1103 744, 1097 745, 1079 751, 1069 754, 1057 760, 1043 767, 1039 769, 1032 773, 1029 774, 1016 781, 1011 783, 1007 786, 991 803, 985 816, 984 818, 975 839, 969 843, 968 844, 952 856, 944 862, 932 871, 923 878, 921 880, 889 896, 887 894, 881 890, 880 890, 875 888, 871 887, 868 886, 862 897, 857 907, 851 925, 842 972, 830 1036, 816 1075, 796 1109, 778 1133, 771 1143, 769 1145, 768 1147, 766 1150, 752 1164, 748 1166, 743 1169, 742 1170, 741 1172, 740 1174, 737 1179, 736 1181, 732 1188, 724 1212, 719 1221, 718 1223, 719 1224, 724 1230, 729 1235, 732 1239, 736 1244, 737 1245, 740 1248, 741 1250, 742 1251, 743 1252, 748 1258, 752 1263, 756 1275, 761 1282, 760 1282, 757 1282, 756 1282, 753 1283, 752 1283, 748 1283, 743 1284, 742 1284, 740 1284, 737 1285, 736 1285, 732 1285, 730 1285, 729 1286, 742 1299, 761 1308, 765 1310, 766 1310, 768 1311, 769 1312, 771 1313, 778 1322, 771 1324, 769 1325, 768 1325, 765 1327, 753 1327, 752 1326, 748 1323, 743 1319, 742 1318, 741 1317, 740 1317, 737 1314, 736 1314, 732 1311, 730 1309, 729 1308, 719 1301, 718 1300, 711 1295, 707 1292, 706 1291, 702 1290, 695 1289, 689 1287, 688 1287, 681 1286, 679 1286, 673 1286, 672 1286, 653 1287, 652 1287, 646 1288, 640 1290, 637 1292, 627 1302, 637 1314, 640 1318, 652 1328, 653 1328, 672 1329, 673 1329, 679 1332, 681 1333, 688 1337, 689 1337, 695 1341, 702 1338, 706 1337, 719 1333, 724 1332, 729 1331, 753 1343, 756 1343, 757 1344, 760 1344, 761 1345, 765 1346, 766 1346, 768 1346, 769 1347, 768 1347, 766 1348, 765 1348, 761 1350, 756 1352, 753 1353, 752 1353, 748 1355, 743 1351, 736 1347, 732 1345, 730 1344, 729 1344, 724 1347, 719 1350, 718 1350, 711 1354, 707 1356, 706 1357, 702 1356, 695 1355, 689 1354, 688 1354, 681 1352, 679 1352, 676 1352, 672 1350, 653 1343, 652 1343, 637 1344, 627 1344, 623 1345, 609 1350, 601 1352, 598 1353, 593 1355, 591 1355, 589 1356, 587 1357, 584 1358, 582 1359, 573 1364, 572 1364, 562 1369, 553 1374, 547 1377, 538 1382, 459 1431, 445 1440, 420 1445, 390 1452, 379 1455, 348 1462, 321 1478, 317 1481, 312 1485, 309 1488, 304 1493, 301 1498, 299 1501, 293 1512, 289 1527, 287 1535, 282 1662, 285 1667, 287 1670, 289 1674, 283 1678, 282 1679, 281 1680, 275 1687, 257 1719, 256 1721, 254 1722, 251 1725, 250 1726, 248 1727, 239 1735, 232 1741, 231 1741, 228 1744, 226 1746, 224 1746, 223 1747, 219 1749, 216 1750, 200 1757, 192 1760, 190 1761, 188 1762, 184 1764, 178 1766, 174 1768, 173 1768, 172 1769, 168 1771, 163 1772, 161 1772, 160 1772, 150 1775, 148 1775, 145 1776, 144 1776, 136 1778, 130 1779, 128 1780, 126 1780, 124 1781, 117 1782, 112 1784, 109 1785, 108 1786, 101 1790, 96 1793, 93 1795, 92 1795, 79 1803, 77 1804, 75 1805, 69 1809, 64 1811, 60 1814, 54 1817, 50 1820, 49 1820, 37 1827, 33 1830, 23 1858, 19 1870, 23 1884, 24 1884, 33 1888, 37 1890, 49 1896, 50 1897, 64 1895, 69 1895, 79 1894, 78 1895, 77 1897, 75 1901, 69 1902, 64 1903, 60 1904, 54 1906, 50 1907, 49 1907, 37 1910, 33 1911, 24 1914, 23 1914, 22 1915, 20 1917, 19 1917, 13 1922, 8 1926, 6 1927, 1 1931, -2 1934, -3 1934, -13 1937, -15 1938, -19 1939, -28 1942, -29 1943, -30 1942, -31 1942, -37 1941, -42 1939, -49 1938, -53 1937, -64 1934, -64 1513, -53 1513, -49 1513, -42 1513, -37 1513, -19 1516, -15 1517, 13 1523, 19 1524, 37 1528, 49 1525, 50 1524, 54 1524, 60 1520, 64 1518, 69 1515, 75 1512, 77 1511, 78 1510, 79 1510, 92 1503, 93 1503, 96 1502, 101 1500, 108 1498, 112 1496, 117 1495, 124 1493, 126 1491, 128 1489, 130 1487, 136 1482, 140 1479, 144 1479, 145 1479, 148 1479, 150 1479, 160 1480, 161 1480, 163 1480, 168 1480, 172 1480, 173 1480, 174 1481, 178 1468, 184 1457, 188 1449, 190 1446, 216 1431, 219 1430, 223 1427, 224 1427, 228 1425, 231 1423, 232 1422, 239 1419, 248 1414, 250 1411, 251 1410, 254 1407, 256 1381, 257 1369, 257 1354, 256 1353, 254 1352, 251 1351, 250 1351, 228 1351, 223 1351, 219 1351, 216 1352, 200 1353, 190 1354, 188 1354, 184 1355, 161 1355, 160 1354, 150 1352, 148 1352, 145 1351, 140 1350, 136 1349, 130 1348, 128 1347, 126 1347, 124 1347, 117 1342, 112 1330, 109 1323, 108 1322, 101 1320, 96 1319, 93 1319, 92 1320, 79 1323, 78 1323, 77 1324, 78 1323, 79 1322, 92 1314, 93 1313, 96 1312, 101 1310, 108 1308, 109 1307, 112 1307, 117 1307, 124 1307, 126 1307, 130 1306, 136 1304, 140 1304, 144 1303, 145 1303, 148 1301, 150 1300, 160 1294, 162 1293, 163 1289, 168 1271, 163 1259, 162 1258, 161 1258, 160 1257, 148 1252, 145 1251, 144 1250, 136 1247, 144 1242, 145 1241, 148 1239, 150 1238, 160 1232, 161 1231, 162 1230, 163 1230, 168 1227, 172 1224, 173 1224, 174 1224, 178 1225, 184 1226, 188 1227, 190 1227, 192 1228, 200 1230, 216 1225, 219 1222, 223 1219, 224 1219, 228 1216, 231 1213, 232 1213, 231 1196, 228 1190, 224 1183, 223 1182, 224 1176, 226 1175, 228 1175, 231 1175, 232 1175, 239 1180, 248 1174, 251 1172, 254 1170, 257 1169, 275 1149, 281 1143, 283 1141, 289 1132, 293 1119, 299 1084, 309 1057, 312 1046, 317 1028, 317 995, 312 965, 309 958, 304 948, 301 942, 299 940, 293 935, 287 930, 285 928, 283 926, 282 926, 281 925, 275 920, 257 905, 256 904, 254 902, 251 900, 250 899, 248 898, 239 894, 232 891, 231 891, 228 890, 223 888, 219 887, 216 886, 200 882, 192 880, 172 882, 168 881, 163 880, 162 879, 160 879, 150 877, 145 876, 144 876, 136 875, 130 875, 128 875, 124 875, 117 876, 112 876, 108 877, 101 878, 96 883, 93 887, 78 911, 75 914, 69 921, 64 923, 60 925, 50 926, 49 925, 37 916, 33 913, 24 907, 19 903, 13 899, 8 896, 13 889, 19 881, 20 879, 22 877, 37 859, 49 847, 50 846, 54 843, 64 819, 60 804, 54 783, 50 769, 49 766, 37 747, 33 741, 24 727, 23 726, 19 722, 13 716, 6 710, 1 706, -3 702, -13 693, -19 687, -28 679, -31 677, -37 671, -42 667, -49 660, -53 657, -64 656, -64 646, -53 643, -49 643, -42 649, -37 653, -31 659, -29 660, -28 661, -19 667, -15 670, -13 672, -3 674, 1 673, 6 673, 8 673, 13 676, 19 681, 20 682, 19 679, 13 666, 8 656, 6 651, 1 641, -2 635, -3 633, -19 604, -28 584, -30 580, -31 576, -37 555, -28 537, -19 528, -15 525, -19 521, -28 514, -31 512, -37 507, -42 503, -49 495, -53 490, -64 478, -64 -64)

case 2: Duplicate points seperated by one or more points, leading to self intersection

LINEARRING (1114 1538, **1122 1536**, 1123 1536, **1122 1536**, 1114 1538, 1114 1538)

case 3: Self intersection without duplicate points

LINEARRING (2132 2870, 2149 2891, 2152 2895, 2157 2827, 2159 2835, 2162 2848, 2167 2872, 2162 2882, 2160 2885, 2159 2888, 2157 2891, 2157 2892, 2152 2902, 2157 2937, 2157 2940, 2157 2939, 2152 2925, 2149 2917, 2132 2870)

Also not conforming to MVT specs: zero area polygons (in this case also with duplicate points):

LINEARRING (1110 1539, 1113 1538, 1114 1538, 1113 1538, 1110 1539)

Hope this helps, and I hope I got this right ;) Will joing the slack channel for further communication, we're thankful for having tegola and would love to give something back

[ARolek]

@FelixCali this is really helpful, especially as we're kicking into some improvements on the geometry processing front. Next step would be getting these into test cases. @gdey do you know if the overlapping points at the beginning and end of this polygon would be dropped during make valid? They might also get dropped during simplification but the underlying polygon appears to be invalid to me either way.

[gdey]

This should be fixed with validation. Especially the self-intersecting and duplication points. Things that could cause this is after simplification, causing self-intersection.

[pnorman]

@FelixCali Do you have a good way to generate the text and graphical forms you posted? I end up doing that kind of debugging by hand and find it slow

[tomass]

@pnorman QGIS can do all of that and even more.

[FelixCali]

@pnorman not really, I used GeoGebra, which required a lot of additional effort