Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

#96 Unexpected empty intersection

*
open
nobody
None
1
2014-05-26
2014-05-12
Anonymous
No

Hello Angus,

the following intersection should be positive but it returns an empty set instead. If I move slightly the first Y coordinate of the subject path (+1) it works. But if I move the first X coordinate nothing changes.

SUBJECT OPEN PATH:
[44735000,31936670],[55270000,31936670],[55270000,25270000],[74730000,25270000],[74730000,44730000],[68063296,44730000],[68063296,55270000],[74730000,55270000],[74730000,74730000],[55270000,74730000],[55270000,68063296],[44730000,68063296],[44730000,74730000],[25270000,74730000],[25270000,55270000],[31936670,55270000],[31936670,44730000],[25270000,44730000],[25270000,25270000],[44730000,25270000],[44730000,31936670]

CLIP CLOSED PATH:
[75200000,45200000],[54800000,45200000],[54800000,24800000],[75200000,24800000]

Thank you as usual.

Discussion

  • Sorry Angus, but how are they related? The subject path of this report has no coincident endpoints.

     

  • Anonymous
    2014-05-13

    Interesting. I'll try with the same Clipper version you used. I used one taken from trunk some time ago.

     

  • Anonymous
    2014-05-20

    I was going to try with current trunk, but these errors prevent me from compiling it:

    src/clipper.cpp:1068:49: error: member reference type 'ClipperLib::TEdge ' is a pointer; maybe you meant to use '->'?
    if (E->Curr == E->Next->Curr && (Closed || E.Next != eStart))
    ~^
    ->
    src/clipper.cpp:1156:8: error: member reference type 'ClipperLib::TEdge
    ' is a pointer; maybe you meant to use '->'?
    if (E.Prev.Bot == E.Prev.Top) E = E.Next;
    ~^
    ->
    src/clipper.cpp:1156:13: error: member reference type 'ClipperLib::TEdge ' is a pointer; maybe you meant to use '->'?
    if (E.Prev.Bot == E.Prev.Top) E = E.Next;
    ->
    src/clipper.cpp:1156:22: error: member reference type 'ClipperLib::TEdge
    ' is a pointer; maybe you meant to use '->'?
    if (E.Prev.Bot == E.Prev.Top) E = E.Next;
    ~^
    ->
    src/clipper.cpp:1156:27: error: member reference type 'ClipperLib::TEdge ' is a pointer; maybe you meant to use '->'?
    if (E.Prev.Bot == E.Prev.Top) E = E.Next;
    ->
    src/clipper.cpp:1156:38: error: member reference type 'ClipperLib::TEdge
    ' is a pointer; maybe you meant to use '->'?
    if (E.Prev.Bot == E.Prev.Top) E = E.Next;
    ~^
    ->
    6 errors generated.

     
  • Angus Johnson
    Angus Johnson
    2014-05-21

    I was going to try with current trunk, but these errors prevent me from compiling it:

    Thanks. Not sure how that happened. Will fix and upload again shortly.

     

  • Anonymous
    2014-05-23

    I just tested this with current trunk and it looks better indeed. Thanks for fixing it.

    However, the result contains two open paths instead of a single continuous one. The two paths actually share a common point. But I think it shouldn't split the original open paths.

     
  • Angus Johnson
    Angus Johnson
    2014-05-24

    However, the result contains two open paths instead of a single continuous one. The two paths actually share a common point. But I think it shouldn't split the original open paths.


    Yes, now fixed in revision 467.

     

  • Anonymous
    2014-05-25

    Angus, I just tried with the code from r467 but by test suite is now failing on another test case:

    ctIntersection between:
    SUBJECT (open path):
    LINESTRING((50 150,300 150))

    CLIP:
    POLYGON((200 100,200 200,100 200,100 100))
    POLYGON((160 140,140 140,140 160,160 160))

    This is the backtrace:

    #0  0x00007fff8902ed46 in __kill ()
    #1  0x00007fff85ccef83 in abort ()
    #2  0x00007fff846a09eb in abort_message ()
    #3  0x00007fff8469e39a in default_terminate ()
    #4  0x00007fff90058887 in _objc_terminate ()
    #5  0x00007fff8469e3c9 in safe_handler_caller ()
    #6  0x00007fff8469e424 in std::terminate ()
    #7  0x00007fff8469f58b in __cxa_throw ()
    #8  0x00000001010c2c35 in ClipperLib::ClipperBase::AddPath (this=0x7fff5fbff7b0, pg=@0x6, PolyTyp=ClipperLib::ptSubject, Closed=<value temporarily unavailable, due to optimizations>) at src/clipper.cpp:1032
    #9  0x00000001010c32b6 in ClipperLib::ClipperBase::AddPaths (this=0x7fff5fbff7b0, ppg=@0x7fff5fbff810, PolyTyp=ClipperLib::ptSubject, Closed=<value temporarily unavailable, due to optimizations>) at src/clipper.cpp:1209
    #10 0x0000000101120bf5 in Slic3r::_clipper_do (clipType=ClipperLib::ctIntersection, subject=<value temporarily unavailable, due to optimizations>, clip=<value temporarily unavailable, due to optimizations>, retval=@0x7fff5fbff888, fillType=ClipperLib::pftNonZero, safety_offset_=<value temporarily unavailable, due to optimizations>) at src/ClipperUtils.cpp:310
    #11 0x000000010111fe2f in Slic3r::_clipper (clipType=<value temporarily unavailable, due to optimizations>, subject=<value temporarily unavailable, due to optimizations>, clip=<value temporarily unavailable, due to optimizations>, retval=@0x7fff5fbff990, safety_offset_=<value temporarily unavailable, due to optimizations>) at src/ClipperUtils.cpp:344
    #12 0x0000000101083c6a in XS_Slic3r__Geometry__Clipper_intersection_pl (my_perl=0x7fff5fbff7b0, cv=<value temporarily unavailable, due to optimizations>) at Clipper.xsp":140
    #13 0x0000000100070abd in Perl_pp_entersub ()
    #14 0x0000000100068ee1 in Perl_runops_standard ()
    #15 0x0000000100019f26 in perl_run ()
    #16 0x0000000100000d54 in main ()
    
     
    Last edit: Angus Johnson 2014-05-25

  • Anonymous
    2014-05-25

    Oh, sorry. I keep forgetting to re-enable the use_lines macro every time I update clipper.hpp. I now put a preprocessor directive in my code that errors out whenever I forget that.

    I just tested, and I still get two open paths instead of a single one as result of the OP test case. I'm using r467.

    Thank you for your patience...

     

  • Anonymous
    2014-05-26

    Thank you Angus. r468 satisfies my test suite.

     
  • I'm sorry... r468 actually satisfies the unit test about that particular issue, but I'm seeing many regressions. For example this intersection:

    POLYGON((100000000 100000000,200000000 100000000,200000000 200000000,100000000 200000000),(140000000 140000000,140000000 160000000,160000000 160000000,160000000 140000000)) (a square with a hole)
    LINESTRING((123431458 123431458,120000000 140000000,120000000 160000000,123431458 176568542,140000000 180000000,160000000 180000000,176568542 176568542,180000000 160000000,180000000 140000000,176568542 123431458,160000000 120000000,140000000 120000000,123431458 123431458)) (an open path with coinciding endpoints)

    The open path should be returned unmodified; however the first two vertices are removed.

     
  • Angus Johnson
    Angus Johnson
    2014-05-26

    Try revision 469 :).

    ps: Unfortunately I don't have too many open path test cases so if you're happy to share yours I'd be grateful if you emailed them to me.

    pps: No more fixes allowed! (Just kidding.)

     


Anonymous


Cancel   Add attachments