0

Based on How to determine if a list of polygon points are in clockwise order?

I've come up with the following code:

bool PointsClockwise(const std::vector<MyPoint>& points)
{  
  double sum = 0.0;
  for(size_t i = 0; i < points.size() - 1; ++i)
    sum += (points[i+1].x()-points[i].x()) * (points[i+1].y()+points[i].y());

  return sum > 0.0;
}

However, this seems to have wrong result in certain cases. Take for example the following ring:

LINESTRING(0 119,0 60,694 70,704 72,712 77,719 83,723 92,725 102,723 111,719 120,712 126,703 130)

It is in counter-clockwise order, but the function returns true.

Thanks!

Community
  • 1
  • 1
zedxz
  • 113
  • 1
  • 8

2 Answers2

1

You missed one of the line segments from your summation - namely the one connecting the last point with the first. Try that:

bool PointsClockwise(const std::vector<MyPoint>& points)
{  
  double sum = 0.0;
  for(size_t i = 0; i < points.size() - 1; ++i)
    sum += (points[i+1].x()-points[i].x()) * (points[i+1].y()+points[i].y());

  sum += (points[0].x()-points[points.size()-1].x()) * (points[0].y()+points[points.size()-1].y());

  return sum > 0.0;
}
Petar Ivanov
  • 91,536
  • 11
  • 82
  • 95
0

You need to include the case i == points.size() - 1, but to do that, you need to do some modular arithmetic in the loop, or else separate out the last iteration. Actually, just initialize sum to the last iteration:

double sum = (points[0].x() - points[points.size() - 1].x())
  * (points[0].y() + points[points.size() - 1].y());

and end the iteration at i < points.size() - 1

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521