Я реализовал решение @ templatetypedef в C++ для замкнутой многоугольной цепочки, описываемой двумя x,y векторами.Я прохожу многоугольник, и если точка коллинеарна предыдущей и следующей точке, я удаляю ее:
template<class T> void del_collinear_vanilla(std::vector<T> &x,
std::vector<T> &y) {
assert(x.size() == y.size());
size_t i = x.size();
size_t im1, ip1 = 0;
do {
i--;
im1 = i ? i - 1 : x.size() - 1;
if (are_collinear(x[ip1], y[ip1], x[i], y[i], x[im1], y[im1])) {
x.erase(x.begin() + i);
y.erase(y.begin() + i);
}
ip1 = i;
} while (i != 0);
}
, где реализация зависит от макроса / шаблона are_collinear(x0,y0,x1,y1,x2,y2).
Однако в некоторых случаях у меня все еще оставались коллинеарные точки на выходе.Это пример входных данных, с которыми алгоритм терпит неудачу:
В этом примере P5 совпадает с P0, а P4 имеет одинаковую ординату P0 и P1;Я немного изменил их координаты, чтобы показать все сегменты.Алгоритм должен возвращать только прямоугольник с вершинами P1, P2, P3, P4.
Выше, P6 коллинеарен с P5 и P0.Затем, как только P6 исключен, P5 и P0 совпадают, и они оба коллинеарны с P4 и P1.
Оказывается, что простая петля над каждой точкой, удаляя точку, если она является коллинеарной с предыдущим иследующая точка не дает правильного результата.
(В примере, скажем, вы начинаете с P0, и вы обнаружите, что он не коллинеарен точке до P6 и точке после P1. Тогда выпереходите к P1, P2, ... пока не достигнете P6. P6 коллинеарен, вы удаляете его, и цикл завершается. Но теперь P0 коллинеарен с P4 и P1, и он должен был быть удален!)
Тот же недостаток существует для открытого пути.Алгоритм работает нормально, пока входной путь не свернулся сам по себе , в некотором смысле.
Решение состоит в том, чтобы при каждом удалении точки делать шаг назад, чтобы проверить,предыдущая точка теперь стала коллинеарной:
template<class T> void del_collinear(std::vector<T> &x, std::vector<T> &y) {
assert(x.size() == y.size());
size_t target = x.size() - 1;
size_t i = x.size() - 1;
do {
size_t im1 = i ? i - 1 : x.size() - 1;
size_t ip1 = (i == x.size() - 1) ? 0 : i + 1;
if (are_collinear(x[ip1], y[ip1], x[i], y[i], x[im1], y[im1])) {
x.erase(x.begin() + i);
y.erase(y.begin() + i);
// I do not decrease i in this case, as the the previous (alread
// processed) point may now be a collinear point that must be
// deleted. I mod it because i may now exceed x.size()
i = i % x.size();
//Increment the target as well.
target = (i + 1 + x.size()) % x.size();
} else
//go for the next point.
i = i ? i - 1 : x.size() - 1;
} while (i != target);
}