problem about polytree's build #576

zengguang-xu · 2023-07-06T09:32:28Z

zengguang-xu
Jul 6, 2023

First of all, thank you very much for helping me with my question. Secondly, I am very sorry for giving you the wrong clip path, in fact, my clip path is a pile of polygons. Could you please help me take a look again? The process flow has not changed. and the correct subject and clips are as follows：

the subjects has only one polygon:
subjects = [(-2600,-4247), (7400,-4247), (7400,5760), (-2600,5760), (-2600,-4247)]

but the clips is composed of multiple polygons，every clip is a closed polygon：
clips = [
[(-258,-605), (-1788,-605), (-1718,-674), (-488,-1905), (332,-1085), (-258,-1085), (-258,-605)],
[(1005,-2843), (441,-3407), (1005,-3407), (1005,-2843)],
[(545,-872), (332,-1085), (758,-1085), (545,-872)],
[(27,-246), (241,-246), (241,-172), (27,-172), (27,-246)],
[(-347,-249), (-287,-249), (-287,174), (-347,174), (-347,-249)],
[(-347,257), (-729,257), (-729,-331), (-347,-331), (-347,-249), (-444,-249), (-444,174), (-504,174), (-504,-249), (-651,-249), (-651,174), (-347,174), (-347,257)],
[(-102,-172), (-42,-172), (-42,126), (-102,126), (-102,-172)],
[(241,-172), (301,-172), (301,126), (241,126), (241,-172)],
[(-42,126), (241,126), (241,200), (-42,200), (-42,126)],
[(555,-73), (1158,-73), (1158,181), (555,181), (555,-73)],
[(1597,-2250), (1005,-2250), (1005,-2843), (1597,-2250)],
[(1239,-1085), (758,-1085), (1239,-1566), (1239,-1085)],
[(1239,-807), (1239,-1085), (1517,-1085), (1239,-807)],
[(2165,-1085), (1517,-1085), (1841,-1409), (2165,-1085)],
[(4146,-1015), (3574,-1015), (3860,-1301), (4146,-1015)],
[(3164,-605), (3164,-1015), (3574,-1015), (3164,-605)],
[(2773,-477), (2165,-1085), (2773,-1085), (2773,-477)],
[(1942,-251), (2193,-251), (2193,333), (1942,333), (1942,-251)],
[(2583,-123), (2793,-123), (2793,333), (2583,333), (2583,-123)],
[(3521,243), (3521,-88), (3802,-88), (3802,-38), (3521,243)],
[(3802,483), (3802,-38), (4012,-248), (4012,273), (3802,483)],
[(3003,0), (3229,0), (3229,333), (3003,333), (3003,0)],
[(-1296,1494), (-1790,1494), (-1790,1334), (-1438,1334), (-1438,896), (-1790,896), (-1790,1334), (-1969,1334), (-1969,829), (-1296,829), (-1296,1494)],
[(-1882,1628), (-1584,1628), (-1584,1688), (-1882,1688), (-1882,1628)],
[(-1240,743), (-1913,743), (-1913,78), (-1598,78), (-1598,-267), (-925,-267), (-925,398), (-1240,398), (-1240,676), (-1419,676), (-1419,238), (-1067,238), (-1067,-200), (-1419,-200), (-1419,238), (-1771,238), (-1771,676), (-1240,676), (-1240,743)],
[(72,992), (-422,992), (-422,832), (-70,832), (-70,394), (-422,394), (-422,832), (-601,832), (-601,327), (72,327), (72,992)],
[(-422,1497), (-1095,1497), (-1095,832), (-601,832), (-601,992), (-953,992), (-953,1430), (-601,1430), (-601,992), (-422,992), (-422,1497)],
[(48,2270), (-625,2270), (-625,1605), (-222,1605), (-222,1161), (451,1161), (451,1826), (48,1826), (48,2203), (-131,2203), (-131,1765), (-43,1765), (-43,1666), (309,1666), (309,1228), (-43,1228), (-43,1666), (-131,1666), (-131,1765), (-483,1765), (-483,2203), (48,2203), (48,2270)],
[(-1956,1688), (-1882,1688), (-1882,1971), (-1956,1971), (-1956,1688)],
[(-1882,1971), (-1584,1971), (-1584,2031), (-1882,2031), (-1882,1971)],
[(-1584,1757), (-1510,1757), (-1510,1971), (-1584,1971), (-1584,1757)],
[(-724,2030), (-806,2030), (-806,1933), (-1229,1933), (-1229,2030), (-1312,2030), (-1312,1648), (-724,1648), (-724,1873), (-806,1873), (-806,1726), (-1229,1726), (-1229,1873), (-724,1873), (-724,2030)],
[(-1229,2030), (-806,2030), (-806,2090), (-1229,2090), (-1229,2030)],
[(1421,2115), (744,2115), (744,777), (1488,777), (1488,1079), (965,1079), (965,1930), (1421,1930), (1421,2115)],
[(1158,181), (1728,181), (1728,408), (1158,408), (1158,181)],
[(2193,333), (2583,333), (2583,574), (2193,574), (2193,333)],
[(3102,1443), (2667,1443), (2667,1079), (1764,1079), (1764,771), (3102,771), (3102,1443)],
[(2793,333), (3003,333), (3003,533), (2793,533), (2793,333)],
[(3229,333), (3403,333), (3403,697), (3229,697), (3229,333)],
[(4042,1295), (4042,1261), (4076,1261), (4042,1295)],
[(1488,1079), (1764,1079), (1764,1556), (1488,1556), (1488,1079)],
[(2062,2053), (2667,2053), (2667,2299), (2062,2299), (2062,2053)],
[(2072,1443), (2667,1443), (2667,1735), (2072,1735), (2072,1443)],
[(4042,1875), (3461,1875), (4042,1295), (4042,1875)],
[(2667,1735), (3231,1735), (3231,2053), (2667,2053), (2667,1735)],
[(4545,-615), (4146,-1015), (4545,-1015), (4545,-615)],
[(6375,-579), (5782,-579), (6375,-1171), (6375,-579)],
[(5218,-15), (5218,-579), (5782,-579), (5218,-15)],
[(6015,2497), (4773,2497), (5133,2137), (5133,1660), (4282,1660), (4680,1261), (4076,1261), (4333,1004), (4012,1004), (4012,273), (4608,-323), (5449,518), (6335,518), (6335,1554), (6024,1865), (6035,1876), (5394,1876), (5610,1660), (5178,1660), (5394,1876), (6035,1876), (6504,2346), (5864,2346), (6015,2497)],
[(1208,-4247), (1441,-4247), (1441,-4080), (1041,-4080), (1208,-4247)],
[(-1128,-2290), (-1439,-2601), (-1920,-2121), (-1920,-2761), (-2071,-2610), (-2071,-3852), (-1711,-3492), (-1234,-3492), (-1234,-4247), (-1138,-4247), (-835,-3945), (-835,-4247), (519,-4247), (749,-4017), (-92,-3176), (-92,-3015), (-1234,-3015), (-1234,-3447), (-1450,-3231), (-1234,-3015), (-92,-3015), (-92,-2290), (-1128,-2290)],
[(7400,-573), (7400,-422), (7249,-573), (7400,-573)],
[(7400,664), (7400,1644), (6910,1154), (7400,664)],
[(1600,5660), (1600,5760), (-2600,5760), (-2600,5660), (-2000,5660), (-2000,5160), (-2600,5160), (-2600,4960), (-2000,4960), (-2000,4360), (-2600,4360), (-2600,4160), (-2000,4160), (-2000,3660), (-2600,3660), (-2600,3460), (-2000,3460), (-2000,2860), (-1800,2860), (-1800,3460), (-1300,3460), (-1300,2860), (-1100,2860), (-1100,3460), (-600,3460), (-600,2860), (-400,2860), (-400,3460), (100,3460), (100,2860), (300,2860), (300,3460), (800,3460), (800,2860), (1000,2860), (1000,3460), (1600,3460), (1600,3660), (1000,3660), (1000,4160), (800,4160), (800,3660), (300,3660), (300,4160), (100,4160), (100,3660), (-400,3660), (-400,4160), (-600,4160), (-600,3660), (-1100,3660), (-1100,4160), (-1300,4160), (-1300,3660), (-1800,3660), (-1800,4160), (1600,4160), (1600,4360), (1000,4360), (1000,4860), (1600,4860), (1600,4960), (800,4960), (800,4360), (300,4360), (300,4960), (100,4960), (100,4360), (-400,4360), (-400,4960), (-600,4960), (-600,4360), (-1100,4360), (-1100,4960), (-1300,4960), (-1300,4360), (-1800,4360), (-1800,4960), (1600,4960), (1600,5060), (1000,5060), (1000,5560), (1600,5560), (1600,5660), (800,5660), (800,5160), (300,5160), (300,5660), (100,5660), (100,5160), (-400,5160), (-400,5660), (-600,5660), (-600,5160), (-1100,5160), (-1100,5660), (-1300,5660), (-1300,5160), (-1800,5160), (-1800,5660), (1600,5660)],
[(5840,5760), (2240,5760), (2240,5600), (2840,5600), (2840,5100), (2240,5100), (2240,4900), (2840,4900), (2840,4300), (2240,4300), (2240,4100), (2840,4100), (2840,3600), (2240,3600), (2240,3400), (2840,3400), (2840,2800), (3040,2800), (3040,3400), (3540,3400), (3540,2800), (3740,2800), (3740,3400), (4240,3400), (4240,2800), (4440,2800), (4440,3400), (4940,3400), (4940,2800), (5140,2800), (5140,3400), (5640,3400), (5640,2800), (5840,2800), (5840,3400), (6440,3400), (6440,3600), (5840,3600), (5840,4100), (5640,4100), (5640,3600), (5140,3600), (5140,4100), (4940,4100), (4940,3600), (4440,3600), (4440,4100), (4240,4100), (4240,3600), (3740,3600), (3740,4100), (3540,4100), (3540,3600), (3040,3600), (3040,4100), (6440,4100), (6440,4300), (5840,4300), (5840,4800), (6440,4800), (6440,4900), (5640,4900), (5640,4300), (5140,4300), (5140,4900), (4940,4900), (4940,4300), (4440,4300), (4440,4900), (4240,4900), (4240,4300), (3740,4300), (3740,4900), (3540,4900), (3540,4300), (3040,4300), (3040,4900), (6440,4900), (6440,5000), (5840,5000), (5840,5500), (6440,5500), (6440,5600), (5640,5600), (5640,5100), (5140,5100), (5140,5600), (4940,5600), (4940,5100), (4440,5100), (4440,5600), (4240,5600), (4240,5100), (3740,5100), (3740,5600), (3540,5600), (3540,5100), (3040,5100), (3040,5600), (6440,5600), (6440,5700), (5840,5700), (5840,5760)],
[(6920,5660), (7400,5660), (7400,5760), (6920,5760), (6920,5660)],
[(6920,4960), (7400,4960), (7400,5160), (6920,5160), (6920,4960)],
[(6920,4160), (7400,4160), (7400,4360), (6920,4360), (6920,4160)],
[(6920,3460), (7400,3460), (7400,3660), (6920,3660), (6920,3460)]
]

and the processed result is as follows. It can be seen that many holes are overlapped as polygons：

BigZebra101010 · 2023-07-06T23:39:10Z

BigZebra101010
Jul 6, 2023

I have reproduced the issue.

1、I add a function in PolygonSamples.cpp, called MyPolygons

void MyPolygons()
{
    Paths64 subject, clip;
    PolyTree64 solution;
    ClipType ct = ClipType::Xor;
    FillRule fr = FillRule::NonZero;

    std::ifstream ifs(".\\MyPolygons.txt");

    if (!MyLoadTest(ifs, subject, clip)) return;
    Clipper64 c64;
    c64.AddSubject(subject);
    c64.AddClip(clip);
    if (!c64.Execute(ct, fr, solution)) return;

    std::cout << "tree solution: " << std::endl;
    std::cout << solution;

    Paths64 ss = PolyTreeToPaths64(solution);

    SvgWriter svg;
    //SvgAddSubject(svg, subject, fr);
    //SvgAddClip(svg, clip, fr);
    //if (fr == FillRule::Negative)
    //    for (auto& path : solution) std::reverse(path.begin(), path.end());
    SvgAddSolution(svg, ss, fr, true);
    std::string filename = "my_poly.svg";
    SvgSaveToFile(svg, filename, 3000, 1000, 10);
    System(filename);
}

MyPolygons.txt:

SUBJECTS
-2600,-4247, 7400,-4247, 7400,5760, -2600,5760, -2600,-4247
CLIPS
-258,-605, -1788,-605, -1718,-674, -488,-1905, 332,-1085, -258,-1085, -258,-605,
1005,-2843, 441,-3407, 1005,-3407, 1005,-2843,
545,-872, 332,-1085, 758,-1085, 545,-872,
27,-246, 241,-246, 241,-172, 27,-172, 27,-246,
-347,-249, -287,-249, -287,174, -347,174, -347,-249,
-347,257, -729,257, -729,-331, -347,-331, -347,-249, -444,-249, -444,174, -504,174, -504,-249, -651,-249, -651,174, -347,174, -347,257,
-102,-172, -42,-172, -42,126, -102,126, -102,-172,
241,-172, 301,-172, 301,126, 241,126, 241,-172,
-42,126, 241,126, 241,200, -42,200, -42,126,
555,-73, 1158,-73, 1158,181, 555,181, 555,-73,
1597,-2250, 1005,-2250, 1005,-2843, 1597,-2250,
1239,-1085, 758,-1085, 1239,-1566, 1239,-1085,
1239,-807, 1239,-1085, 1517,-1085, 1239,-807,
2165,-1085, 1517,-1085, 1841,-1409, 2165,-1085,
4146,-1015, 3574,-1015, 3860,-1301, 4146,-1015,
3164,-605, 3164,-1015, 3574,-1015, 3164,-605,
2773,-477, 2165,-1085, 2773,-1085, 2773,-477,
1942,-251, 2193,-251, 2193,333, 1942,333, 1942,-251,
2583,-123, 2793,-123, 2793,333, 2583,333, 2583,-123,
3521,243, 3521,-88, 3802,-88, 3802,-38, 3521,243,
3802,483, 3802,-38, 4012,-248, 4012,273, 3802,483,
3003,0, 3229,0, 3229,333, 3003,333, 3003,0,
-1296,1494, -1790,1494, -1790,1334, -1438,1334, -1438,896, -1790,896, -1790,1334, -1969,1334, -1969,829, -1296,829, -1296,1494,
-1882,1628, -1584,1628, -1584,1688, -1882,1688, -1882,1628,
-1240,743, -1913,743, -1913,78, -1598,78, -1598,-267, -925,-267, -925,398, -1240,398, -1240,676, -1419,676, -1419,238, -1067,238, -1067,-200, -1419,-200, -1419,238, -1771,238, -1771,676, -1240,676, -1240,743,
72,992, -422,992, -422,832, -70,832, -70,394, -422,394, -422,832, -601,832, -601,327, 72,327, 72,992,
-422,1497, -1095,1497, -1095,832, -601,832, -601,992, -953,992, -953,1430, -601,1430, -601,992, -422,992, -422,1497,
48,2270, -625,2270, -625,1605, -222,1605, -222,1161, 451,1161, 451,1826, 48,1826, 48,2203, -131,2203, -131,1765, -43,1765, -43,1666, 309,1666, 309,1228, -43,1228, -43,1666, -131,1666, -131,1765, -483,1765, -483,2203, 48,2203, 48,2270,
-1956,1688, -1882,1688, -1882,1971, -1956,1971, -1956,1688,
-1882,1971, -1584,1971, -1584,2031, -1882,2031, -1882,1971,
-1584,1757, -1510,1757, -1510,1971, -1584,1971, -1584,1757,
-724,2030, -806,2030, -806,1933, -1229,1933, -1229,2030, -1312,2030, -1312,1648, -724,1648, -724,1873, -806,1873, -806,1726, -1229,1726, -1229,1873, -724,1873, -724,2030,
-1229,2030, -806,2030, -806,2090, -1229,2090, -1229,2030,
1421,2115, 744,2115, 744,777, 1488,777, 1488,1079, 965,1079, 965,1930, 1421,1930, 1421,2115,
1158,181, 1728,181, 1728,408, 1158,408, 1158,181,
2193,333, 2583,333, 2583,574, 2193,574, 2193,333,
3102,1443, 2667,1443, 2667,1079, 1764,1079, 1764,771, 3102,771, 3102,1443,
2793,333, 3003,333, 3003,533, 2793,533, 2793,333,
3229,333, 3403,333, 3403,697, 3229,697, 3229,333,
4042,1295, 4042,1261, 4076,1261, 4042,1295,
1488,1079, 1764,1079, 1764,1556, 1488,1556, 1488,1079,
2062,2053, 2667,2053, 2667,2299, 2062,2299, 2062,2053,
2072,1443, 2667,1443, 2667,1735, 2072,1735, 2072,1443,
4042,1875, 3461,1875, 4042,1295, 4042,1875,
2667,1735, 3231,1735, 3231,2053, 2667,2053, 2667,1735,
4545,-615, 4146,-1015, 4545,-1015, 4545,-615,
6375,-579, 5782,-579, 6375,-1171, 6375,-579,
5218,-15, 5218,-579, 5782,-579, 5218,-15,
6015,2497, 4773,2497, 5133,2137, 5133,1660, 4282,1660, 4680,1261, 4076,1261, 4333,1004, 4012,1004, 4012,273, 4608,-323, 5449,518, 6335,518, 6335,1554, 6024,1865, 6035,1876, 5394,1876, 5610,1660, 5178,1660, 5394,1876, 6035,1876, 6504,2346, 5864,2346, 6015,2497,
1208,-4247, 1441,-4247, 1441,-4080, 1041,-4080, 1208,-4247,
-1128,-2290, -1439,-2601, -1920,-2121, -1920,-2761, -2071,-2610, -2071,-3852, -1711,-3492, -1234,-3492, -1234,-4247, -1138,-4247, -835,-3945, -835,-4247, 519,-4247, 749,-4017, -92,-3176, -92,-3015, -1234,-3015, -1234,-3447, -1450,-3231, -1234,-3015, -92,-3015, -92,-2290, -1128,-2290,
7400,-573, 7400,-422, 7249,-573, 7400,-573,
7400,664, 7400,1644, 6910,1154, 7400,664,
1600,5660, 1600,5760, -2600,5760, -2600,5660, -2000,5660, -2000,5160, -2600,5160, -2600,4960, -2000,4960, -2000,4360, -2600,4360, -2600,4160, -2000,4160, -2000,3660, -2600,3660, -2600,3460, -2000,3460, -2000,2860, -1800,2860, -1800,3460, -1300,3460, -1300,2860, -1100,2860, -1100,3460, -600,3460, -600,2860, -400,2860, -400,3460, 100,3460, 100,2860, 300,2860, 300,3460, 800,3460, 800,2860, 1000,2860, 1000,3460, 1600,3460, 1600,3660, 1000,3660, 1000,4160, 800,4160, 800,3660, 300,3660, 300,4160, 100,4160, 100,3660, -400,3660, -400,4160, -600,4160, -600,3660, -1100,3660, -1100,4160, -1300,4160, -1300,3660, -1800,3660, -1800,4160, 1600,4160, 1600,4360, 1000,4360, 1000,4860, 1600,4860, 1600,4960, 800,4960, 800,4360, 300,4360, 300,4960, 100,4960, 100,4360, -400,4360, -400,4960, -600,4960, -600,4360, -1100,4360, -1100,4960, -1300,4960, -1300,4360, -1800,4360, -1800,4960, 1600,4960, 1600,5060, 1000,5060, 1000,5560, 1600,5560, 1600,5660, 800,5660, 800,5160, 300,5160, 300,5660, 100,5660, 100,5160, -400,5160, -400,5660, -600,5660, -600,5160, -1100,5160, -1100,5660, -1300,5660, -1300,5160, -1800,5160, -1800,5660, 1600,5660,
5840,5760, 2240,5760, 2240,5600, 2840,5600, 2840,5100, 2240,5100, 2240,4900, 2840,4900, 2840,4300, 2240,4300, 2240,4100, 2840,4100, 2840,3600, 2240,3600, 2240,3400, 2840,3400, 2840,2800, 3040,2800, 3040,3400, 3540,3400, 3540,2800, 3740,2800, 3740,3400, 4240,3400, 4240,2800, 4440,2800, 4440,3400, 4940,3400, 4940,2800, 5140,2800, 5140,3400, 5640,3400, 5640,2800, 5840,2800, 5840,3400, 6440,3400, 6440,3600, 5840,3600, 5840,4100, 5640,4100, 5640,3600, 5140,3600, 5140,4100, 4940,4100, 4940,3600, 4440,3600, 4440,4100, 4240,4100, 4240,3600, 3740,3600, 3740,4100, 3540,4100, 3540,3600, 3040,3600, 3040,4100, 6440,4100, 6440,4300, 5840,4300, 5840,4800, 6440,4800, 6440,4900, 5640,4900, 5640,4300, 5140,4300, 5140,4900, 4940,4900, 4940,4300, 4440,4300, 4440,4900, 4240,4900, 4240,4300, 3740,4300, 3740,4900, 3540,4900, 3540,4300, 3040,4300, 3040,4900, 6440,4900, 6440,5000, 5840,5000, 5840,5500, 6440,5500, 6440,5600, 5640,5600, 5640,5100, 5140,5100, 5140,5600, 4940,5600, 4940,5100, 4440,5100, 4440,5600, 4240,5600, 4240,5100, 3740,5100, 3740,5600, 3540,5600, 3540,5100, 3040,5100, 3040,5600, 6440,5600, 6440,5700, 5840,5700, 5840,5760,
6920,5660, 7400,5660, 7400,5760, 6920,5760, 6920,5660,
6920,4960, 7400,4960, 7400,5160, 6920,5160, 6920,4960,
6920,4160, 7400,4160, 7400,4360, 6920,4360, 6920,4160,
6920,3460, 7400,3460, 7400,3660, 6920,3660, 6920,3460

MyLoadTest Function:

bool MyLoadTest(std::ifstream& source, Clipper2Lib::Paths64& subj, Clipper2Lib::Paths64& clip)
{
    string line;
    source.seekg(0, ios_base::beg);
    subj.clear(); clip.clear();

    while (std::getline(source, line))
    {
        if (line.find("SUBJECTS") != string::npos)
        {
            GetPaths(source, subj);
        }
        else if (line.find("CLIPS") != string::npos)
        {
            GetPaths(source, clip);
        }
    }
    return true;
}

the svg result is right:

but the poly tree is wrong:

0 replies

AngusJohnson · 2023-07-08T23:54:05Z

AngusJohnson
Jul 8, 2023
Maintainer

I have reproduced the issue.

Thanks.
I've been tied up with other things but I am still planning to investigate.

0 replies

AngusJohnson · 2023-07-14T12:06:23Z

AngusJohnson
Jul 14, 2023
Maintainer

I'm still testing but I think the following fixes this:

In clipper.engine.cpp (~2163ff)

  void ClipperBase::ProcessHorzJoins()
  {
    for (const HorzJoin& j : horz_join_list_)
    {
    ....
      if (or1 == or2)
      {
        ....
        if (using_polytree_)
        {
          if (Path1InsidePath2(or2->pts, or1->pts))
          {
            SetOwner(or2, or1);
            //if (!or1->splits) or1->splits = new OutRecList();
            //or1->splits->push_back(or2); //(#520)
          }
          else if (Path1InsidePath2(or1->pts, or2->pts))
            SetOwner(or1, or2);
          else
          {
            //if (!or1->splits) or1->splits = new OutRecList(); 
            //or1->splits->push_back(or2); //(#498)
            or2->owner = or1;
          }
          //ADD THESE 2 LINES (and comment out lines as per above)...
          if (!or1->splits) or1->splits = new OutRecList();
          or1->splits->push_back(or2); //(#498, #520, #576)
        }
        else
        ....

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

problem about polytree's build #576

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{editor}}'s edit

{{editor}}'s edit

Uh oh!

Replies: 3 comments

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{title}}

Uh oh!

Select a reply

Uh oh!

problem about polytree's build #576

Uh oh!

Uh oh!

zengguang-xu Jul 6, 2023

Replies: 3 comments

Uh oh!

BigZebra101010 Jul 6, 2023

Uh oh!

AngusJohnson Jul 8, 2023 Maintainer

Uh oh!

AngusJohnson Jul 14, 2023 Maintainer

zengguang-xu
Jul 6, 2023

BigZebra101010
Jul 6, 2023

AngusJohnson
Jul 8, 2023
Maintainer

AngusJohnson
Jul 14, 2023
Maintainer