Как правильно определить ориентацию кольцевых точек?

Question

На основании Как определить, находится ли список точек многоугольника по часовой стрелке?

Я придумал следующий код:

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;
}

Однако в некоторых случаях это, похоже, имеет неправильный результат. Возьмем, к примеру, следующее кольцо:

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)

Это в порядке против часовой стрелки, но функция возвращает true.

Спасибо!

Answer 1

Вы пропустили один из отрезков от суммирования, а именно тот, который соединяет последнюю точку с первой. Попробуйте это:

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;
}

Answer 2

Вам необходимо включить регистр i == points.size() - 1, но для этого вам нужно выполнить некоторую модульную арифметику в цикле или выделить последнюю итерацию.На самом деле, просто инициализируйте sum до последней итерации:

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

и завершите итерацию на i < points.size() - 1