¿Cómo verificar si un punto dado se encuentra dentro o fuera de un polígono?

Dado un polígono y un punto ‘ p ‘, encuentre si ‘ p ‘ se encuentra dentro del polígono o no. Los puntos que se encuentran en el borde se consideran interiores.

Ejemplos:

check if a given point lies inside or outside a polygon 1

Enfoque: La idea para resolver este problema se basa en Cómo verificar si dos segmentos de línea dados se intersecan , y se usará de la siguiente manera:

  1. Dibuja una línea horizontal a la derecha de cada punto y extiéndela hasta el infinito.
  2. Cuente el número de veces que la línea se cruza con los bordes del polígono.
  3. Un punto está dentro del polígono si el número de intersecciones es impar o si el punto se encuentra en un borde del polígono. Si ninguna de las condiciones es verdadera, entonces el punto está fuera.

check if a given point lies inside or outside a polygon 2

¿Cómo manejar el punto ‘g’ en la figura anterior? 

Tenga en cuenta que debemos devolver verdadero si el punto se encuentra en la línea o en uno de los vértices del polígono dado. Para manejar esto, después de verificar si la línea desde ‘p’ hasta el extremo se cruza, verificamos si ‘p’ es colineal con los vértices de la línea actual del polígono. Si es colineal, verificamos si el punto ‘p’ se encuentra en el lado actual del polígono, si se encuentra, devolvemos verdadero, de lo contrario, falso.

La siguiente es la implementación del enfoque anterior: 

C++

// A C++ program to check if a given point lies inside a given polygon
// Refer https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
// for explanation of functions onSegment(), orientation() and doIntersect()
#include <iostream>
using namespace std;
 
// Define Infinite (Using INT_MAX caused overflow problems)
#define INF 10000
 
struct Point
{
    int x;
    int y;
};
 
// Given three collinear points p, q, r, the function checks if
// point q lies on line segment '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;
}
 
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are collinear
// 1 --> Clockwise
// 2 --> Counterclockwise
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; // collinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}
 
// The function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);
 
    // General case
    if (o1 != o2 && o3 != o4)
        return true;
 
    // Special Cases
    // p1, q1 and p2 are collinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
 
    // p1, q1 and p2 are collinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
 
    // p2, q2 and p1 are collinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
 
    // p2, q2 and q1 are collinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;
 
    return false; // Doesn't fall in any of the above cases
}
 
// Returns true if the point p lies inside the polygon[] with n vertices
bool isInside(Point polygon[], int n, Point p)
{
    // There must be at least 3 vertices in polygon[]
    if (n < 3) return false;
 
    // Create a point for line segment from p to infinite
    Point extreme = {INF, p.y};
   
      // To count number of points in polygon
      // whose y-coordinate is equal to
      // y-coordinate of the point
      int decrease = 0;
 
    // Count intersections of the above line with sides of polygon
    int count = 0, i = 0;
    do
    {
        int next = (i+1)%n;
       
          if(polygon[i].y == p.y) decrease++;
 
        // Check if the line segment from 'p' to 'extreme' intersects
        // with the line segment from 'polygon[i]' to 'polygon[next]'
        if (doIntersect(polygon[i], polygon[next], p, extreme))
        {
            // If the point 'p' is collinear with line segment 'i-next',
            // then check if it lies on segment. If it lies, return true,
            // otherwise false
            if (orientation(polygon[i], p, polygon[next]) == 0)
            return onSegment(polygon[i], p, polygon[next]);
 
            count++;
        }
        i = next;
    } while (i != 0);
     
  // Reduce the count by decrease amount
  // as these points would have been added twice
      count -= decrease;
   
    // Return true if count is odd, false otherwise
    return count&1; // Same as (count%2 == 1)
}
 
// Driver program to test above functions
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

// A Java program to check if a given point
// lies inside a given polygon
// Refer https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
// for explanation of functions onSegment(),
// orientation() and doIntersect()
class GFG
{
 
    // Define Infinite (Using INT_MAX
    // caused overflow problems)
    static int INF = 10000;
 
    static class Point
    {
        int x;
        int y;
 
        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    };
 
    // Given three collinear points p, q, r,
    // the function checks if point q lies
    // on line segment '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;
    }
 
    // To find orientation of ordered triplet (p, q, r).
    // The function returns following values
    // 0 --> p, q and r are collinear
    // 1 --> Clockwise
    // 2 --> Counterclockwise
    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; // collinear
        }
        return (val > 0) ? 1 : 2; // clock or counterclock wise
    }
 
    // The function that returns true if
    // line segment 'p1q1' and 'p2q2' intersect.
    static boolean doIntersect(Point p1, Point q1,
                            Point p2, Point q2)
    {
        // Find the four orientations needed for
        // general and special cases
        int o1 = orientation(p1, q1, p2);
        int o2 = orientation(p1, q1, q2);
        int o3 = orientation(p2, q2, p1);
        int o4 = orientation(p2, q2, q1);
 
        // General case
        if (o1 != o2 && o3 != o4)
        {
            return true;
        }
 
        // Special Cases
        // p1, q1 and p2 are collinear and
        // p2 lies on segment p1q1
        if (o1 == 0 && onSegment(p1, p2, q1))
        {
            return true;
        }
 
        // p1, q1 and p2 are collinear and
        // q2 lies on segment p1q1
        if (o2 == 0 && onSegment(p1, q2, q1))
        {
            return true;
        }
 
        // p2, q2 and p1 are collinear and
        // p1 lies on segment p2q2
        if (o3 == 0 && onSegment(p2, p1, q2))
        {
            return true;
        }
 
        // p2, q2 and q1 are collinear and
        // q1 lies on segment p2q2
        if (o4 == 0 && onSegment(p2, q1, q2))
        {
            return true;
        }
 
        // Doesn't fall in any of the above cases
        return false;
    }
 
    // Returns true if the point p lies
    // inside the polygon[] with n vertices
    static boolean isInside(Point polygon[], int n, Point p)
    {
        // There must be at least 3 vertices in polygon[]
        if (n < 3)
        {
            return false;
        }
 
        // Create a point for line segment from p to infinite
        Point extreme = new Point(INF, p.y);
       
          // To count number of points in polygon
          // whose y-coordinate is equal to
          // y-coordinate of the point
          int decrease = 0;
 
        // Count intersections of the above line
        // with sides of polygon
        int count = 0, i = 0;
        do
        {
            int next = (i + 1) % n;
               
              if(polygon[i].y == p.y) decrease++;
 
            // Check if the line segment from 'p' to
            // 'extreme' intersects with the line
            // segment from 'polygon[i]' to 'polygon[next]'
            if (doIntersect(polygon[i], polygon[next], p, extreme))
            {
                // If the point 'p' is collinear with line
                // segment 'i-next', then check if it lies
                // on segment. If it lies, return true, otherwise false
                if (orientation(polygon[i], p, polygon[next]) == 0)
                {
                    return onSegment(polygon[i], p,
                                    polygon[next]);
                }
 
                count++;
            }
            i = next;
        } while (i != 0);
       
          // Reduce the count by decrease amount
          // as these points would have been added twice
          count -= decrease;
 
        // Return true if count is odd, false otherwise
        return (count % 2 == 1); // Same as (count%2 == 1)
    }
 
    // Driver Code
    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");
        }
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# A Python3 program to check if a given point 
# lies inside a given polygon
# Refer https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
# for explanation of functions onSegment(),
# orientation() and doIntersect() 
 
# Define Infinite (Using INT_MAX 
# caused overflow problems)
INT_MAX = 10000
 
# Given three collinear points p, q, r, 
# the function checks if point q lies
# on line segment 'pr'
def onSegment(p:tuple, q:tuple, r:tuple) -> bool:
     
    if ((q[0] <= max(p[0], r[0])) &
        (q[0] >= min(p[0], r[0])) &
        (q[1] <= max(p[1], r[1])) &
        (q[1] >= min(p[1], r[1]))):
        return True
         
    return False
 
# To find orientation of ordered triplet (p, q, r).
# The function returns following values
# 0 --> p, q and r are collinear
# 1 --> Clockwise
# 2 --> Counterclockwise
def orientation(p:tuple, q:tuple, r:tuple) -> int:
     
    val = (((q[1] - p[1]) *
            (r[0] - q[0])) -
           ((q[0] - p[0]) *
            (r[1] - q[1])))
            
    if val == 0:
        return 0
    if val > 0:
        return 1 # Collinear
    else:
        return 2 # Clock or counterclock
 
def doIntersect(p1, q1, p2, q2):
     
    # Find the four orientations needed for 
    # general and special cases
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)
 
    # General case
    if (o1 != o2) and (o3 != o4):
        return True
     
    # Special Cases
    # p1, q1 and p2 are collinear and
    # p2 lies on segment p1q1
    if (o1 == 0) and (onSegment(p1, p2, q1)):
        return True
 
    # p1, q1 and p2 are collinear and
    # q2 lies on segment p1q1
    if (o2 == 0) and (onSegment(p1, q2, q1)):
        return True
 
    # p2, q2 and p1 are collinear and
    # p1 lies on segment p2q2
    if (o3 == 0) and (onSegment(p2, p1, q2)):
        return True
 
    # p2, q2 and q1 are collinear and
    # q1 lies on segment p2q2
    if (o4 == 0) and (onSegment(p2, q1, q2)):
        return True
 
    return False
 
# Returns true if the point p lies 
# inside the polygon[] with n vertices
def is_inside_polygon(points:list, p:tuple) -> bool:
     
    n = len(points)
     
    # There must be at least 3 vertices
    # in polygon
    if n < 3:
        return False
         
    # Create a point for line segment
    # from p to infinite
    extreme = (INT_MAX, p[1])
     
    # To count number of points in polygon
      # whose y-coordinate is equal to
      # y-coordinate of the point
    decrease = 0
    count = i = 0
     
    while True:
        next = (i + 1) % n
         
        if(points[i][1] == p[1]):
            decrease += 1
         
        # Check if the line segment from 'p' to 
        # 'extreme' intersects with the line 
        # segment from 'polygon[i]' to 'polygon[next]'
        if (doIntersect(points[i],
                        points[next],
                        p, extreme)):
                             
            # If the point 'p' is collinear with line 
            # segment 'i-next', then check if it lies 
            # on segment. If it lies, return true, otherwise false
            if orientation(points[i], p,
                           points[next]) == 0:
                return onSegment(points[i], p,
                                 points[next])
                                  
            count += 1
             
        i = next
         
        if (i == 0):
            break
             
    # Reduce the count by decrease amount
      # as these points would have been added twice
    count -= decrease
     
    # Return true if count is odd, false otherwise
    return (count % 2 == 1)
 
# Driver code
if __name__ == '__main__':
     
    polygon1 = [ (0, 0), (10, 0), (10, 10), (0, 10) ]
     
    p = (20, 20)
    if (is_inside_polygon(points = polygon1, p = p)):
      print ('Yes')
    else:
      print ('No')
       
    p = (5, 5)
    if (is_inside_polygon(points = polygon1, p = p)):
      print ('Yes')
    else:
      print ('No')
 
    polygon2 = [ (0, 0), (5, 0), (5, 5), (3, 3) ]
     
    p = (3, 3)
    if (is_inside_polygon(points = polygon2, p = p)):
      print ('Yes')
    else:
      print ('No')
       
    p = (5, 1)
    if (is_inside_polygon(points = polygon2, p = p)):
      print ('Yes')
    else:
      print ('No')
       
    p = (8, 1)
    if (is_inside_polygon(points = polygon2, p = p)):
      print ('Yes')
    else:
      print ('No')
     
    polygon3 = [ (0, 0), (10, 0), (10, 10), (0, 10) ]
     
    p = (-1, 10)
    if (is_inside_polygon(points = polygon3, p = p)):
      print ('Yes')
    else:
      print ('No')
       
# This code is contributed by Vikas Chitturi

C#

// A C# program to check if a given point
// lies inside a given polygon
// Refer https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
// for explanation of functions onSegment(),
// orientation() and doIntersect()
using System;
 
class GFG
{
 
    // Define Infinite (Using INT_MAX
    // caused overflow problems)
    static int INF = 10000;
 
    class Point
    {
        public int x;
        public int y;
 
        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    };
 
    // Given three collinear points p, q, r,
    // the function checks if point q lies
    // on line segment '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;
    }
 
    // To find orientation of ordered triplet (p, q, r).
    // The function returns following values
    // 0 --> p, q and r are collinear
    // 1 --> Clockwise
    // 2 --> Counterclockwise
    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; // collinear
        }
        return (val > 0) ? 1 : 2; // clock or counterclock wise
    }
 
    // The function that returns true if
    // line segment 'p1q1' and 'p2q2' intersect.
    static bool doIntersect(Point p1, Point q1,
                            Point p2, Point q2)
    {
        // Find the four orientations needed for
        // general and special cases
        int o1 = orientation(p1, q1, p2);
        int o2 = orientation(p1, q1, q2);
        int o3 = orientation(p2, q2, p1);
        int o4 = orientation(p2, q2, q1);
 
        // General case
        if (o1 != o2 && o3 != o4)
        {
            return true;
        }
 
        // Special Cases
        // p1, q1 and p2 are collinear and
        // p2 lies on segment p1q1
        if (o1 == 0 && onSegment(p1, p2, q1))
        {
            return true;
        }
 
        // p1, q1 and p2 are collinear and
        // q2 lies on segment p1q1
        if (o2 == 0 && onSegment(p1, q2, q1))
        {
            return true;
        }
 
        // p2, q2 and p1 are collinear and
        // p1 lies on segment p2q2
        if (o3 == 0 && onSegment(p2, p1, q2))
        {
            return true;
        }
 
        // p2, q2 and q1 are collinear and
        // q1 lies on segment p2q2
        if (o4 == 0 && onSegment(p2, q1, q2))
        {
            return true;
        }
 
        // Doesn't fall in any of the above cases
        return false;
    }
 
    // Returns true if the point p lies
    // inside the polygon[] with n vertices
    static bool isInside(Point []polygon, int n, Point p)
    {
        // There must be at least 3 vertices in polygon[]
        if (n < 3)
        {
            return false;
        }
 
        // Create a point for line segment from p to infinite
        Point extreme = new Point(INF, p.y);
 
        // Count intersections of the above line
        // with sides of polygon
        int count = 0, i = 0;
        do
        {
            int next = (i + 1) % n;
 
            // Check if the line segment from 'p' to
            // 'extreme' intersects with the line
            // segment from 'polygon[i]' to 'polygon[next]'
            if (doIntersect(polygon[i],
                            polygon[next], p, extreme))
            {
                // If the point 'p' is collinear with line
                // segment 'i-next', then check if it lies
                // on segment. If it lies, return true, otherwise false
                if (orientation(polygon[i], p, polygon[next]) == 0)
                {
                    return onSegment(polygon[i], p,
                                    polygon[next]);
                }
                count++;
            }
            i = next;
        } while (i != 0);
 
        // Return true if count is odd, false otherwise
        return (count % 2 == 1); // Same as (count%2 == 1)
    }
 
    // Driver Code
    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");
        }
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// A Javascript program to check if a given point
// lies inside a given polygon
// Refer https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
// for explanation of functions onSegment(),
// orientation() and doIntersect()
 
// Define Infinite (Using INT_MAX
    // caused overflow problems)
let INF = 10000;
 
class Point
{
    constructor(x,y)
    {
        this.x = x;
        this.y = y;
    }
}
 
// Given three collinear points p, q, r,
    // the function checks if point q lies
    // on line segment 'pr'
function onSegment(p,q,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;
}
 
// To find orientation of ordered triplet (p, q, r).
    // The function returns following values
    // 0 --> p, q and r are collinear
    // 1 --> Clockwise
    // 2 --> Counterclockwise
function orientation(p,q,r)
{
    let val = (q.y - p.y) * (r.x - q.x)
                - (q.x - p.x) * (r.y - q.y);
  
        if (val == 0)
        {
            return 0; // collinear
        }
        return (val > 0) ? 1 : 2; // clock or counterclock wise
}
 
// The function that returns true if
    // line segment 'p1q1' and 'p2q2' intersect.
function  doIntersect(p1,q1,p2,q2)
{
    // Find the four orientations needed for
        // general and special cases
        let o1 = orientation(p1, q1, p2);
        let o2 = orientation(p1, q1, q2);
        let o3 = orientation(p2, q2, p1);
        let o4 = orientation(p2, q2, q1);
  
        // General case
        if (o1 != o2 && o3 != o4)
        {
            return true;
        }
  
        // Special Cases
        // p1, q1 and p2 are collinear and
        // p2 lies on segment p1q1
        if (o1 == 0 && onSegment(p1, p2, q1))
        {
            return true;
        }
  
        // p1, q1 and p2 are collinear and
        // q2 lies on segment p1q1
        if (o2 == 0 && onSegment(p1, q2, q1))
        {
            return true;
        }
  
        // p2, q2 and p1 are collinear and
        // p1 lies on segment p2q2
        if (o3 == 0 && onSegment(p2, p1, q2))
        {
            return true;
        }
  
        // p2, q2 and q1 are collinear and
        // q1 lies on segment p2q2
        if (o4 == 0 && onSegment(p2, q1, q2))
        {
            return true;
        }
  
        // Doesn't fall in any of the above cases
        return false;
}
 
// Returns true if the point p lies
    // inside the polygon[] with n vertices
function  isInside(polygon,n,p)
{
    // There must be at least 3 vertices in polygon[]
        if (n < 3)
        {
            return false;
        }
  
        // Create a point for line segment from p to infinite
        let extreme = new Point(INF, p.y);
  
        // Count intersections of the above line
        // with sides of polygon
        let count = 0, i = 0;
        do
        {
            let next = (i + 1) % n;
  
            // Check if the line segment from 'p' to
            // 'extreme' intersects with the line
            // segment from 'polygon[i]' to 'polygon[next]'
            if (doIntersect(polygon[i], polygon[next], p, extreme))
            {
                // If the point 'p' is collinear with line
                // segment 'i-next', then check if it lies
                // on segment. If it lies, return true, otherwise false
                if (orientation(polygon[i], p, polygon[next]) == 0)
                {
                    return onSegment(polygon[i], p,
                                    polygon[next]);
                }
  
                count++;
            }
            i = next;
        } while (i != 0);
  
        // Return true if count is odd, false otherwise
        return (count % 2 == 1); // Same as (count%2 == 1)
}
 
// Driver Code
polygon1 = [new Point(0, 0),
                            new Point(10, 0),
                            new Point(10, 10),
                            new Point(0, 10)];
                             
let n = polygon1.length;
        let p = new Point(20, 20);
        if (isInside(polygon1, n, p))
        {
            document.write("Yes<br>");
        }
        else
        {
            document.write("No<br>");
        }
        p = new Point(5, 5);
        if (isInside(polygon1, n, p))
        {
            document.write("Yes<br>");
        }
        else
        {
            document.write("No<br>");
        }
        let 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))
        {
            document.write("Yes<br>");
        }
        else
        {
            document.write("No<br>");
        }
        p = new Point(5, 1);
        if (isInside(polygon2, n, p))
        {
            document.write("Yes<br>");
        }
        else
        {
            document.write("No<br>");
        }
        p = new Point(8, 1);
        if (isInside(polygon2, n, p))
        {
            document.write("Yes<br>");
        }
        else
        {
            document.write("No<br>");
        }
        let 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))
        {
            document.write("Yes<br>");
        }
        else
        {
            document.write("No<br>");
        }                           
 
// This code is contributed by rag2127
</script>
Producción

No 
Yes 
Yes 
Yes 
No 
No 

Complejidad de tiempo: O(n) donde n es el número de vértices en el polígono dado.
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.

Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *