Java Program to Check if Point is Inside Polygon

This is a Java Program to check whether a point lies inside, outside or on the Polygon. Following is a simple idea to check whether a point is inside or outside.
1) Draw a horizontal line to the right of each point and extend it to infinity
2) Count the number of times the line intersects with polygon edges.
3) 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.

Here is the source code of the Java Program to Check Whether a Given Point is in a Given Polygon. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to check whether a point lies in a polygon or not
  2. class Point
  3. {
  4.     int x, y;
  5.  
  6.     Point()
  7.     {}
  8.  
  9.     Point(int p, int q)
  10.     {
  11.         x = p;
  12.         y = q;
  13.     }
  14. }
  15.  
  16. public class Position_Point_WRT_Polygon
  17. {
  18.  
  19.     public static boolean onSegment(Point p, Point q, Point r)
  20.     {
  21.         if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x)
  22.                 && q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y))
  23.             return true;
  24.         return false;
  25.     }
  26.  
  27.     public static int orientation(Point p, Point q, Point r)
  28.     {
  29.         int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  30.  
  31.         if (val == 0)
  32.             return 0;
  33.         return (val > 0) ? 1 : 2;
  34.     }
  35.  
  36.     public static boolean doIntersect(Point p1, Point q1, Point p2, Point q2)
  37.     {
  38.  
  39.         int o1 = orientation(p1, q1, p2);
  40.         int o2 = orientation(p1, q1, q2);
  41.         int o3 = orientation(p2, q2, p1);
  42.         int o4 = orientation(p2, q2, q1);
  43.  
  44.         if (o1 != o2 && o3 != o4)
  45.             return true;
  46.  
  47.         if (o1 == 0 && onSegment(p1, p2, q1))
  48.             return true;
  49.  
  50.         if (o2 == 0 && onSegment(p1, q2, q1))
  51.             return true;
  52.  
  53.         if (o3 == 0 && onSegment(p2, p1, q2))
  54.             return true;
  55.  
  56.         if (o4 == 0 && onSegment(p2, q1, q2))
  57.             return true;
  58.  
  59.         return false;
  60.     }
  61.  
  62.     public static boolean isInside(Point polygon[], int n, Point p)
  63.     {
  64.         int INF = 10000;
  65.         if (n < 3)
  66.             return false;
  67.  
  68.         Point extreme = new Point(INF, p.y);
  69.  
  70.         int count = 0, i = 0;
  71.         do
  72.         {
  73.             int next = (i + 1) % n;
  74.             if (doIntersect(polygon[i], polygon[next], p, extreme))
  75.             {
  76.                 if (orientation(polygon[i], p, polygon[next]) == 0)
  77.                     return onSegment(polygon[i], p, polygon[next]);
  78.  
  79.                 count++;
  80.             }
  81.             i = next;
  82.         } while (i != 0);
  83.  
  84.         return (count & 1) == 1 ? true : false;
  85.     }
  86.  
  87.     public static void main(String args[])
  88.     {
  89.         Point polygon1[] = { new Point(0, 0), new Point(10, 0),
  90.                 new Point(10, 10), new Point(0, 10) };
  91.         int n = 4;
  92.  
  93.         Point p = new Point(20, 20);
  94.         System.out.println("Point P(" + p.x + ", " + p.y
  95.                 + ") lies inside polygon1: " + isInside(polygon1, n, p));
  96.         p = new Point(5, 5);
  97.         System.out.println("Point P(" + p.x + ", " + p.y
  98.                 + ") lies inside polygon1: " + isInside(polygon1, n, p));
  99.  
  100.         Point polygon2[] = { new Point(0, 0), new Point(5, 5), new Point(5, 0) };
  101.         n = 3;
  102.  
  103.         p = new Point(3, 3);
  104.         System.out.println("Point P(" + p.x + ", " + p.y
  105.                 + ") lies inside polygon2: " + isInside(polygon2, n, p));
  106.         p = new Point(5, 1);
  107.         System.out.println("Point P(" + p.x + ", " + p.y
  108.                 + ") lies inside polygon2: " + isInside(polygon2, n, p));
  109.         p = new Point(8, 1);
  110.         System.out.println("Point P(" + p.x + ", " + p.y
  111.                 + ") lies inside polygon2: " + isInside(polygon2, n, p));
  112.  
  113.         Point polygon3[] = { new Point(0, 0), new Point(10, 0),
  114.                 new Point(10, 10), new Point(0, 10), new Point(5, 5) };
  115.         n = 5;
  116.  
  117.         p = new Point(-1, 10);
  118.         System.out.println("Point P(" + p.x + ", " + p.y
  119.                 + ") lies inside polygon3: " + isInside(polygon3, n, p));
  120.     }
  121. }

Output:

$ javac Position_Point_WRT_Polygon.java
$ java Position_Point_WRT_Polygon
 
Point P(20, 20) lies inside polygon1: false
Point P(5, 5) lies inside polygon1: true
Point P(3, 3) lies inside polygon2: true
Point P(5, 1) lies inside polygon2: true
Point P(8, 1) lies inside polygon2: false
Point P(-1, 10) lies inside polygon3: false

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.