Алгоритм упаковки подарков с коллинеарными точками

Итак, я написал следующий код, основанный на примерах алгоритма упаковки подарков для нахождения выпуклой оболочки группы точек:

std::vector<sf::Vector2f> convexHull(const std::vector<sf::Vector2f>& _shape)
{
std::vector<sf::Vector2f> returnValue;
returnValue.push_back(leftmostPoint(_shape));
for (std::vector<sf::Vector2f>::const_iterator it = _shape.begin(), end = _shape.end(); it != end; ++it)
{
if (elementIncludedInVector(*it, returnValue)) continue;
bool allPointWereToTheLeft = true;
for (std::vector<sf::Vector2f>::const_iterator it1 = _shape.begin(); it1 != end; ++it1)
{
if (*it1 == *it || elementIncludedInVector(*it1, returnValue)) continue;
if (pointPositionRelativeToLine(returnValue.back(), *it, *it1) > 0.0f)
{
allPointWereToTheLeft = false;
break;
}
}
if (allPointWereToTheLeft)
{
returnValue.push_back(*it);
it = _shape.begin();
}
}
return returnValue;
}

Вот моя функция для определения, на какой стороне линии находится третья точка:

float pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C)
{
return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

Возврат отрицательного числа означает, что точка находится на одной стороне, положительная на другой, 0 означает, что три точки коллинеарны.
А теперь вопрос: как можно изменить приведенный выше код, чтобы он работал правильно, даже если в _shape есть коллинеарные точки?

3

Решение

Если некоторые точки коллинеарны, вам нужно выбрать самую дальнюю из них (с максимальным расстоянием до текущей точки)

4

Другие решения

Вы можете основывать свои рассуждения на «исключающем» отношении между двумя точками (вокруг общего центра), имея в виду, что A исключает B, если относительное расположение A и B доказывает, что B не может быть на выпуклой оболочке.

На рисунке зеленые точки исключают синюю, а красные — нет. Среди двух выровненных точек самая дальняя от центра исключает другую. Локус исключения — это открытая полуплоскость и полупрямая линия.

введите описание изображения здесь

Обратите внимание, что «исключение» является транзитивным и определяет общее упорядочение.

1

Это немного сложнее сделать правильно, чем код, который вы демонстрируете. Я сосредоточусь только на стабильности вашего предиката, а не на том, как вы справляетесь с коллинеарными точками. Предикат — это место, где вы делаете геометрические вычисления — pointPositionRelativeToLine,

Ваш код хорошо спроектирован так, что вы делаете только геометрические вычисления в предикате. Это необходимо, чтобы сделать его надежным. Увы, ваш предикат не должен возвращать число с плавающей запятой, но один результат из небольшого набора: либо LEFT, RIGHT или же COLLINEAR:

enum RelPos { LEFT, RIGHT, COLLINEAR };

RelPos pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C)
{
auto result = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
if (result < 0.0) return LEFT;
else if (result > 0.0) return RIGHT;
return COLLINEAR;
}

Затем вы можете выяснить, как гарантировать, что при любых трех точках верный ответ возвращается для любой их перестановки. Это необходимо, иначе ваш алгоритм не гарантированно будет работать.

Есть два основных подхода:

  1. Используйте правильный тип данных, который гарантирует точные результаты при использовании в вашем предикате.

  2. Примите, что с неточными типами данных, которые вы используете, есть некоторые входные данные, для которых результат не может быть вычислен. В частности, вы можете предложить предикату четвертое значение, INDETERMINATEи вернуть его в таких случаях.

Второй подход легко реализовать, вызвав исходный предикат для всех перестановок ввода:

enum RelPos { LEFT, RIGHT, COLLINEAR, INDETERMINATE };
typedef sf::Vector2f Point_2;

RelPos ppImpl(const Point_2 & A, const Point_2 & B, const Point_2 & C)
{
auto result = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
if (result < 0.0) return LEFT;
else if (result > 0.0) return RIGHT;
return COLLINEAR;
}

bool inverse(RelPos a, RelPos b) {
return a == LEFT && b == RIGHT || a == RIGHT && b == LEFT;
}

bool equal(RelPos a, RelPos b, RelPos c, RelPos d, RelPos e, RelPos f) {
return a==b && b==c && c==d && d==e && e==f;
}

RelPos pointPositionRelativeToLine(const Point_2 & A, const Point_2 & B, const Point_2 & C) {
auto abc = ppImpl(A, B, C);
auto bac = ppImpl(B, A, C);
auto acb = ppImpl(A, C, B);
auto cab = ppImpl(C, A, B);
auto bca = ppImpl(B, C, A);
auto cba = ppImpl(C, B, A);
if (abc == COLLINEAR) return equal(abc, bac, acb, cab, bca, cba) ?
COLLINEAR : INDETERMINATE;
if (!inverse(abc, bac) || !inverse(acb, cab) || !inverse(bca, cba))
return INDETERMINATE;
if (abc != bca || abc != cab)
return INDETERMINATE;
return abc;
}

Может быть ошибка в логике выше, будем надеяться, что я понял это правильно. Но это общий подход здесь. По крайней мере, вышеупомянутые тесты на заданном наборе данных должен пройти для алгоритма для работы с набором данных. Но я не припомню, если это достаточное условие.

Конечно, алгоритм должен завершиться, когда INDETERMINATE Результат получается из предиката:

const auto errVal = std::vector<sf::Vector2f>();
...
auto rel = pointPositionRelativeToLine(returnValue.back(), *it, *it1);
if (rel == INDETERMINATE) return errVal;
if (rel == RIGHT) {
allPointWereToTheLeft = false;
break;
}
0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector