Рубрики

Выпуклая оболочка | Набор 1 (алгоритм Джарвиса или упаковка)

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

Мы настоятельно рекомендуем сначала увидеть следующий пост.
Как проверить, пересекаются ли два заданных отрезка?

Идея алгоритма Джарвиса проста: мы начинаем с крайней левой точки (или точки с минимальным значением координаты x) и сохраняем точки обтекания в направлении против часовой стрелки. Большой вопрос, учитывая точку p как текущую точку, как найти следующую точку в выводе? Идея в том, чтобы использовать ориентацию () здесь. Следующая точка выбирается в качестве точки, которая бьет все остальные точки в ориентации против часовой стрелки, т. Е. Следующая точка равна q, если для любой другой точки r мы имеем «ориентацию (p, q, r) = против часовой стрелки». Ниже приводится подробный алгоритм.

1) Инициализируйте p как крайнюю левую точку.
2) Следуйте, пока мы не вернемся к первой (или самой левой) точке.
… .. a) Следующая точка q — это точка, такая, что триплет (p, q, r) против часовой стрелки для любой другой точки r.
… .. b) next [p] = q (сохранить q как следующее из p в выходной выпуклой оболочке).
… .. c) p = q (установите p как q для следующей итерации).

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// Программа на C ++ для поиска выпуклой оболочки множества точек. обращаться
// https://www.geeksforgeeks.org/orientation-3-ordered-points/amp/
// для объяснения ориентации ()
#include <bits/stdc++.h>

using namespace std;

  

struct Point

{

    int x, 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; // часы или против часовой стрелки

}

  
// Печатает выпуклую оболочку из набора из n точек.

void convexHull(Point points[], int n)

{

    // Должно быть не менее 3 баллов

    if (n < 3) return;

  

    // Инициализировать результат

    vector<Point> hull;

  

    // Найти крайнюю левую точку

    int l = 0;

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

        if (points[i].x < points[l].x)

            l = i;

  

    // Начинаем с крайней левой точки, продолжаем двигаться против часовой стрелки

    // пока снова не достигнем начальной точки. Этот цикл запускает O (h)

    // время, где h - количество точек в результате или выходе.

    int p = l, q;

    do

    {

        // Добавить текущую точку к результату

        hull.push_back(points[p]);

  

        // Поиск точки 'q' такой, что ориентация (p, x,

        // q) против часовой стрелки для всех точек 'x'. Идея

        // отслеживать последние посещенные часы

        // мудрый пункт в д. Если любая точка «я» больше против часовой стрелки

        // мудрее чем q, тогда обновите q.

        q = (p+1)%n;

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

        {

           // Если я больше против часовой стрелки, чем текущий q, то

           // обновляем q

           if (orientation(points[p], points[i], points[q]) == 2)

               q = i;

        }

  

        // Теперь q наиболее против часовой стрелки относительно p

        // Установить p как q для следующей итерации, так что q добавляется к

        // результат 'корпус'

        p = q;

  

    } while (p != l);  // Пока мы не подошли к первому пункту

  

    // Распечатать результат

    for (int i = 0; i < hull.size(); i++)

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

              << hull[i].y << ")\n";

}

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

int main()

{

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

                      {3, 0}, {0, 0}, {3, 3}};

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

    convexHull(points, n);

    return 0;

}

Джава

// Java-программа для поиска выпуклой оболочки множества точек. обращаться
// https://www.geeksforgeeks.org/orientation-3-ordered-points/amp/
// для объяснения ориентации ()

import java.util.*;

  

class Point

{

    int x, y;

    Point(int x, int y){

        this.x=x;

        this.y=y;

    }

}

  

class GFG {

      

    // Найти ориентацию упорядоченного триплета (p, q, r).

    // Функция возвращает следующие значения

    // 0 -> p, q и r являются коллинеарными

    // 1 -> по часовой стрелке

    // 2 -> против часовой стрелки

    public static 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; // часы или против часовой стрелки

    }

      

    // Печатает выпуклую оболочку из набора из n точек.

    public static void convexHull(Point points[], int n)

    {

        // Должно быть не менее 3 баллов

        if (n < 3) return;

       

        // Инициализировать результат

        Vector<Point> hull = new Vector<Point>();

       

        // Найти крайнюю левую точку

        int l = 0;

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

            if (points[i].x < points[l].x)

                l = i;

       

        // Начинаем с крайней левой точки, продолжаем двигаться

        // против часовой стрелки до достижения начальной точки

        // опять таки. Этот цикл выполняется O (h) раз, где h

        // количество точек в результате или выходе.

        int p = l, q;

        do

        {

            // Добавить текущую точку к результату

            hull.add(points[p]);

       

            // Поиск точки 'q' такой, что

            // ориентация (p, x, q) против часовой стрелки

            // для всех точек «х». Идея состоит в том, чтобы сохранить

            // трек последнего посещенного наиболее

            // мудрый пункт в д. Если любая точка «я» больше

            // против часовой стрелки, чем q, затем обновляем q.

            q = (p + 1) % n;

              

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

            {

               // Если я против часовой стрелки

               // текущее q, затем обновляемое q

               if (orientation(points[p], points[i], points[q])

                                                   == 2)

                   q = i;

            }

       

            // Теперь q наиболее против часовой стрелки с

            // уважение к р. Установите p как q для следующей итерации,

            // так что q добавляется к результату 'hull'

            p = q;

       

        } while (p != l);  // Пока мы не приходим к первому

                           // точка

       

        // Распечатать результат

        for (Point temp : hull)

            System.out.println("(" + temp.x + ", " +

                                temp.y + ")");

    }

      

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

    public static void main(String[] args) 

    {

  

        Point points[] = new Point[7];

        points[0]=new Point(0, 3);

        points[1]=new Point(2, 3);

        points[2]=new Point(1, 1);

        points[3]=new Point(2, 1);

        points[4]=new Point(3, 0);

        points[5]=new Point(0, 0);

        points[6]=new Point(3, 3);

          

        int n = points.length;

        convexHull(points, n);

         

    }

}

    
// Этот код предоставлен Арнавом Кр. Мандал.

python3

# C # программа для поиска выпуклой оболочки множества точек. обращаться
# https://www.geeksforgeeks.org/orientation-3-ordered-points/amp/
# для объяснения ориентации ()

  
# точка класса с х, у в качестве точки

class Point:

    def __init__(self, x, y):

        self.x = x

        self.y = y

  

def Left_index(points):

      

    «»»

    Нахождение самой левой точки

    «»»

    minn = 0

    for i in range(1,len(points)):

        if points[i].x < points[minn].x:

            minn = i

        elif points[i].x == points[minn].x:

            if points[i].y > points[minn].y:

                minn = i

    return minn

  

def orientation(p, q, r):

    «»»

    Найти ориентацию упорядоченного триплета (p, q, r).

    Функция возвращает следующие значения

    0 -> p, q и r являются коллинеарными

    1 -> по часовой стрелке

    2 -> против часовой стрелки

    «»»

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

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

  

    if val == 0:

        return 0

    elif val > 0:

        return 1

    else:

        return 2

  

def convexHull(points, n):

      

    # Должно быть не менее 3 баллов

    if n < 3:

        return

  

    # Найти крайнюю левую точку

    l = Left_index(points)

  

    hull = []

      

    «»»

    Начните с крайней левой точки, продолжайте движение против часовой стрелки

    пока не достигните начальной точки снова. Этот цикл запускает O (h)

    времена, где h количество точек в результате или выходе.

    «»»

    p = l

    q = 0

    while(True):

          

        # Добавить текущую точку к результату

        hull.append(p)

  

        «»»

        Поиск точки «q» такой, что ориентация (р, х,

        q) против часовой стрелки для всех точек «x». Идея

        отслеживать последние посещенные наиболее

        мудрый момент в д. Если любая точка «я» больше против часовой стрелки

        мудрее чем q, тогда обновите q.

        «»»

        q = (p + 1) % n

  

        for i in range(n):

              

            # Если я больше против часовой стрелки

            # чем текущий q, затем обновить q

            if(orientation(points[p], 

                           points[i], points[q]) == 2):

                q = i

  

        «»»

        Теперь q наиболее против часовой стрелки относительно p

        Установите p как q для следующей итерации, так что q добавляется к

        результат 'корпус'

        «»»

        p = q

  

        # Пока мы не подошли к первому пункту

        if(p == l):

            break

  

    # Печать результата

    for each in hull:

        print(points[each].x, points[each].y)

  
Код водителя

points = []

points.append(Point(0, 3))

points.append(Point(2, 2))

points.append(Point(1, 1))

points.append(Point(2, 1))

points.append(Point(3, 0))

points.append(Point(0, 0))

points.append(Point(3, 3))

  

convexHull(points, len(points))

  
# Этот код предоставлен
# Akarsh Somani, IIIT Kalyani

C #

// C # программа для поиска выпуклой оболочки множества точек. обращаться
// https://www.geeksforgeeks.org/orientation-3-ordered-points/amp/
// для объяснения ориентации ()

using System;

using System.Collections.Generic; 

      

public class Point

{

    public int x, y;

    public Point(int x, int y)

    {

        this.x = x;

        this.y = y;

    }

}

  

public class GFG 

{

      

    // Найти ориентацию упорядоченного триплета (p, q, r).

    // Функция возвращает следующие значения

    // 0 -> p, q и r являются коллинеарными

    // 1 -> по часовой стрелке

    // 2 -> против часовой стрелки

    public static 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; // часы или против часовой стрелки

    }

      

    // Печатает выпуклую оболочку из набора из n точек.

    public static void convexHull(Point []points, int n)

    {

        // Должно быть не менее 3 баллов

        if (n < 3) return;

      

        // Инициализировать результат

        List<Point> hull = new List<Point>();

      

        // Найти крайнюю левую точку

        int l = 0;

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

            if (points[i].x < points[l].x)

                l = i;

      

        // Начинаем с крайней левой точки, продолжаем двигаться

        // против часовой стрелки до достижения начальной точки

        // опять таки. Этот цикл выполняется O (h) раз, где h

        // количество точек в результате или выходе.

        int p = l, q;

        do

        {

            // Добавить текущую точку к результату

            hull.Add(points[p]);

      

            // Поиск точки 'q' такой, что

            // ориентация (p, x, q) против часовой стрелки

            // для всех точек «х». Идея состоит в том, чтобы сохранить

            // трек последнего посещенного наиболее

            // мудрый пункт в д. Если любая точка «я» больше

            // против часовой стрелки, чем q, затем обновляем q.

            q = (p + 1) % n;

              

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

            {

            // Если я против часовой стрелки

            // текущее q, затем обновляемое q

            if (orientation(points[p], points[i], points[q])

                                                == 2)

                q = i;

            }

      

            // Теперь q наиболее против часовой стрелки с

            // уважение к р. Установите p как q для следующей итерации,

            // так что q добавляется к результату 'hull'

            p = q;

      

        } while (p != l); // Пока мы не приходим к первому

                        // точка

      

        // Распечатать результат

        foreach (Point temp in hull)

            Console.WriteLine("(" + temp.x + ", " +

                                temp.y + ")");

    }

      

    / * Код водителя * /

    public static void Main(String[] args) 

    {

  

        Point []points = new Point[7];

        points[0]=new Point(0, 3);

        points[1]=new Point(2, 3);

        points[2]=new Point(1, 1);

        points[3]=new Point(2, 1);

        points[4]=new Point(3, 0);

        points[5]=new Point(0, 0);

        points[6]=new Point(3, 3);

          

        int n = points.Length;

        convexHull(points, n);

          

    }

}

  
// Этот код предоставлен Принчи Сингхом


Вывод: вывод — это точки выпуклой оболочки.

(0, 3)
(0, 0)
(3, 0)
(3, 3)

Сложность времени: Для каждой точки на корпусе мы исследуем все остальные точки, чтобы определить следующую точку. Временная сложность равна? (M * n), где n — количество входных точек, а m — количество выходных точек или точек корпуса (m <= n). В худшем случае сложность времени равна O (n 2 ). Наихудший случай возникает, когда все точки на корпусе (m = n)

Комплект 2 — выпуклый корпус (сканирование Грэма)

Источники:
http://www.cs.uiuc.edu/~jeffe/teaching/373/notes/x05-convexhull.pdf
http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1.pdf

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

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

Выпуклая оболочка | Набор 1 (алгоритм Джарвиса или упаковка)

0.00 (0%) 0 votes