Сортировка точек в векторе для формирования conture

Question

У меня есть вектор с n строками с xy координатами точек. Эти точки составляют контур данной модели САПР. Теперь я хочу восстановить внешний вид модели. Поэтому я попытался разобраться с функцией atan2. Это код, который я использую для сортировки очков.

std::sort(matrix.begin(), matrix.end(), sort1); 

matrix.erase(std::unique(matrix.begin(), matrix.end(), compare2),matrix.end()); 

matrix.push_back(std::vector<double>(3, 0)); 

Итак, сначала я сортирую точки в векторной матрице. Как сравнить функции я использую этот код

bool sort1(vector<double> const& s1, vector<double> const& s2) 
{ 
    return atan2(s1[1],s1[0])<atan2(s2[1],s2[0]); 
} 

После того, как вектор был отсортирован, я просто удалить дубликаты, чтобы уменьшить размер вектора. Последний шаг - отбросить первую точку до конца вектора, чтобы закрыть контур. Для стандартных моделей, таких как куб или шар, это отлично работает, но для более сложных моделей функция atan2 замечает, что работает нормально. Итак, это изображение показывает несортированные точки.

Когда сортировать вектор я получаю эту Контурный как результат

Мой первый подход для проверки функции ATAN2, но работает отлично. Проблема, похоже, является результатом функции atan2. Так что этот список показывает фактические координаты и результат функции atan2

x    y  z  atan2 
-5.44283 -1.94995 0 -2.79758 
-5.36969 -1.93228 0 -2.79617 
-5.33637 -1.92454 0 -2.79547 
-13.15  -4.76500 0 -2.79395 
-5.26308 -1.90750 0 -2.79389 
-5.22970 -1.90005 0 -2.7931 
-5.15626 -1.88364 0 -2.79134 

Как вы можете видеть, в то время как х и у координат изменить atan2 остается в том же диапазоне, что и другие значения. Для меня в этом проблема, почему мое убеждение неверно. Должен ли я добавить что-то к моей функции сортировки, чтобы получить правильные результаты?

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

Answer 1

atan2, очевидно, не поможет в общем случае. Это в основном полезно для выпуклых фигур. Рассмотрим узкий прямоугольник с (0,0) внутри и соседний прямоугольник и попробуйте отсортировать их точки по их atan2. Вы пробовали рисовать точку в наборе, а затем искали ближайшую, еще не нарисованную точку, как шаг итерации?

Answer 2

Если вы имеете дело с кривыми только тогда я предложил бы использовать следующий алгоритм:

1. Определить диапазон угла R
2. Возьмем начальную точку , пометить его как посетил
3. Найти ближайший к AB, отметьте его как посетивший
4. Рассчитать е направление, образованный вектором [, В]
5. Найти ближайший к B непосещенная точка С в диапазоне углов R и пометить его посетили
6. Перейти к шагу 4 с B как и С, как Б

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