Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

Clarification on SimplePolygons()

Preet
2013-02-28
2013-04-23
  • Preet
    Preet
    2013-02-28

    Hi,

    I'm trying to clean up some self-intersecting polygons by splitting them up into multiple simple polygons using Clipper. The results I get with SimplifyPolygons() seems to indicate that clipper allows vertices with the same position. See (http://i.imgur.com/pTg8RvW.png)

    Is there any way to force Clipper to return separate polygons as opposed to the above behaviour in the general case? I noticed that I could run SimplifyPolygons twice, once with a positive filltype and once with a negative filltype and this seemed to give me polygons separately, but I don't know if thats reliable in the general case.

     
  • Angus Johnson
    Angus Johnson
    2013-02-28

    Hi Preet.

    Is there any way to force Clipper to return separate polygons as opposed to the above behaviour in the general case?

    Not without modifying the underlying code.
    In the IntersectEdges() method, change the follow from ...

    if ( e1Contributing && e2contributing )
    {
      if ( e1stops || e2stops || 
        (e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
        (e1->polyType != e2->polyType && m_ClipType != ctXor) )
          AddLocalMaxPoly(e1, e2, pt); 
      else
          DoBothEdges( e1, e2, pt );
    }
    

    to ...

    if ( e1Contributing && e2contributing )
    {
        AddLocalMaxPoly(e1, e2, pt); 
        AddLocalMinPoly(e1, e2, pt);
    }
    

    and I think that you'll get separate polygons at these points of intersection (though I haven't tested this).

     
    Last edit: Angus Johnson 2013-02-28
  • Preet
    Preet
    2013-02-28

    Hi Angus,

    This seems to work great! Thank you for the quick reply and example. I have a follow up question. In some cases, the input polygon can't be decomposed any further, but it still has non adjacent duplicate points... see http://i.imgur.com/ZHqTrz2.png for example. Can Clipper detect these cases?

     
  • Angus Johnson
    Angus Johnson
    2013-03-01

    Can Clipper detect these cases?

    Detect for what purpose?

    Would you prefer an inner polygon touching an outer polygon instead? I believe that for everyone who wants that, there is at least another who prefers the current implementation.

     
  • Timo
    Timo
    2013-04-23

    I made a question on
    http://stackoverflow.com/questions/16158931/polygon-triangulation-fails-in-pseudo-duplicate-points regarding polygon simplifying. Anyone who knows about terms Simple Polygon and Triangulation are welcome to give an answer.

    Clipper does seem to be permissive what it comes to unioning (simplifying) pseudo duplicate points, which causes failures in triangulation routines.

    I wonder, why Clipper accepts pseudo duplicates (see the attached image) in Union and Simplify operations?

     
  • Timo
    Timo
    2013-04-23

    I tested the suggestion by changing the lines that were provided in the comment at https://sourceforge.net/p/polyclipping/discussion/1148419/thread/4e614a38/#b81a, but there comes "ProcessHorizontal error" and the output has only one polygon, although there should be two separate ones.

    My Clipper version is Javascript Clipper 5.0.2.1 (with the above changes) and the code that produced error:

    var cpr = new ClipperLib.Clipper();
    var weak = [{"X":100,"Y":200},{"X":150,"Y":150},{"X":100,"Y":100},{"X":200,"Y":100},{"X":150,"Y":150},{"X":200,"Y":200}];
    // console.log(JSON.stringify(weak));
    var simple = cpr.SimplifyPolygon(weak);
    // console.log(JSON.stringify(simple));
    

    The example polygon has one weak duplicate point: {"X":150,"Y":150}.

    The test is at: http://jsbin.com/owivew/1

    Have anyone tested that solution in C# or C++?

     
    Last edit: Timo 2013-04-23
  • Timo
    Timo
    2013-04-23

    Here is a more complex "simple" polygon (after simplifying in Clipper).

    All the points that seem to be together are exactly identical, but there are not duplicate sequential points nor self-intersections on face level, but self-intersections are on vertex level.

    To divide this to truly simple polygons, would require it to be divided into pieces.

    My eyes say that here is four bottom polygons and one (bigger) upper polygon that has a hole, so after truly-simplifying there should be totally five outer polygons and one hole. On a second look it seems that here is only 1 outer polygon with 5 hole polygons.

    The polygon can be seen as SVG at http://jsbin.com/ugimab/3. The points of the polygon are:

    [{"X":270,"Y":520},{"X":130,"Y":490},{"X":210,"Y":250},{"X":60,"Y":170},{"X":130,"Y":490},{"X":20,"Y":410},{"X":60,"Y":300},{"X":60,"Y":20},{"X":780,"Y":40},{"X":680,"Y":180},{"X":460,"Y":130},{"X":210,"Y":250},{"X":320,"Y":100},{"X":220,"Y":80},{"X":210,"Y":250},{"X":520,"Y":250},{"X":680,"Y":180},{"X":770,"Y":480},{"X":540,"Y":470},{"X":520,"Y":250},{"X":380,"Y":280},{"X":430,"Y":390},{"X":540,"Y":470},{"X":270,"Y":520},{"X":330,"Y":350},{"X":210,"Y":250}]
    
    

    How this like truly simplifying could be achieved using Clipper? If not in the current implementation, is it possible to modify the code in some way and how this could be done?

     
    Last edit: Timo 2013-04-24