код выпуклой оболочки «конкурентного программирования 1»;
Я пытаюсь понять алгоритм «выпуклой оболочки» в книге Стивена Халима и Феликса Халима Конкурентное программирование. Проблема «выпуклой оболочки», учитывая коллекцию п из N точки на плоскости, чтобы найти подмножество СН(п), которая образует вершины выпуклого многоугольника, содержащего все остальные точки. Вот изображение, описывающее их подход:
Их алгоритм начинается с сортировки точек по их углу относительно «оси», а именно, самой нижней и правой точки в п.
У меня есть некоторые проблемы с пониманием их angle_comp функция — что она делает и какова ее цель. Может ли кто-нибудь помочь мне понять это?
typedef struct {
double x, y ;
} point;
point pivot;
// A function to compute the distance between two points:
double dist2 (point a, point b)
{
double dx = a.x - b.x ;
double dy = a.y - b.y ;
return sqrt (dx *dx + dy * dy) ;
}
// A function to compare the angles of two points with respect to the pivot:
bool angle_comp (point a, point b)
{
if (fabs(area2(pivot, a, b) - 0) < 10e-9)
return dist2(pivot, a) < dist2(pivot, b);
int d1x = a.x - pivot.x, d1y = a.y - pivot.y;
int d2x = b.x - pivot.x, d2y = b.y - pivot.y;
return (atan2((double) d1y, (double) d1x)
- atan2 ((double) d2y, (double)d2x))
< 0;
}
Решение
Если я правильно понимаю ваш вопрос, вы хотите знать, почему важна функция сортировки? Это потому, что ваш код использует сканирование Грэма, метод поиска выпуклой оболочки. Чтобы сканирование Грэма было более эффективным, точки должны быть отсортированы по их углу относительно фиксированной точки.
angle_comp Функция сравнивает углы двух точек A и B относительно точки поворота. Эта функция при подключении к std::sortПозволяет отсортировать все точки вокруг оси на основе их угла относительно или расстояния от точки.
Для двух точек А и В вокруг разворота. Если точки A и B имеют один и тот же угол, или если оба из них находятся рядом с осью, то нам нужен альтернативный способ сортировки двух точек. Вместо этого мы сортируем точки по их расстоянию от оси.
Иначе, мы узнаем, где точки A и B относительно нашего центра. Мы делаем это, вычитая стержень из наших точек. Так, если, например, наш пивот равен (4, 3), а А равен (5, 7), то А равен 1 единице справа и на 4 единицы выше нашего пивота. Если наш стержень равен (0, 0), то A будет (1, 4). Надеюсь, это понятно.
После того, как у нас есть относительная точка, то есть D, мы вычисляем угол точки относительно нашей оси или начала координат. atan2 принимает два параметра, значение y нашей точки и значение x нашей точки, и выплевывает угол нашей точки в радианах. За atan20 радиан определяется как любая точка (N, 0) от начала координат, и когда радианы увеличиваются, точка идет против часовой стрелки вокруг точки поворота или начала координат.
Затем мы вычитаем угол D из угла D2. Если угол D2 больше, чем угол D1, мы вернемся с истиной, и std::sort может использовать эти возвращенные данные для сортировки углов против часовой стрелки.
Другие решения
Других решений пока нет …