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.
//This is a java program to check whether a point lies in a polygon or not class Point { int x, y; Point() {} Point(int p, int q) { x = p; y = q; } } public class Position_Point_WRT_Polygon { public 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; } 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; } public 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; if (o1 == 0 && onSegment(p1, p2, q1)) return true; if (o2 == 0 && onSegment(p1, q2, q1)) return true; if (o3 == 0 && onSegment(p2, p1, q2)) return true; if (o4 == 0 && onSegment(p2, q1, q2)) return true; return false; } public static boolean isInside(Point polygon[], int n, Point p) { int INF = 10000; if (n < 3) return false; Point extreme = new Point(INF, p.y); int count = 0, i = 0; do { int next = (i + 1) % n; if (doIntersect(polygon[i], polygon[next], p, extreme)) { if (orientation(polygon[i], p, polygon[next]) == 0) return onSegment(polygon[i], p, polygon[next]); count++; } i = next; } while (i != 0); return (count & 1) == 1 ? true : false; } 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 = 4; Point p = new Point(20, 20); System.out.println("Point P(" + p.x + ", " + p.y + ") lies inside polygon1: " + isInside(polygon1, n, p)); p = new Point(5, 5); System.out.println("Point P(" + p.x + ", " + p.y + ") lies inside polygon1: " + isInside(polygon1, n, p)); Point polygon2[] = { new Point(0, 0), new Point(5, 5), new Point(5, 0) }; n = 3; p = new Point(3, 3); System.out.println("Point P(" + p.x + ", " + p.y + ") lies inside polygon2: " + isInside(polygon2, n, p)); p = new Point(5, 1); System.out.println("Point P(" + p.x + ", " + p.y + ") lies inside polygon2: " + isInside(polygon2, n, p)); p = new Point(8, 1); System.out.println("Point P(" + p.x + ", " + p.y + ") lies inside polygon2: " + isInside(polygon2, n, p)); Point polygon3[] = { new Point(0, 0), new Point(10, 0), new Point(10, 10), new Point(0, 10), new Point(5, 5) }; n = 5; p = new Point(-1, 10); System.out.println("Point P(" + p.x + ", " + p.y + ") lies inside polygon3: " + isInside(polygon3, n, p)); } }
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
Related posts:
Giới thiệu về Stream API trong Java 8
A Guide to Java SynchronousQueue
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Phương thức tham chiếu trong Java 8 – Method References
Adding a Newline Character to a String in Java
Java Program to Find MST (Minimum Spanning Tree) using Kruskal’s Algorithm
Initialize a HashMap in Java
Spring Boot - Tomcat Deployment
Java Program to Implement Hash Tables with Linear Probing
Case-Insensitive String Matching in Java
Hướng dẫn Java Design Pattern – Decorator
Working with Network Interfaces in Java
Câu lệnh điều khiển vòng lặp trong Java (break, continue)
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Java Program to Find the Median of two Sorted Arrays using Binary Search Approach
Java Program to Implement VList
Java Program to Implement Self organizing List
Debug a JavaMail Program
Java Program to Implement Gaussian Elimination Algorithm
Java Program to Generate Randomized Sequence of Given Range of Numbers
Java Program to Implement Meldable Heap
Java Program to Implement Fermat Factorization Algorithm
Spring Security – security none, filters none, access permitAll
Date Time trong Java 8
Spring @RequestMapping New Shortcut Annotations
Sử dụng CyclicBarrier trong Java
How to Read HTTP Headers in Spring REST Controllers
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Marker Interface trong Java
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS
Java – Write an InputStream to a File
Control the Session with Spring Security