Area formula

[Terence_13]

Dear Angus,

The area formula used in clipper continues to confuse me as it is different than all my other polygon manipulation libraries. In cartesian coordinates (0,0 is bottom left) positive areas indicate CCW, and negative CW orientation. The area formula in clipper does that, but only by reversing the final result because it is using ((1/2 (Xi + Xi+1)(Yi-Yi+1), which is neither the Trapezoid formula (1/2 (Yi + Yi+1)(Xi-Xi+1) nor the Triangle/Shoelace Formula (1/2 (Xi * Yi+1) - (Xi+1 * Yi). To that end, what do you think about this (also a bit shorter):

public static double AreaNew(PathD path)
        {
            double a = 0.0;
            int cnt = path.Count, j = cnt - 1;
            if (cnt < 3) return 0.0;
            for (int i = 0; i < cnt; j = i++) 
                a += (path[j].y + path[i].y) * (path[j].x - path[i].x);
            return a * 0.5;
        }       

(btw: I usually multiply by 0.5 in each iteration of the loop to minimize risk of overflow. Certainly more expensive. Are you not worried about this?)

The other piece that confuses me: why does clipper interpret a positive area as CW and not CCW? Is it because the Vatti algorithm considers the top left as (0,0)? I would understand that, however maybe you could indicate this in the code as a comment to minimize confusion such as

//Result in a coordinate system where 0,0 is top/left (is opposite in cartesian coordinate system having 0,0 at bottom left.
  public static bool IsClockwise(Path64 poly)
    {
      return Area(poly) >= 0;
    }

[Angus Johnson]

Hi again Terence.

The area formula used in clipper continues to confuse me

LOL, it confuses me too! 😕 All my development has been done using inverted Y-axis displays (0,0 at top left). This of course reverses winding orientation (clockwise vs counterclockwise ) and I recently I tried to fix this with a pre-compiler switch (that reverses orientation). Howver, in doing this I broke things and, rather than persisting, I reversed the changes. Thanks to your feedback here I'll make a more concerted effort to get this right.

As to my strange Area algorithm, I don't remember where I got the formula and accept it's inconsistent with the formula you mentioned. (And I presumed I was having to negate the final value because I was using an inverted Y-axis, so as you can see I'm still working through my confusion 😱.) Thanks for your AreaNew code which I'm happy to adopt. However, I'm not sure if the line if (cnt < 3) return 0.0; is needed. It looks safe to remove (though I'm yet to test this).

I usually multiply by 0.5 in each iteration of the loop to minimize risk of overflow. Certainly more expensive. Are you not worried about this?

Absolutely! However I would imagine that typecasting the first multipication value to double would circumvent overflow without resorting to the expense of many additional multiplications.

The other piece that confuses me: why does clipper interpret a positive area as CW and not CCW?

As I said above, it's because all my development has been done using inverted Y-axis displays. I'll try again to fix this.

ps: While it makes sense to finish this discussion here, I'd prefer discussion on Clipper2 to be conducted in GitHub where Clipper2 is being hosted.

[Terence_13]

However, I'm not sure if the line if (cnt < 3) return 0.0; is needed. It looks safe to remove (though I'm yet to test this).

Indeed, in my framework the area function looks like this:

public static double AreaNew(PathD path)
{
    double a = default;
    for (int i = 0, cnt = path.Count; i < cnt; j = i++) 
        a += (path[j].y + path[i].y) * (path[j].x - path[i].x) * 0.5;
    return a;
}

While the double version does not need any type casting, the integer version does need it and looks like this:

public static double AreaNew(Path64 path)
{
    double a = default;
    for (int i = 0, cnt = path.Count; i < cnt; j = i++) 
        a += (double)(path[j].y + path[i].y) * (double)(path[j].x - path[i].x) * 0.5;
    return a;
}

the first multipication value to double would circumvent overflow

Not sure I fully understand: the double version (PathD) does not need any typecasting as everything is double already. While double does permit ridiculously large numbers, I am still paranoid of having overflow as my polygons having thousands of coordinates store 36degree Latitude as as 36 000 000 000.

ps: While it makes sense to finish this discussion here, I'd prefer discussion on Clipper2 to be conducted in GitHub where Clipper2 is being hosted.

Got you, prefer Github anyhow. Many Thanks for all your effort you put into this library.

[Angus Johnson]

Not sure I fully understand: the double version (PathD) does not need any typecasting as everything is double already.

Yeah, sorry, I was referring (implicitly) to Area(Path64 path) since you'd also mentioned overflow, and I didn't think you'd be concerned about overflow when multiplying floating point values And very the reason the integer version of Area returns a double is to avoid overflow. The alternative (used in Clipper1) is to use custom 128bit integers, but they create an unnecessary performance burden.