Check If a Point Lies In The Interior of a Polygon

Problem Explanation

The problem of checking if a point lies within the interior of a polygon is a fundamental problem in computational geometry with various applications in computer graphics, geographic information systems, and robotics. The goal is to determine if a given point is surrounded by the polygon. Here we will understand this through simple programing language.

Example

Input: 

Point polygon1[ ] = {{0, 0}, {7, 7}, {7, 0}}; (vertices of the polygon and a point)

Point p = {5, 4};

Output: 

yes(interior or not).

Approach

Here the approach to check if a point lies in the interior of a polygon is the Ray Casting Method. 

Ray Casting Method

This method draws an infinite ray toward the right from the point. The number of times the ray intersects with the polygon's sides is counted. The point is inside the polygon if the number of intersections is odd. If the number of intersections is even, then the point is outside the polygon.

1. Ray A cuts the polygon at 4 points, so it is even and outside of the polygon.
2. Ray B cuts the polygon at 1 point, so it is odd and inside of the polygon. 
3. Ray C cuts the polygon at 1 point, so it is odd and inside of the polygon. 
4. Ray D cuts the polygon at 2 points so it is even and outside of the polygon.

Explanation

Suppose you have a polygon that's defined by the vertices (0, 0), (4, 0), (4, 4), and (0, 4). To check if point (3, 3) lies in the interior of this polygon, you can use the following approach:

Draw a line from point (3, 3) to the point outside the polygon. For example, a point far away from the polygon (we may take infinity also or some outside point), say (10, 10). In this example, the line from point (3, 3) to (10, 10) intersects with the edges of the polygon once. Since the number of intersections is odd, the point (3, 3) is inside the polygon.

Algorithm

The algorithm works as follows:

Initialize variables: The function first initialises variables for the number of vertices in the polygon, the x-coordinate and y-coordinate of the test point, and a boolean flag indicating whether the point is inside the polygon.
 

   int num_vertices = polygon.size();
   double x = point.x, y = point.y;
   bool inside = false;

Loop through each edge in the polygon: It loop through each edge to check whether the test point lies inside or outside the polygon.
 

   // Store the first point in the polygon and initialize the second point
   Point p1 = polygon[0], p2;
 
   // Loop through each edge in the polygon
   for (int i = 1; i <= num_vertices; i++) {
     
       // Get the next point in the polygon
       p2 = polygon[i % num_vertices];

Check if the point is above the minimum y-coordinate of the edge: Here it checks whether the test point is above the minimum y-coordinate of the edge. This is necessary because if the test point is below the minimum y-coordinate of the edge, it cannot intersect the edge and hence cannot lie inside the polygon.
 

       // Check if the point is above the minimum y coordinate of the edge
       if (y > min(p1.y, p2.y)) 

If the point is not above or below the edge, we need to check whether it's to the left or right of the edge. We calculate the x-coordinate of the intersection point between the line containing the edge and the horizontal line passing through the point. This can be done using the equation of the line:
 

x_intersection = (y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x

where y is the y-coordinate of the point we're testing, p1 and p2 are the endpoints of the edge, and x_intersection is the x-coordinate of the intersection point.

Finally, we update the value of the inside variable by flipping its value. We do this each time we encounter an edge that crosses the horizontal line passing through the point. This is because each crossing indicates that the point is either entering or exiting the polygon, so we need to update our inside/outside status accordingly.

After looping through all the edges of the polygon, we return the final value of the inside variable. If it is true, the point is inside the polygon; otherwise, it is outside.

Click here to know more about Introduction to C#

Dry Run

Below is an example of a dry run of the point in the polygon algorithm:

• Consider a polygon with vertices at points (0,0), (4,0), (4,4), and (0,4).

• Let's take a point P with coordinates (3,3).

• Now draw a point straight right side from point (3,3).
   
• It will intersect only at (4,3).

• So the total number of intersecting is one, which is odd. So the point lies inside the polygon.

Code

C++ Implementation

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Point {
   double x, y;
};

// Checking if a point is inside a polygon
bool point_in_polygon(Point point, vector<Point> polygon) {
  
   int num_vertices = polygon.size();
  
   double x = point.x, y = point.y;
  
   bool inside = false;
  
   // Store the first point in the polygon and initialize the second point
   Point p1 = polygon[0], p2;
  
   // Loop through each edge in the polygon
   for (int i = 1; i <= num_vertices; i++) {
      
       // Get the next point in the polygon
       p2 = polygon[i % num_vertices];
      
       // Check if the point is above the minimum y coordinate of the edge
       if (y > min(p1.y, p2.y)) {
          
           // Check if the point is below the maximum y coordinate of the edge
           if (y <= max(p1.y, p2.y)) {
              
               // Check if the point is to the left of the maximum x coordinate of the edge
               if (x <= max(p1.x, p2.x)) {
                  
                   /*
                        Calculate the x-intersection of the line connecting the point to the edge
                   */
                   double x_intersection = (y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
                  
                   // Check if the point is on the same line as the edge or to the left of the x-intersection
                   if (p1.x == p2.x || x <= x_intersection) {
                     
                       // Flip the inside flag
                       inside = !inside;
                   }
               }
           }
       }
      
       // Store the current point as the first point for the next iteration
       p1 = p2;
   }
  
   // Return the value of the inside flag
   return inside;
}

int main() {
  
   // Define a point to test
   Point point = {3, 3};
  
   // Define a polygon
   vector<Point> polygon = {{0, 0}, {4, 0}, {4, 4}, {0, 4}};
  
   if (point_in_polygon(point, polygon)) {
       cout << "Point is inside the polygon" << endl;
   } else {
       cout << "Point is outside the polygon" << endl;
   }
   return 0;
}

Output

Java Implementation

import java.util.ArrayList;
import java.util.List;

// Class to represent a point in 2D space
class Point {
   double x, y;

   // Constructor to initialize the x and y values of a point
   public Point(double x, double y) {
       this.x = x;
       this.y = y;
   }
}

class Solution {
  
   // Checking if a point lies inside a polygon
   public static boolean pointInPolygon(Point point, List<Point> polygon) {
      
       // Total number of vertices in the polygon
       int numVertices = polygon.size();
      
       // X and Y coordinates of the point
       double x = point.x, y = point.y;
      
       // Flag to store if the point is inside the polygon or not
       boolean inside = false;
      
       // First vertex of the polygon
       Point p1 = polygon.get(0);
      
       // Loop through each vertex in the polygon
       for (int i = 1; i <= numVertices; i++) {
           Point p2 = polygon.get(i % numVertices); // Current vertex
          
           // Check if the point is below the lower edge of the polygon
           if (y > Math.min(p1.y, p2.y)) {
              
               // Check if the point is above the upper edge of the polygon
               if (y <= Math.max(p1.y, p2.y)) {
                  
                   // Check if the point is on the left of the polygon
                   if (x <= Math.max(p1.x, p2.x)) {
                      
                       /*
                       Calculate the intersection of the line passing through
                       the two vertices and the horizontal line passing through the point
                       */
                       double xIntersection = (y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
                      
                       // Check if the line passes through the point or if the two vertices are at the same x-coordinate
                       if (p1.x == p2.x || x <= xIntersection) {
                          
                           // Flip the inside flag
                           inside = !inside;
                       }
                   }
               }
           }
          
           // Set the current vertex as the previous vertex for the next iteration
           p1 = p2;
       }
      
       // Return the inside flag as the result
       return inside;
   }

   public static void main(String[] args) {
       Point point = new Point(3, 3);
      
       // Create a polygon as a list of points
       List<Point> polygon = new ArrayList<Point>();
       polygon.add(new Point(0, 0));
       polygon.add(new Point(4, 0));
       polygon.add(new Point(4, 4));
       polygon.add(new Point(0, 4));
      
       // Check if the point lies inside the polygon
       if (pointInPolygon(point, polygon)) {
           System.out.println("Point is inside the polygon");
       } else {
           System.out.println("Point is outside the polygon");
       }
   }
}

Output

Complexity

Time Complexity 

O(n), where n is the number of vertices in the polygon. 

Reason: This complexity is because the algorithm loops through each edge in the polygon and performs constant operations for each edge.

In each iteration, the algorithm performs a few simple calculations, such as determining the minimum and maximum y-coordinates of the edge and calculating the x-intersection of the line connecting the point to the edge. These operations are constant time, so the total time complexity of the algorithm is proportional to the number of vertices in the polygon.

Space Complexity

O(n), where n is the number of vertices in the polygon.

Reason: This is because the algorithm requires storing each vertex's x and y coordinates in the polygon, which takes up a total of O(n) space. 

Frequently Asked Questions 

How do I represent a polygon in code?

You need to represent the polygon as a set of points in code. One way to do this is to store the coordinates of each vertex in an array or list.

What is the Ray Casting algorithm?

The Ray Casting algorithm is a method for finding whether a point is outside or inside a polygon. The algorithm works by drawing a ray from the point to be tested in any direction and counting the number of times the ray intersects with the edges of the polygon. For the odd number of intersections, the point is inside the polygon, if it is even, it is outside the polygon.

What if the polygon is self-intersecting?

If the polygon is self-intersecting, the algorithm may not work correctly. In this case, you may need to preprocess the polygon to split it into non-intersecting parts or use a different algorithm that can handle self-intersecting polygons.

Can the algorithm handle non-convex polygons?

Yes, the algorithm can handle non-convex polygons if the polygon edges do not intersect. If the polygon is self-intersecting, the algorithm may not work correctly.

What if the point lies on the boundary of the polygon?

If the point lies precisely on the boundary of the polygon, it is not considered to be inside the polygon. To include points on the boundary, you can modify the algorithm to check for "touching" instead of "intersections".

Conclusion

This article covered the method of checking if a point lies in the interior point of a polygon. We have gone through the approach, algorithm and dry run. We also covered the Ray Casting algorithm.

Below are more links related to the DSA topic that will help you to build your skill:

• Car Pooling
   
• Bucket Sort
   
• Check if a number is not a power of 2
   

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning