Preserving collinear closed polygon spikes

[giedrius-stanevicius]

I would like to be able to preserve collinear spikes present on original polygons when they are simplified or clipped with other polygons. However, documentation explicitly states that such spikes would be removed and that's how it actually works (at least with Clipper1). I wonder if such behavior is inherent to the clipping algorithm or is it just an arbitrary design choice? If it is the later, then how complicated it could be to adjust the library for this? Would it be worth investigating?

[AngusJohnson]

Hi Giedrius. Yes this is an arbitrary design choice. It's my presumption that removing spikes would almost always be the preferred option. And while it wouldn't be very hard to allow these spikes** with an additional boolean property in Clipper64, these additional options just increases the complexity of the library (and the documentation).

**It would just be a minor tweak to CleanCollinear() in Clipper.Engine.

[giedrius-stanevicius]

Hi Angus. Thanks for fast reply. I am now trying to make modifications to the library for my own use. I want the PreserveCollinear option to work for all cases, even for the spikes. Here are the changes I made so far (commented out the conditions that seemed relevant):

clipper.engine.cpp:1397:

     //NB if preserveCollinear == true, then only remove 180 deg. spikes
     if ((CrossProduct(op2->prev->pt, op2->pt, op2->next->pt) == 0) &&
        (op2->pt == op2->prev->pt ||
          op2->pt == op2->next->pt || !PreserveCollinear /*||
          DotProduct(op2->prev->pt, op2->pt, op2->next->pt) < 0*/))

clipper.engine.cpp:2192:

      //always trim 180 deg. spikes (in closed paths)
      //but otherwise break if preserveCollinear = true
      if (preserveCollinear /*&&
        ((pt.x < horzEdge.top.x) != (horzEdge.bot.x < horzEdge.top.x))*/)
        break;

clipper.engine.cpp:2387:

      /*if (PreserveCollinear && !horzIsOpen && HorzIsSpike(horz))
        TrimHorz(horz, true);*/

The problem is that while it preserves some of the spikes, there are still cases where it removes them. For example, I have such polygon with 2 spikes: [(0, 10), (50, 10), (60, 0), (70, 10), (120, 10)]. For starters, I want to simplify it before inflating. I use such code for this:

cl::PathsD simplifiedPolies;
cl::ClipperD clipper;
clipper.PreserveCollinear = true;
clipper.AddSubject(inPolies); 
clipper.Execute(cl::ClipType::Union, cl::FillRule::EvenOdd, simplifiedPolies);

As a result I get such polygon: [(70, 10), (120, 10), (50, 10), (60, 0)]. So, one spike is being preserved, but the first one is removed. Is there a way to fix this?

[giedrius-stanevicius]

It's my presumption that removing spikes would almost always be the preferred option.

I think this presumption might be true for applications that are close to the real world - in such cases spikes with zero areas practically mean emptiness and it is ok and even preferable to be removed. However this is not the case with graphics design applications. In graphics design the exact path shape is very important and removing spikes could significantly change visual representation of the content. For example, a path could be used for stroking and a stroked path with spikes or without them would look very differently. So, I think there are quite a lot of cases where preserving spikes would be very preferable.

That's my 2 cents just in case you would like to reconsider this design choice in the future ;)

[AngusJohnson]

Looking in DoHorizontal , amend the following ...

      if (PreserveCollinear && !horzIsOpen && HorzIsSpike(horz))
        TrimHorz(horz, true);

[giedrius-stanevicius]

Unfortunately this did not change the result with the particular example. What did make correct result, though, was commenting out the following code:
clipper.engine.cpp:1721

      /*else if (IsFront(e1) || (e1.outrec == e2.outrec))
      {
        //this 'else if' condition isn't strictly needed but
        //it's sensible to split polygons that ony touch at
        //a common vertex (not at common edges).

        resultOp = AddLocalMaxPoly(e1, e2, pt);
#ifdef USINGZ
        OutPt* op2 = AddLocalMinPoly(e1, e2, pt);
        if (zCallback_ && resultOp) SetZ(e1, e2, resultOp->pt);
        if (zCallback_) SetZ(e1, e2, op2->pt);
#else
        AddLocalMinPoly(e1, e2, pt);
#endif
      }*/

Could this be the main cause of the issue, or did it work only by accident?

[AngusJohnson]

or did it work only by accident?

Yes, I believe you were just lucky in this instance. I've now had a fairly good look at this and there's not easy way to reliably allow spikes without significantly reworking the clipping code. Sorry to disappoint.

[giedrius-stanevicius]

Oh well.. Thanks anyway for the look into this, really appreciated. Clipper is still probably the best polygons clipping lib I know ;)