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

Я уже реализовал сканирование Грэма, но вижу, что узким местом моей программы является сортировка (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 ());
}

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

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


c++ sorting algorithm math grahams-scan
person Ryper    schedule 12.01.2017    source источник
comment
Не ответ, но можно ли заменить сканирование Грэма монотонной цепочкой? Я имею в виду, что сортировка в монотонной цепочке выполняется по координатам, а не по углу, что делает ее немного быстрее.   -  person Juan Lopes    schedule 13.01.2017

Ответы (2)


arrow_upward
3
arrow_downward

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

Изображение, например, вы хотите сравнить две точки (x1, y1) и (x2, y2< /sub>), предполагая, что самая нижняя точка находится в точке (xp, yp). Посмотрите на два вектора v1 = (x1 - xp, y1 - y p) и v2 = (x2 - xp, y2 - y< под>p). Чтобы определить, находится ли v1 слева или справа от v2, что означает, что вы хотите посмотреть на знак угла, образованного от v с 1 по v2. Если он положительный, то v2 находится слева от v1, а если отрицательный, то v1 находится слева от v 2.

Двумерное перекрестное произведение обладает прекрасным свойством:

v1 v2 = |v1| |v2| грех()

где угол, полученный при переходе от v1 к v2. Это означает, что > 0, если v1 находится справа от v2 и наоборот. перекрестный продукт!

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

  • Если v1 v2 › 0, то v2 находится слева от v1.
  • Если v1 v2 = 0, то точки лежат на одной прямой.
  • Если v1 v2 ‹ 0, то v2 находится справа от v1.

Формула двумерного перекрестного произведения определяется выражением

(x1, y1) (x2, y2) = (x1< /sub> y2 - x2 y1)

Где здесь x1 представляет x1 - xp и т. д.

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

person templatetypedef    schedule 12.01.2017
comment
Да, я пробовал это, единственное, что я пропустил, это то, что моя функция возвращала целое число, а не число с плавающей запятой. Так что спасибо тебе. (Я работаю с поплавками) Кроме того, что, если углы одинаковы, а векторное произведение - нет? - person Ryper; 13.01.2017
comment
Не могли бы вы уточнить свой вопрос об углах? Я не совсем уловил это. - person templatetypedef; 13.01.2017
comment
@templatetypedef Но я думаю, что OP нужны функции сортировки для сортировки всех точек по углу, который они образуют с осью x. Для этого sin не работает, так как это не монотонно от [0, pi] радиан. Это он использовал функцию cosine для вычисления угла. - person Joe Black; 18.07.2021

arrow_upward
0
arrow_downward

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

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

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

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

person Alexander Anikin    schedule 13.01.2017