IsClockwise and Orientation

[dev7355608]

So unless REVERSE_ORIENTATION is defined, Clipper2 paths' orientation is opposite compared to Clipper1. In Clipper1 paths with mathematical counter-clockwise orientation are positive and paths with mathematical clockwise orientation are negative. This is the behavior I want to have, and therefore I define REVERSE_ORIENTATION. To me clockwise/counter-clockwise does not depend on the orientation of the y-axis of the display. So I expect IsClockwise to return false for positively oriented paths, which are mathematically counter-clockwise. Of course on a y-axis down display it looks clockwise to the observer. So it depends on how you look at it. I like the Orientation function of Clipper1 better, because the name makes sense regardless of how you look at it.

[AngusJohnson]

Thanks again dev7355608. See my reply here. ps: I'm not (currently) persuaded to leave IsClockwise() unaffected by REVERSE_ORIENTATION.

[dev7355608]

I wasn't suggesting for IsClockwise to be unaffected by REVERSE_ORIENTATION, but instead rename it to the old Orientation to avoid confusion. Because whether something is clockwise or counter-clockwise depends on how you look at it (mathematically or on the display).

I would also suggest making REVERSE_ORIENTATION the default, because that is the mathematically correct orientation, that other libraries use as well.

Shouldn't positively oriented paths have a positive area and negatively oriented paths a negative area? This is no longer true after the changes to Area without REVERSE_ORIENTATION.

[AngusJohnson]

I don't think there's a simple or "right" answer to this and I'm certainly not committed to the current implementation.

Nevertheless, orientation is important when using either the Positive or Negative filling rules and IMHO these need to be consistent with IsClockwise(). And my presumption is that most Clipper2 users will understand these things relative to how polygons are being displayed. So if I implement REVERSE_ORIENTATION properly, I'm hoping that both IsClockwise() and the filling rules will be easier to document (and more easily understood by users).

I'm certainly open to making REVERSE_ORIENTATION the default as that's the orientation I use (and the orientation used when developing Clipper1 and Clipper2). But I haven't been able to find out just how prevalent inverted Y-axis displays are. ISTM that Windows' developers are mostly using inverted Y-axis displays, whereas Linux developers are not.

[dev7355608]

I've never seen that clockwise orientation being associated with positive orientation in a mathematical setting or in another software. I think how you documented Orientation in Clipper1 was pretty clear. Another naming suggestion: IsPositive / IsNegative. Those would make it even clearer than Orientation.

[AngusJohnson]

I've never seen that clockwise orientation being associated with positive orientation in a mathematical setting or in another software.

OK. I've always come at this from the perspective of graphics display.

Another naming suggestion: IsPositive / IsNegative. Those would make it even clearer than Orientation.

Yes, that's an interesting idea.

[AngusJohnson]

I think I've finally got this working properly, but I'll leave this thread open for a little while just in case I haven't. 🤞🙏.

[dev7355608]

If REVERSE_ORIENTATION is disabled, positive paths are IsPositive, but have a negative Area; it should be positive. If REVERSE_ORIENTATION is enabled, positive paths have a positive Area, but are not IsPositive.

IsPositive should be equivalent to Area > 0.

template <typename T>
inline double Area(const Path<T>& path)
{
    // ...
#ifdef REVERSE_ORIENTATION
    return a * 0.5;
#else
        return a * -0.5;
#endif
}

template <typename T>
inline bool IsPositive(const Path<T>& poly)
{
    return Area<T>(poly) > 0;
}

I also just noticed that the orientation of Ellipse is negative regardless of REVERSE_ORIENTATION.

[AngusJohnson]

positive paths [should] have a positive Area.

Thanks, you're right 😡😭. And I only got it half right in Delphi 😵. And I'm just about to post the fix.

---

I also just noticed that the orientation of Ellipse is negative regardless of REVERSE_ORIENTATION.

Not according to my tests.

  //having just added this to clipper.core.h
  template <typename T>
  std::ostream& operator << (std::ostream& outstream, const Path<T>& path)
  {
    if (!path.empty())
    {
        auto pt = path.cbegin(), last = path.cend() - 1;
        while (pt != last)
            outstream << *pt++ << ", ";
        outstream << *last << std::endl;
    }
    return outstream;
  }

and running this ...

  Path64 subj = Ellipse(Point64(100, 100), 100, 100, 5);
  std::cout << IsPositive(subj) << std::endl;
  std::cout << subj;

I get this when REVERSE_ORIENTATION is defined:

0
200,100, 131,5, 19,41, 19,159, 131,195

and this when it isn't:

1
200,100, 131,195, 19,159, 19,41, 131,5

[dev7355608]

If REVERSE_ORIENTATION is enabled now, it's working properly. But otherwise, if REVERSE_ORIENTATION is disabled, IsPositive and Area do not return opposite results: IsPositive doesn't match the fill rule behavior. This is missing in Area:

#ifdef REVERSE_ORIENTATION
    return a * 0.5;
#else
        return a * -0.5;
#endif

If I union an ellipse with the positive fill rule, I always get an empty result.

[AngusJohnson]

I'll need to sleep in this (again) otherwise I'll just go around in circles (😜).

Edit: Just in case some are wondering why I haven't nailed this yet, this really isn't simple because there are lots of moving parts. Firstly, there's the orientation of the clipping input. Then there's the orientation of the clipping solution that needs to match the orientation of the input. In other words, if the input paths are oriented in a positive direction (for outer paths) then the solution should match this orientation (and vice versa). Yes, so far, that's fairly simple. But things get really tricky when offsetting. First the offsetting direction (whether delta offsets away left or away right depends not only on delta's sign, but also on the winding direction - positive or negative). Then the path output direction also needs to match the path input direction, and finally there's clipping internal to offsetting that obeys another set of rules and they all depend on orientation. So no, this really isn't simple.

[philstopford]

Just to add to this (also sent by e-mail), the current code appears to misbehave with something like this : the left/right and top/bottom results are not respecting the input orientation, it seems

    public static void test()
    {
        Path64 testPath = ClipperFunc.MakePath(new[]
        {
            -50000, -550000,
            -50000, -150000,
            650000, -150000
        });

        Path64 b = ClipperFunc.MakePath(new[]
        {
            300000,-800000,
            300000,0,
            500000,0,
            500000,-800000
        });

        Clipper c = new() {PreserveCollinear = true};
        c.AddOpenSubject(testPath);
        c.AddClip(b);
        Paths64 unused = new();
        Paths64 topChords = new();
        c.Execute(ClipType.Intersection, FillRule.EvenOdd, unused, topChords);

        Path64 testPath2 = ClipperFunc.MakePath(new[]
        {
            650000,-150000,
            650000,-550000,
            -50000,-550000
        });

        c.Clear();
        c.AddOpenSubject(testPath2);
        c.AddClip(b);
        Paths64 bottomChords = new();
        c.Execute(ClipType.Intersection, FillRule.EvenOdd, unused, bottomChords);

        Path64 testPath3 = ClipperFunc.MakePath(new[]
        {
            300000,-800000,
            300000,0
        });

        Path64 a = ClipperFunc.MakePath(new[]
        {
            -50000, -550000,
            -50000, -150000,
            650000, -150000,
            650000, -550000
        });

        c.Clear();
        c.AddOpenSubject(testPath3);
        c.AddClip(a);
        Paths64 leftChords = new();
        c.Execute(ClipType.Intersection, FillRule.EvenOdd, unused, leftChords);

        Path64 testPath4 = ClipperFunc.MakePath(new[]
        {
            300000,0,
            500000,0,
            500000,-800000,
            300000,-800000
        });

        c.Clear();
        c.AddOpenSubject(testPath4);
        c.AddClip(a);
        Paths64 rightChords = new();
        c.Execute(ClipType.Intersection, FillRule.EvenOdd, unused, rightChords);

    }

The 'good' results I got before would look like this :

leftChords = {List<List<Point64>>} Count = 1
 [0] = {List<Point64>} Count = 2
  [0] = {Point64} 300000,-550000,0
  [1] = {Point64} 300000,-150000,0

rightChords = {List<List<Point64>>} Count = 1
 [0] = {List<Point64>} Count = 2
  [0] = {Point64} 500000,-150000,0
  [1] = {Point64} 500000,-550000,0

bottomChords = {List<List<Point64>>} Count = 1
 [0] = {List<Point64>} Count = 2
  [0] = {Point64} 500000,-550000,0
  [1] = {Point64} 300000,-550000,0

topChords = {List<List<Point64>>} Count = 1
 [0] = {List<Point64>} Count = 2
  [0] = {Point64} 300000,-150000,0
  [1] = {Point64} 500000,-150000,0 

Now, I get :

leftChords = {List<List<Point64>>} Count = 1
 [0] = {List<Point64>} Count = 2
  [0] = {Point64} 300000,-150000,0 
  [1] = {Point64} 300000,-550000,0 

rightChords = {List<List<Point64>>} Count = 1
 [0] = {List<Point64>} Count = 2
  [0] = {Point64} 500000,-150000,0 
  [1] = {Point64} 500000,-550000,0 

bottomChords = {List<List<Point64>>} Count = 1
 [0] = {List<Point64>} Count = 2
  [0] = {Point64} 500000,-550000,0 
  [1] = {Point64} 300000,-550000,0 

topChords = {List<List<Point64>>} Count = 1
 [0] = {List<Point64>} Count = 2
  [0] = {Point64} 500000,-150000,0 
  [1] = {Point64} 300000,-150000,0 

[AngusJohnson]

OK, I think the latest revision is about as good as I'm going to get things on orientation.

Here's a summary of the situation:

1. The Clipper2 library contains a compiler directive REVERSE_ORIENTATION that will change how the library interprets the winding direction for input polygons. When REVERSE_ORIENTATION is undefined and polygons are viewed on displays using Cartesian coordinates (ie Y-axis positive upwards), polygons with positive areas will have their vertices progressing in a roughly clockwise direction. This "positive" clockwise orientation is also true when REVERSE_ORIENTATION is combined with inverted Y-axis displays.
2. Orientation is only important when using the Positive and Negative filling rules. (EvenOdd and NonZero polygon filling will not be affected by orientation changes.)
3. When outer polygons have positive areas then inner "hole" paths will have negative areas. In the Clipper2 library, outer polygons will almost always have positive areas. The only exception to this is when the Negative filling rule has been used in the clipping operation.
4. Open paths have undefined orientations. Furthermore, open paths may appear reversed in clipping solutions. Vertex order in open path solutions is generally decided by the vertex with the lowest Y value being the first vertex in a given path.

[dev7355608]

In closed path solutions, generally outer polygons will have positive areas and inner "hole" paths will have negative areas. The only exception is when the Negative filling rule has been selected, in which case the orientation of solution polygons will be reversed.

This exception seems weird to me. I'd except for the solution be to a zero-one filling always. Why reverse it in the case of Negative?

I also noticed that paths with negative orientation are offset as if they were positive. I'd expect the offset direction to depend on the orientation of the path.

[philstopford]

The orientation related changes seem to have completely broken my use cases for open path clipping. For arbitrary geometry, it's now going to be impossible to locate left/right/top/bottom chords if the orientation does not match the original - I deliberately re-orient and re-order the points so that the lowest Y, lowest X point is first and rely on the output coming back with matching order. It looks like this cannot be done any more and I don't really see a solution. I relied on the order to be able to generate appropriate normals based on the geometry, which could be non-trivial and non-orthogonal. I may end up abusing the Z callback to stuff the series number in to the Z position, but that seems like a really ugly hack and I already use the Z for tracking in other situations (e.g. source polygon index), so this is going to be even more awkward.

I'm also seeing a bunch of other failures that I was hoping were related to these bugs, and I will have to try and figure out what's going wrong.

At least for me, prior to these orientation changes, everything was working beautifully and I may have to simply sit on an older version of the code at this point.

[AngusJohnson]

This exception seems weird to me. I'd except for the solution be to a zero-one filling always. Why reverse it in the case of Negative?

The library could render solutions such that outer paths were always positive (with inner paths negative). However, Negative filling by definition indicates that paths (subject and clip) will have negative oriented outer paths. If clipping solutions then returned positive oriented outer paths (the reverse of these input paths), not only would the display renderer need to apply separate filling rules for the solution, but I believe this orientation would be more confusing for users. (Fortunately the Negative filling is rarely used in practise.)

[AngusJohnson]

The orientation related changes seem to have completely broken my use cases for open path clipping.

Phil, I don't believe that open paths were ever predictably ordered (ie in either Clipper1 or earlier versions of Clipper2), at least not such that they consistently followed their input directions.

I deliberately re-orient and re-order the points so that the lowest Y, lowest X point is first and rely on the output coming back with matching order.

As far as I can tell, the only change is that open paths will now be lowest Y (ie closest to most negative) first, possibly the reverse of what you were getting before. However, the Clipper object now has a ReverseOrientation property (that simply reverses solutions) which should address that.

Anyhow, I am still open to persuassion to make further changes here if I can be convinced they will make things not only better but realistically achieveable.

[philstopford]

At least in my experience, they have been. I see left-right ordering differences in the test case I supplied earlier, and I could rely on the open path clipping for normal calculations for geometry coming from the open path clipping : I used this for overlap computation in one of my tools. I use a similar technique also for visibility computations that resize geometry along its normals based on proximity to other shapes. In all cases, the order is important and when that's not available, the handling breaks down and I don't see any solution from my side at the moment. It may come to me as I walk the dogs, but I'm concerned at the moment.

Current code does this instead :

I can't tell which way the emission should run because the order can't be relied on (am I ascending or descending)? It's not enough to compare start and end points because the geometry is arbitrary. The old approach really seemed to give predictable results every time. I never had any complaints.

[dev7355608]

This exception seems weird to me. I'd except for the solution be to a zero-one filling always. Why reverse it in the case of Negative?

The library could render solutions such that outer paths were always positive (with inner paths negative). However, Negative filling by definition indicates that paths (subject and clip) will have negative oriented outer paths. If clipping solutions then returned positive oriented outer paths (the reverse of these input paths), not only would the display renderer need to apply separate filling rules for the solution, but I believe this orientation would be more confusing for users. (Fortunately the Negative filling is rarely used in practise.)

But wouldn't the user expect for filled regions to have a positive area and holes a negative area regardless of the fill rule? The fill rule used might not the one that is used for drawing necessarily. I'd expect the Negative fill rule to return the exact same results as reversing the paths and then using Positive fill rule.

[philstopford]

My keyholer code is also broken with this change; it's proving tricky to understand what's misfiring and I'll need some time to put a comparison together for the two modes. I relied heavily on IsClockwise and never used reversed orientation, in order to locate holes vs outers. That approach currently seems to be broken; IsPositive seems to return the inverse of IsClockwise now, which leads to holes being tagged as outers, and all kinds of chaos ensues.

The aim is to find all the holes, emit rays from them in a way that they intersect outers, and to find minimal edge lengths. Orientation changes, etc. really mess with this processing. The emission requires on computing the normal; if the open path orientation is undefined, I cannot make a good normal computation for the emission; as you can see above, there's no way to decide which way to emit.....

[philstopford]

Digging in further, in one of my tests I have an input as a mix of an outer and a hole; the orientation here was to match the library behavior I was seeing at the time (mix of Clipper1 and Clipper2)

Paths64 source = new() {
 ClipperFunc.MakePath(new [] {
-200000,-200000, 
200000,-200000, 
200000,200000, 
-200000,200000, 
-200000,-200000
}), 
 ClipperFunc.MakePath(new [] {
-100000,-100000, 
-100000,100000, 
100000,100000, 
100000,-100000, 
-100000,-100000
})
); 

I feed this through an offset to remove any slivers and gaps. There are some constants below, but in the library code, these values are changeable based on need :

        Paths cGeometry = new();

        ClipperOffset co = new();
        co.AddPaths(source, joinType, EndType.Polygon);
        cGeometry = co.Execute(customSizing);
        co.Clear();
        co.AddPaths(cGeometry.ToList(), joinType, EndType.Polygon);
        cGeometry.Clear();
        cGeometry = co.Execute(-customSizing); // Size back to original dimensions

In the old code, this yielded :

cGeometry = {List<List<Point64>>} Count = 2
 [0] = {List<Point64>} Count = 4
  [0] = {Point64} 200000,-200000,0 
  [1] = {Point64} -200000,-200000,0 
  [2] = {Point64} -200000,200000,0 
  [3] = {Point64} 200000,200000,0 
 [1] = {List<Point64>} Count = 4
  [0] = {Point64} 100000,-100000,0 
  [1] = {Point64} 100000,100000,0 
  [2] = {Point64} -100000,100000,0 
  [3] = {Point64} -100000,-100000,0 

In the new code, though, I get :

cGeometry = {List<List<Point64>>} Count = 2
 [0] = {List<Point64>} Count = 5
  [0] = {Point64} -200000,-200000,0 
  [1] = {Point64} 200000,-200000,0 
  [2] = {Point64} 200000,200000,0 
  [3] = {Point64} -200000,200000,0 
  [4] = {Point64} -200000,-200000,0 
 [1] = {List<Point64>} Count = 5
  [0] = {Point64} -100000,-100000,0 
  [1] = {Point64} -100000,100000,0 
  [2] = {Point64} 100000,100000,0 
  [3] = {Point64} 100000,-100000,0 
  [4] = {Point64} -100000,-100000,0 

Even with REVERSE_ORIENTATION specified, I get a different result than I was looking for.:

cGeometry = {List<List<Point64>>} Count = 2
 [0] = {List<Point64>} Count = 4
  [0] = {Point64} 200000,-200000,0 
  [1] = {Point64} 200000,200000,0 
  [2] = {Point64} -200000,200000,0 
  [3] = {Point64} -200000,-200000,0 
 [1] = {List<Point64>} Count = 4
  [0] = {Point64} -100000,100000,0 
  [1] = {Point64} 100000,100000,0 
  [2] = {Point64} 100000,-100000,0 
  [3] = {Point64} -100000,-100000,0 

Is there a way to get back the old behavior in the new code?

This may also just be a consequence of dragging my existing library code through the successive iterations of Clipper2 from the Clipper1 starting point, but it would be annoying to have to restart the migration work. As such, knowing whether the above is expected and correct behavior would be helpful, or if this is a bug

[Fribur]

A maybe controversial suggestion to simplify things(?): stay consistent throughout the entire library that Y axis goes from min (bottom) to top (up) = Cartesian? So ignore what displays are doing, as per OP suggestion, and stick to pure Cartesian mathematics? (Which probably also means that scanline movement is inversed?) IMHO consideration of the arbitrary & proprietary things displays do just complicates thing unnecessarily and the user of the library should take care of that (e.g. in Unity Y-Axis goes up on WordSpace, but in ScreenSpace it goes down…confused yet?)

[AngusJohnson]

But wouldn't the user expect for filled regions to have a positive area and holes a negative area regardless of the fill rule?

The user should expect what the documentations states 😜. However, I'm committed to making library (and hence the documentation) as simple as possible, so you have persuaded me to make this change such that clipping will always produce positive orientations for outer paths 👍. And for those (very few) who will use negative orientation, and are wanting to preserve this orientation in the clipping output, they can simply set Clipper's ReverseSolutions* property.

*The ReverseSolutions property is currently ReverseOrientation which I can see is very confusing so it's about to be changed to ReverseSolutions.

A maybe controversial suggestion to simplify things(?): stay consistent throughout the entire library that Y axis goes from min (bottom) to top (up) = Cartesian?

The library does default to Positive == counter-clockwise in Cartesian coordinates (edited: see Fribur's post below). However I do think it's helpful to have a compiler switch that's mostly set and forget (ie REVERSE_ORIENTATION), so Positive can be either clockwise or counter-clockwise (and consistent with whatever graphics display library that's being used).

And I'll say again, this is only relevant to those very few library users who will need/use either Positive or Negative filling rules. Most users will only require NonZero and EvenOdd filling (and the majority of graphics libraries will only support these two fill rules).

[Fribur]

The library does default to Positive == clockwise in Cartesian coordinates.<<

?

In Cartesian positive areas = Counter Clockwise as also stated by OP and

“Given: A planar simple polygon with a positively oriented (counter clock wise) sequence of points […] in a Cartesian coordinate system. https://en.m.wikipedia.org/wiki/Shoelace_formula

[AngusJohnson]

In Cartesian positive areas = Counter Clockwise as also stated by OP and

OK, thanks for reminding me. I'll check this again.

[AngusJohnson]

Even with REVERSE_ORIENTATION specified, I get a different result than I was looking for.:

Phil, did you try the Clipper object's ReverseOrientation property (which I'm about to rename to ReverseSolution)? And I'm afraid I'm suffering from TLDR with your posts. You'll need to simplify them otherwise I'm not going to be able to respond constructively.

[AngusJohnson]

I'm going to close this issue now, but not because I consider Orientation finally resolved, but because further discussion should continue in Discussions and likely in more than one thread.

[AngusJohnson]

@philstopford re this post I've just tested your code against the latest revision and it seems we're back to "good results" 😁.

[philstopford]

Thanks, as ever, for the hard work on this. I will take this as a sign to start running tests tomorrow.