Рубрики

Найти простой замкнутый путь для заданного набора точек

Учитывая набор точек, соедините точки без пересечения.

Пример:

Input: points[] = {(0, 3), (1, 1), (2, 2), (4, 4),
                   (0, 0), (1, 2), (3, 1}, {3, 3}};

Output: Connecting points in following order would
        not cause any crossing
       {(0, 0), (3, 1), (1, 1), (2, 2), (3, 3),
        (4, 4), (1, 2), (0, 3)}

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Идея состоит в том, чтобы использовать сортировку.

  1. Найдите самую нижнюю точку, сравнивая координату y всех точек. Если есть две точки с одинаковым значением y, то рассматривается точка с меньшим значением координаты x. Поместите самую нижнюю точку в первую позицию.
  2. Рассмотрим оставшиеся n-1 точек и отсортируем их по углу наклона в направлении против часовой стрелки вокруг точек [0]. Если угол наклона двух точек одинаков, то сначала ставьте ближайшую точку.
  3. Обход отсортированного массива (отсортированный в порядке возрастания угла) дает простой замкнутый путь.

Как рассчитать углы?
Одним из решений является использование тригонометрических функций.
Наблюдение: нас не волнуют фактические значения углов. Мы просто хотим отсортировать по углу.
Идея: использовать ориентацию для сравнения углов без фактического их вычисления!

Ниже приведена реализация вышеуказанной идеи на C ++.

// Программа на C ++ для поиска простого замкнутого пути для n точек
// для объяснения ориентации ()
#include <bits/stdc++.h>

using namespace std;

  

struct Point

{

    int x, y;

};

  
// Глобальная точка, необходимая для сортировки точек со ссылкой
// к первому пункту. Используется в функции сравнения qsort ()
Point p0;

  
// Утилита для обмена двумя точками

int swap(Point &p1, Point &p2)

{

    Point temp = p1;

    p1 = p2;

    p2 = temp;

}

  
// Функция полезности для возврата квадрата расстояния между
// p1 и p2

int dist(Point p1, Point p2)

{

    return (p1.x - p2.x)*(p1.x - p2.x) +

           (p1.y - p2.y)*(p1.y - p2.y);

}

  
// Найти ориентацию упорядоченного триплета (p, q, r).
// Функция возвращает следующие значения
// 0 -> p, q и r являются коллинеарными
// 1 -> по часовой стрелке
// 2 -> против часовой стрелки

int orientation(Point p, Point q, Point r)

{

    int val = (q.y - p.y) * (r.x - q.x) -

              (q.x - p.x) * (r.y - q.y);

  

    if (val == 0) return 0;  // коллинеар

    return (val > 0)? 1: 2; // по часовой стрелке или против часовой стрелки

}

  
// Функция, используемая библиотечной функцией qsort () для сортировки
// массив точек относительно первой точки

int compare(const void *vp1, const void *vp2)

{

   Point *p1 = (Point *)vp1;

   Point *p2 = (Point *)vp2;

  

   // Найти ориентацию

   int o = orientation(p0, *p1, *p2);

   if (o == 0)

     return (dist(p0, *p2) >= dist(p0, *p1))? -1 : 1;

  

   return (o == 2)? -1: 1;

}

  
// Печатает простой замкнутый путь для набора из n точек.

void printClosedPath(Point points[], int n)

{

   // Находим самую нижнюю точку

   int ymin = points[0].y, min = 0;

   for (int i = 1; i < n; i++)

   {

     int y = points[i].y;

  

     // Выберите самый нижний. В случае галстука, выбрал

     // левая крайняя точка

     if ((y < ymin) || (ymin == y &&

         points[i].x < points[min].x))

        ymin = points[i].y, min = i;

   }

  

   // Поместить самую нижнюю точку на первую позицию

   swap(points[0], points[min]);

  

   // Сортировка n-1 точек по первой точке.

   // Точка p1 идет перед p2 в отсортированном выходе, если p2

   // имеет больший полярный угол (против часовой стрелки

   // направление) чем р1

   p0 = points[0];

   qsort(&points[1], n-1, sizeof(Point), compare);

  

   // Теперь в стеке есть выходные точки, печатаем содержимое

   // стека

   for (int i=0; i<n; i++)

       cout << "(" << points[i].x << ", "

            << points[i].y <<"), ";

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},

                       {0, 0}, {1, 2}, {3, 1}, {3, 3}};

    int n = sizeof(points)/sizeof(points[0]);

    printClosedPath(points, n);

    return 0;

}

Выход:

(0, 0), (3, 1), (1, 1), (2, 2), (3, 3),
(4, 4), (1, 2), (0, 3), 

Временная сложность вышеуказанного решения составляет O (n Log n), если мы используем алгоритм сортировки O (nLogn) для сортировки точек.

Источник:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf

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

Рекомендуемые посты:

Найти простой замкнутый путь для заданного набора точек

0.00 (0%) 0 votes