Рубрики

Как проверить, находится ли данная точка внутри или снаружи многоугольника?

По заданному многоугольнику и точке 'p' найдите, находится ли 'p' внутри многоугольника или нет. Точки, лежащие на границе, рассматриваются внутри.

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

Ниже приводится простая идея проверить, находится ли точка внутри или снаружи.

1) Draw a horizontal line to the right of each point and extend it to infinity

1) Count the number of times the line intersects with polygon edges.

2) A point is inside the polygon if either count of intersections is odd or
   point lies on an edge of polygon.  If none of the conditions is true, then 
   point lies outside.

Как обработать точку «g» на рисунке выше?
Обратите внимание, что мы должны вернуть true, если точка лежит на прямой или совпадает с одной из вершин данного многоугольника. Чтобы справиться с этим, после проверки, пересекается ли линия от 'p' до крайнего, мы проверяем, является ли 'p' коллинеарным с вершинами текущей линии многоугольника. Если это coliear, то мы проверяем, лежит ли точка 'p' на текущей стороне многоугольника, если она лежит, мы возвращаем true, иначе false.

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

C ++

// Программа на C ++ для проверки, находится ли заданная точка внутри заданного многоугольника
// См. Https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/amp/
// для объяснения функций onSegment (), direction () и doIntersect ()
#include <iostream>

using namespace std;

  
// Определить бесконечность (использование INT_MAX вызвало проблемы переполнения)
#define INF 10000

  

struct Point

{

    int x;

    int y;

};

  
// Учитывая три коллинеарных точки p, q, r, функция проверяет,
// точка q лежит на отрезке прямой 'pr'

bool onSegment(Point p, Point q, Point r)

{

    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&

            q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))

        return true;

    return false;

}

  
// Найти ориентацию упорядоченного триплета (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; // часы или против часовой стрелки

}

  
// Функция, которая возвращает true, если отрезок линии 'p1q1'
// и 'p2q2' пересекаются.

bool doIntersect(Point p1, Point q1, Point p2, Point q2)

{

    // Находим четыре ориентации, необходимые для общего и

    // Особые случаи

    int o1 = orientation(p1, q1, p2);

    int o2 = orientation(p1, q1, q2);

    int o3 = orientation(p2, q2, p1);

    int o4 = orientation(p2, q2, q1);

  

    // Общий случай

    if (o1 != o2 && o3 != o4)

        return true;

  

    // Особые случаи

    // p1, q1 и p2 коллинеарны, а p2 лежит на отрезке p1q1

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

  

    // p1, q1 и p2 коллинеарны, а q2 лежит на отрезке p1q1

    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

  

    // p2, q2 и p1 коллинеарны, а p1 лежит на отрезке p2q2

    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

  

     // p2, q2 и q1 коллинеарны, а q1 лежит на отрезке p2q2

    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

  

    return false; // Не попадает ни в один из вышеперечисленных случаев

}

  
// Возвращает true, если точка p лежит внутри многоугольника [] с n вершинами

bool isInside(Point polygon[], int n, Point p)

{

    // В многоугольнике должно быть как минимум 3 вершины []

    if (n < 3)  return false;

  

    // Создать точку для отрезка от p до бесконечности

    Point extreme = {INF, p.y};

  

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

    int count = 0, i = 0;

    do

    {

        int next = (i+1)%n;

  

        // Проверяем, пересекается ли отрезок от 'p' до 'extreme'

        // с отрезком от 'polygon [i]' до 'polygon [next]'

        if (doIntersect(polygon[i], polygon[next], p, extreme))

        {

            // Если точка 'p' является коллинеарной с отрезком линии 'i-next',

            // затем проверяем, лежит ли он на сегменте. Если это ложь, верните истину,

            // иначе ложь

            if (orientation(polygon[i], p, polygon[next]) == 0)

               return onSegment(polygon[i], p, polygon[next]);

  

            count++;

        }

        i = next;

    } while (i != 0);

  

    // Возвращаем true, если count нечетно, иначе false

    return count&1;  // То же, что (count% 2 == 1)

}

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

int main()

{

    Point polygon1[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};

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

    Point p = {20, 20};

    isInside(polygon1, n, p)? cout << "Yes \n": cout << "No \n";

  

    p = {5, 5};

    isInside(polygon1, n, p)? cout << "Yes \n": cout << "No \n";

  

    Point polygon2[] = {{0, 0}, {5, 5}, {5, 0}};

    p = {3, 3};

    n = sizeof(polygon2)/sizeof(polygon2[0]);

    isInside(polygon2, n, p)? cout << "Yes \n": cout << "No \n";

  

    p = {5, 1};

    isInside(polygon2, n, p)? cout << "Yes \n": cout << "No \n";

  

    p = {8, 1};

    isInside(polygon2, n, p)? cout << "Yes \n": cout << "No \n";

  

    Point polygon3[] =  {{0, 0}, {10, 0}, {10, 10}, {0, 10}};

    p = {-1,10};

    n = sizeof(polygon3)/sizeof(polygon3[0]);

    isInside(polygon3, n, p)? cout << "Yes \n": cout << "No \n";

  

    return 0;

}

Джава

// Java-программа для проверки, является ли данная точка
// лежит внутри заданного многоугольника
// См. Https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/amp/
// для объяснения функций onSegment (),
// Ориентация () и doIntersect ()

class GFG

{

  

    // Определить бесконечность (используя INT_MAX

    // вызвал проблемы переполнения)

    static int INF = 10000;

  

    static class Point 

    {

        int x;

        int y;

  

        public Point(int x, int y)

        {

            this.x = x;

            this.y = y;

        }

    };

  

    // Даны три коллинеарных точки p, q, r,

    // функция проверяет, лежит ли точка q

    // в линейном сегменте 'pr'

    static boolean onSegment(Point p, Point q, Point r) 

    {

        if (q.x <= Math.max(p.x, r.x) &&

            q.x >= Math.min(p.x, r.x) &&

            q.y <= Math.max(p.y, r.y) &&

            q.y >= Math.min(p.y, r.y))

        {

            return true;

        }

        return false;

    }

  

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

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

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

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

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

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

    }

  

    // Функция, которая возвращает true, если

    // отрезок «p1q1» и «p2q2» пересекаются.

    static boolean doIntersect(Point p1, Point q1, 

                               Point p2, Point q2) 

    {

        // Находим четыре ориентации, необходимые для

        // общие и частные случаи

        int o1 = orientation(p1, q1, p2);

        int o2 = orientation(p1, q1, q2);

        int o3 = orientation(p2, q2, p1);

        int o4 = orientation(p2, q2, q1);

  

        // Общий случай

        if (o1 != o2 && o3 != o4)

        {

            return true;

        }

  

        // Особые случаи

        // p1, q1 и p2 являются коллинеарными и

        // p2 лежит на сегменте p1q1

        if (o1 == 0 && onSegment(p1, p2, q1)) 

        {

            return true;

        }

  

        // p1, q1 и p2 являются коллинеарными и

        // q2 лежит на отрезке p1q1

        if (o2 == 0 && onSegment(p1, q2, q1)) 

        {

            return true;

        }

  

        // p2, q2 и p1 являются коллинеарными и

        // p1 лежит на сегменте p2q2

        if (o3 == 0 && onSegment(p2, p1, q2))

        {

            return true;

        }

  

        // p2, q2 и q1 являются коллинеарными и

        // q1 лежит на отрезке p2q2

        if (o4 == 0 && onSegment(p2, q1, q2))

        {

            return true;

        }

  

        // Не попадает ни в один из вышеперечисленных случаев

        return false

    }

  

    // Возвращает true, если точка p лежит

    // внутри многоугольника [] с n вершинами

    static boolean isInside(Point polygon[], int n, Point p)

    {

        // В многоугольнике должно быть как минимум 3 вершины []

        if (n < 3

        {

            return false;

        }

  

        // Создать точку для отрезка от p до бесконечности

        Point extreme = new Point(INF, p.y);

  

        // Считаем пересечения вышеуказанной линии

        // со сторонами многоугольника

        int count = 0, i = 0;

        do 

        {

            int next = (i + 1) % n;

  

            // Проверяем, является ли отрезок от 'p' до

            // «крайний» пересекается с линией

            // сегментируем от 'polygon [i]' до 'polygon [next]'

            if (doIntersect(polygon[i], polygon[next], p, extreme)) 

            {

                // Если точка 'p' является коллинеарной с линией

                // сегментируем «i-next», затем проверяем, лежит ли он

                // на сегменте. Если это ложь, верните true, иначе false

                if (orientation(polygon[i], p, polygon[next]) == 0)

                {

                    return onSegment(polygon[i], p,

                                     polygon[next]);

                }

  

                count++;

            }

            i = next;

        } while (i != 0);

  

        // Возвращаем true, если count нечетно, иначе false

        return (count % 2 == 1); // То же, что (count% 2 == 1)

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        Point polygon1[] = {new Point(0, 0),

                            new Point(10, 0), 

                            new Point(10, 10), 

                            new Point(0, 10)};

        int n = polygon1.length;

        Point p = new Point(20, 20);

        if (isInside(polygon1, n, p))

        {

            System.out.println("Yes");

        

        else 

        {

            System.out.println("No");

        }

        p = new Point(5, 5);

        if (isInside(polygon1, n, p))

        {

            System.out.println("Yes");

        

        else 

        {

            System.out.println("No");

        }

        Point polygon2[] = {new Point(0, 0), 

            new Point(5, 5), new Point(5, 0)};

        p = new Point(3, 3);

        n = polygon2.length;

        if (isInside(polygon2, n, p)) 

        {

            System.out.println("Yes");

        

        else 

        {

            System.out.println("No");

        }

        p = new Point(5, 1);

        if (isInside(polygon2, n, p)) 

        {

            System.out.println("Yes");

        

        else 

        {

            System.out.println("No");

        }

        p = new Point(8, 1);

        if (isInside(polygon2, n, p))

        {

            System.out.println("Yes");

        

        else 

        {

            System.out.println("No");

        }

        Point polygon3[] = {new Point(0, 0), 

                            new Point(10, 0),

                            new Point(10, 10),

                            new Point(0, 10)};

        p = new Point(-1, 10);

        n = polygon3.length;

        if (isInside(polygon3, n, p))

        {

            System.out.println("Yes");

        

        else 

        {

            System.out.println("No");

        }

    }

}

  
// Этот код предоставлен 29AjayKumar

C #

// AC # программа для проверки наличия заданной точки
// лежит внутри заданного многоугольника
// См. Https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/amp/
// для объяснения функций onSegment (),
// Ориентация () и doIntersect ()

using System;

  

class GFG

{

  

    // Определить бесконечность (используя INT_MAX

    // вызвал проблемы переполнения)

    static int INF = 10000;

  

    class Point 

    {

        public int x;

        public int y;

  

        public Point(int x, int y)

        {

            this.x = x;

            this.y = y;

        }

    };

  

    // Даны три коллинеарных точки p, q, r,

    // функция проверяет, лежит ли точка q

    // в линейном сегменте 'pr'

    static bool onSegment(Point p, Point q, Point r) 

    {

        if (q.x <= Math.Max(p.x, r.x) &&

            q.x >= Math.Min(p.x, r.x) &&

            q.y <= Math.Max(p.y, r.y) &&

            q.y >= Math.Min(p.y, r.y))

        {

            return true;

        }

        return false;

    }

  

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

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

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

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

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

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

    }

  

    // Функция, которая возвращает true, если

    // отрезок «p1q1» и «p2q2» пересекаются.

    static bool doIntersect(Point p1, Point q1, 

                            Point p2, Point q2) 

    {

        // Находим четыре ориентации, необходимые для

        // общие и частные случаи

        int o1 = orientation(p1, q1, p2);

        int o2 = orientation(p1, q1, q2);

        int o3 = orientation(p2, q2, p1);

        int o4 = orientation(p2, q2, q1);

  

        // Общий случай

        if (o1 != o2 && o3 != o4)

        {

            return true;

        }

  

        // Особые случаи

        // p1, q1 и p2 являются коллинеарными и

        // p2 лежит на сегменте p1q1

        if (o1 == 0 && onSegment(p1, p2, q1)) 

        {

            return true;

        }

  

        // p1, q1 и p2 являются коллинеарными и

        // q2 лежит на отрезке p1q1

        if (o2 == 0 && onSegment(p1, q2, q1)) 

        {

            return true;

        }

  

        // p2, q2 и p1 являются коллинеарными и

        // p1 лежит на сегменте p2q2

        if (o3 == 0 && onSegment(p2, p1, q2))

        {

            return true;

        }

  

        // p2, q2 и q1 являются коллинеарными и

        // q1 лежит на отрезке p2q2

        if (o4 == 0 && onSegment(p2, q1, q2))

        {

            return true;

        }

  

        // Не попадает ни в один из вышеперечисленных случаев

        return false

    }

  

    // Возвращает true, если точка p лежит

    // внутри многоугольника [] с n вершинами

    static bool isInside(Point []polygon, int n, Point p)

    {

        // В многоугольнике должно быть как минимум 3 вершины []

        if (n < 3) 

        {

            return false;

        }

  

        // Создать точку для отрезка от p до бесконечности

        Point extreme = new Point(INF, p.y);

  

        // Считаем пересечения вышеуказанной линии

        // со сторонами многоугольника

        int count = 0, i = 0;

        do

        {

            int next = (i + 1) % n;

  

            // Проверяем, является ли отрезок от 'p' до

            // «крайний» пересекается с линией

            // сегментируем от 'polygon [i]' до 'polygon [next]'

            if (doIntersect(polygon[i], 

                            polygon[next], p, extreme)) 

            {

                // Если точка 'p' является коллинеарной с линией

                // сегментируем «i-next», затем проверяем, лежит ли он

                // на сегменте. Если это ложь, верните true, иначе false

                if (orientation(polygon[i], p, polygon[next]) == 0)

                {

                    return onSegment(polygon[i], p,

                                     polygon[next]);

                }

                count++;

            }

            i = next;

        } while (i != 0);

  

        // Возвращаем true, если count нечетно, иначе false

        return (count % 2 == 1); // То же, что (count% 2 == 1)

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        Point []polygon1 = {new Point(0, 0),

                            new Point(10, 0), 

                            new Point(10, 10), 

                            new Point(0, 10)};

        int n = polygon1.Length;

        Point p = new Point(20, 20);

        if (isInside(polygon1, n, p))

        {

            Console.WriteLine("Yes");

        

        else

        {

            Console.WriteLine("No");

        }

        p = new Point(5, 5);

        if (isInside(polygon1, n, p))

        {

            Console.WriteLine("Yes");

        

        else

        {

            Console.WriteLine("No");

        }

        Point []polygon2 = {new Point(0, 0), 

                            new Point(5, 5), 

                            new Point(5, 0)};

        p = new Point(3, 3);

        n = polygon2.Length;

        if (isInside(polygon2, n, p)) 

        {

            Console.WriteLine("Yes");

        

        else

        {

            Console.WriteLine("No");

        }

        p = new Point(5, 1);

        if (isInside(polygon2, n, p)) 

        {

            Console.WriteLine("Yes");

        

        else

        {

            Console.WriteLine("No");

        }

        p = new Point(8, 1);

        if (isInside(polygon2, n, p))

        {

            Console.WriteLine("Yes");

        

        else

        {

            Console.WriteLine("No");

        }

        Point []polygon3 = {new Point(0, 0), 

                            new Point(10, 0),

                            new Point(10, 10),

                            new Point(0, 10)};

        p = new Point(-1, 10);

        n = polygon3.Length;

        if (isInside(polygon3, n, p))

        {

            Console.WriteLine("Yes");

        

        else

        {

            Console.WriteLine("No");

        }

    }

}

  
// Этот код предоставлен 29AjayKumar

Выход:

No
Yes
Yes
Yes
No
No

Сложность времени: O (n) где n — количество вершин в данном многоугольнике.

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

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

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

Как проверить, находится ли данная точка внутри или снаружи многоугольника?

0.00 (0%) 0 votes