Алгоритм выпуклого корпуса — функция быстрого сравнения Грэма?

Question

Алгоритм выпуклого корпуса — функция быстрого сравнения Грэма?

Я уже реализовал сканирование Грэма, но я вижу, что узким местом моей программы является сортировка (80% времени). Я хочу улучшить это, сейчас я делаю следующее:

 std::sort(intersections.begin() + 1, intersections.end(), [&minElement](Point const& a, Point const& b)
{return angle (minElement - a, XAxis) < angle (minElement - b,XAxis);});

Что дает мне точный угол, но это не дешево, потому что моя функция угла выглядит следующим образом:

float angle (const Point& v1, const Point& v2) {
return dot (v1, v2) / (v1.Length () * v2.Length ());
}

В функции Length мне нужно сделать квадратный корень, что является одной из самых дорогих операций. Но так я получаю хороший заказ.

Я попытался упорядочить массив по Slope, dot, ccw и даже удалить только sqrt из моего сравнения, но ничего из этого не дает мне тот же порядок. Можете ли вы дать мне какой-нибудь совет?

1

algorithm c++grahams-scan math sorting

Решение

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

Вы можете сделать специальную оптимизацию через кэширование.

Во-первых, Length () может кэшировать свой результат в переменной-члене. Вам нужно только аннулировать это значение в случае изменения точки (и, возможно, это не так). Вы можете выполнить ленивый расчет, поэтому Length проверит, имеет ли оно значение, и вычислит / сохранит, если его нет, затем вернет сохраненное значение.

Во-вторых, для данного minElement и xAxis, угол (минЭлемент — а, ось X) становится функцией от 1 аргумента, поэтому вы можете сохранять (кэшировать) его значения для каждой точки перед сортировкой и использовать компаратор для подготовленных значений.

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

0

Источник

Accepted Answer

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

Изображение, например, вы хотите сравнить две точки (х₁, Y₁) и (х₂, Y₂), предполагая, что самая нижняя точка находится в (х_п, Y_п). Посмотрите на два вектора V₁ = (х₁ — Икс_п, Y₁ — Y_п) и V₂ = (х₂ — Икс_п, Y₂ — Y_п). Чтобы определить, v₁ находится слева или справа от v₂, Это означает, что вы хотите посмотреть на знак угла, идущего от V₁ к V₂. Если это положительно, то V₂ находится слева от V₁, и если это отрицательно, то V₁ находится слева от V₂.

2D-перекрестное произведение обладает хорошим свойством

v₁ × V₂ = | V₁| | v₂| Sin (θ)

где θ — угол, образованный переходом от v₁ к V₂. Это означает, что θ> 0, если v₁ находится справа от v₂ и наоборот, что приятно, так как позволяет сравнивать, куда идет, просто взяв перекрестный продукт!

Другими словами:

Если v₁ × V₂ > 0, то v₂ находится слева от v₁.
Если v₁ × V₂ = 0, то точки коллинеарны.
Если v₁ × V₂ < 0, то v₂ находится справа от v₁.

2D формула кросс-произведения определяется как

(? x₁, Δy₁) × (Δx₂, Δy₂) = (Δx₁ Δy₂ — ? x₂ Δy₁)

Где, здесь, Δx₁ представляет х₁ — Икс_п, и т.п.

Таким образом, вы можете вычислить вышеуказанное количество, а затем посмотреть на его знак, чтобы определить, как эти две точки связаны друг с другом. Квадратные корни не нужны!

3