AngusJohnson / Clipper2

Polygon Clipping and Offsetting - C++, C# and Delphi
Boost Software License 1.0
1.34k stars 248 forks source link

Union returns self-intersecting polygon #851

Closed sethhillbrand closed 4 weeks ago

sethhillbrand commented 1 month ago

Using revision ff378668baae3570e9d8070aa9eb339bdd5a6aba

image

image

I have a bit of a pathological case here. I have a segment in the first image that just slightly crosses over itself (see second image). I believe, based on (https://angusj.com/clipper2/Docs/Units/Clipper.Engine/Classes/Clipper64/Functions/Execute.htm) that the output of Execute should never intersect in this way.

Attached is a sample code that shows the behavior

#include <clipper2/clipper.h>
#include <Utils/clipper.svg.h>
#include <Utils/clipper.svg.utils.h>

using namespace Clipper2Lib;

int main(int argc, char * argv[])
{
  Paths64 subject, solution;
  SvgWriter svg;
  Clipper64 c;
  PolyTree64 pt_solution;

  subject.push_back(MakePath({176308954,86819031,176308954,87200002,176308954,87580966,176308954,88899500,175911975,88899500,175853784,88880593,175817820,88831093,175817820,88769907,175821921,88759375,175836210,88728083,175854627,88600002,175836212,88471922,175783946,88357473,175400001,88741420,175160452,88980966,175211134,89013539,175236789,89021074,175287296,89055610,175307857,89113237,175304524,89141685,175299500,89160435,175299500,89239564,175319978,89315988,175359538,89384508,175415489,89440460,175484007,89480019,175560435,89500499,176308954,89500500,176308954,90000000,165872636,90000000,165872636,88980966,165872636,88600002,174945373,88599997,174963787,88728077,175016051,88842526,175238687,88619891,175258578,88600000,175238687,88580109,175300000,88580109,175300000,88619891,175315224,88656645,175343355,88684776,175380109,88700000,175419891,88700000,175456645,88684776,175484776,88656645,175500000,88619891,175500000,88580109,175484776,88543355,175456645,88515224,175419891,88500000,175380109,88500000,175343355,88515224,175315224,88543355,175300000,88580109,175238687,88580109,175016051,88357473,174963787,88471920,174945373,88599997,165872636,88599997,165872636,88219031,175160453,88219031,175400000,88458578,175639546,88219032,175588858,88186456,175464701,88150000,175335298,88150000,175211139,88186457,175160453,88219031,165872636,88219031,165872636,87580966,175160452,87580966,175211134,87613539,175335298,87649999,175464699,87650000,175588857,87613543,175639545,87580967,175399999,87341421,175160452,87580966,165872636,87580966,165872636,87200002,174945373,87199997,174963787,87328077,175016051,87442526,175238687,87219891,175258578,87200000,175238687,87180109,175300000,87180109,175300000,87219891,175315224,87256645,175343355,87284776,175380109,87300000,175419891,87300000,175456645,87284776,175484776,87256645,175500000,87219891,175500000,87199999,175541421,87199999,175783946,87442524,175836211,87328080,175854627,87200002,175836212,87071922,175783946,86957473,175541421,87199999,175500000,87199999,175500000,87180109,175484776,87143355,175456645,87115224,175419891,87100000,175380109,87100000,175343355,87115224,175315224,87143355,175300000,87180109,175238687,87180109,175016051,86957473,174963787,87071920,174945373,87199997,165872636,87199997,165872636,86819031,175160453,86819031,175400000,87058578,175639546,86819032,175588858,86786456,175464701,86750000,175335298,86750000,175211139,86786457,175160453,86819031,165872636,86819031,165872636,80033416,176308954,80033416}));
  clip.push_back(MakePath({ 160000000, 70000000, 180000000, 70000000, 180000000, 90000000, 160000000, 90000000 } ));
  c.AddSubject( subject );
  c.Execute( ClipType::Union, FillRule::NonZero, solution );
  c.Execute( ClipType::Union, FillRule::NonZero, pt_solution );

  std::cout << pt_solution << std::endl;

  SvgAddSolution( svg, solution, FillRule::NonZero, false );
  SvgSaveToFile( svg, "bad_union.svg" );

}
AngusJohnson commented 4 weeks ago
void Test()
{
  Paths64 subject, solution;
  subject.push_back(MakePath({ 176308954,86819031,176308954,87200002,176308954,87580966,176308954,88899500,175911975,88899500,175853784,88880593,175817820,88831093,175817820,88769907,175821921,88759375,175836210,88728083,175854627,88600002,175836212,88471922,175783946,88357473,175400001,88741420,175160452,88980966,175211134,89013539,175236789,89021074,175287296,89055610,175307857,89113237,175304524,89141685,175299500,89160435,175299500,89239564,175319978,89315988,175359538,89384508,175415489,89440460,175484007,89480019,175560435,89500499,176308954,89500500,176308954,90000000,165872636,90000000,165872636,88980966,165872636,88600002,174945373,88599997,174963787,88728077,175016051,88842526,175238687,88619891,175258578,88600000,175238687,88580109,175300000,88580109,175300000,88619891,175315224,88656645,175343355,88684776,175380109,88700000,175419891,88700000,175456645,88684776,175484776,88656645,175500000,88619891,175500000,88580109,175484776,88543355,175456645,88515224,175419891,88500000,175380109,88500000,175343355,88515224,175315224,88543355,175300000,88580109,175238687,88580109,175016051,88357473,174963787,88471920,174945373,88599997,165872636,88599997,165872636,88219031,175160453,88219031,175400000,88458578,175639546,88219032,175588858,88186456,175464701,88150000,175335298,88150000,175211139,88186457,175160453,88219031,165872636,88219031,165872636,87580966,175160452,87580966,175211134,87613539,175335298,87649999,175464699,87650000,175588857,87613543,175639545,87580967,175399999,87341421,175160452,87580966,165872636,87580966,165872636,87200002,174945373,87199997,174963787,87328077,175016051,87442526,175238687,87219891,175258578,87200000,175238687,87180109,175300000,87180109,175300000,87219891,175315224,87256645,175343355,87284776,175380109,87300000,175419891,87300000,175456645,87284776,175484776,87256645,175500000,87219891,175500000,87199999,175541421,87199999,175783946,87442524,175836211,87328080,175854627,87200002,175836212,87071922,175783946,86957473,175541421,87199999,175500000,87199999,175500000,87180109,175484776,87143355,175456645,87115224,175419891,87100000,175380109,87100000,175343355,87115224,175315224,87143355,175300000,87180109,175238687,87180109,175016051,86957473,174963787,87071920,174945373,87199997,165872636,87199997,165872636,86819031,175160453,86819031,175400000,87058578,175639546,86819032,175588858,86786456,175464701,86750000,175335298,86750000,175211139,86786457,175160453,86819031,165872636,86819031,165872636,80033416,176308954,80033416 }));
  solution = Union(subject, FillRule::NonZero);

  solution.resize(2); // ignore the irrelevant paths
  std::cout << solution << std::endl;
  SvgWriter svg;
  SvgAddSolution(svg, solution, FillRule::NonZero, false);
  std::string filename = "test.svg";
  SvgSaveToFile(svg, filename, 8000, 8000);
  System(filename);
}
solution[0] = 
176308954,86819031, 176308954,87200002, 176308954,87580966, 176308954,88899500, 175911975,88899500, 175853784,88880593, 175817820,88831093, 175817820,88769907, 175821921,88759375, 175836210,88728083, 175854627,88600002, 175836212,88471922, 175783946,88357473, 175400001,88741420, 175160452,88980966, 175211134,89013539, 175236789,89021074, 175287296,89055610, 175307857,89113237, 175304524,89141685, 175299500,89160435, 175299500,89239564, 175319978,89315988, 175359538,89384508, 175415489,89440460, 175484007,89480019, 175560435,89500499, 176308954,89500500, 176308954,90000000, 165872636,90000000, 165872636,88980966, 165872636,88600002, 174945373,88599997, 174963787,88728077, 175016051,88842526, 175238687,88619891, 175258578,88600000, 175238687,88580109, 175016051,88357473, 174963787,88471920, 174945373,88599997, 165872636,88599997, 165872636,88219031, 165872636,87580966, 165872636,87200002, 174945373,87199997, 174963787,87328077, 175016051,87442526, 175238687,87219891, 175258578,87200000, 175238687,87180109, 175016051,86957473, 174963787,87071920, 174945373,87199997, 165872636,87199997, 165872636,86819031, 165872636,80033416, 176308954,80033416
solution[1] = 
175300000,88619891, 175315224,88656645, 175343355,88684776, 175380109,88700000, 175419891,88700000, 175456645,88684776, 175484776,88656645, 175500000,88619891, 175500000,88580109, 175484776,88543355, 175456645,88515224, 175419891,88500000, 175380109,88500000, 175343355,88515224, 175315224,88543355, 175300000,88580109

I'm not getting a self-intersection, however the relevant edges in the solution are collinear.