How to check if a given point lies inside or outside a polygon? | GeeksforGeeks


How to check if a given point lies inside or outside a polygon? | GeeksforGeeks
Given a polygon and a point ‘p’, find if ‘p’ lies inside the polygon or not. The points lying on the border are considered inside.
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
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.
// 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};
    // 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 colinear 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&1;  // Same as (count%2 == 1)
}
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 colinear
// 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;  // colinear
    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 colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
     // p2, q2 and q1 are colinear 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
}
http://zheng12tian.iteye.com/blog/1922112
  1.     public static boolean isPointInPolygon(BmapPoint point, BmapPoint[] boundaryPoints) {  
  2.         // 防止第一个点与最后一个点相同  
  3.         if (boundaryPoints != null && boundaryPoints.length > 0  
  4.                 && boundaryPoints[boundaryPoints.length - 1].equals(boundaryPoints[0])) {  
  5.             boundaryPoints = Arrays.copyOf(boundaryPoints, boundaryPoints.length - 1);  
  6.         }  
  7.         int pointCount = boundaryPoints.length;  
  8.   
  9.         // 首先判断点是否在多边形的外包矩形内,如果在,则进一步判断,否则返回false  
  10.         if (!isPointInRectangle(point, boundaryPoints)) {  
  11.             return false;  
  12.         }  
  13.   
  14.         // 如果点与多边形的其中一个顶点重合,那么直接返回true  
  15.         for (int i = 0; i < pointCount; i++) {  
  16.             if (point.equals(boundaryPoints[i])) {  
  17.                 return true;  
  18.             }  
  19.         }  
  20.   
  21.         /** 
  22.          * 基本思想是利用X轴射线法,计算射线与多边形各边的交点,如果是偶数,则点在多边形外,否则在多边形内。还会考虑一些特殊情况,如点在多边形顶点上 
  23.          * , 点在多边形边上等特殊情况。 
  24.          */  
  25.         // X轴射线与多边形的交点数  
  26.         int intersectPointCount = 0;  
  27.         // X轴射线与多边形的交点权值  
  28.         float intersectPointWeights = 0;  
  29.         // 浮点类型计算时候与0比较时候的容差  
  30.         double precision = 2e-10;  
  31.         // 边P1P2的两个端点  
  32.         BmapPoint point1 = boundaryPoints[0], point2;  
  33.         // 循环判断所有的边  
  34.         for (int i = 1; i <= pointCount; i++) {  
  35.             point2 = boundaryPoints[i % pointCount];  
  36.   
  37.             /** 
  38.              * 如果点的y坐标在边P1P2的y坐标开区间范围之外,那么不相交。 
  39.              */  
  40.             if (point.getLat() < Math.min(point1.getLat(), point2.getLat())  
  41.                     || point.getLat() > Math.max(point1.getLat(), point2.getLat())) {  
  42.                 point1 = point2;  
  43.                 continue;  
  44.             }  
  45.   
  46.             /** 
  47.              * 此处判断射线与边相交 
  48.              */  
  49.             if (point.getLat() > Math.min(point1.getLat(), point2.getLat())  
  50.                     && point.getLat() < Math.max(point1.getLat(), point2.getLat())) {// 如果点的y坐标在边P1P2的y坐标开区间内  
  51.                 if (point1.getLng() == point2.getLng()) {// 若边P1P2是垂直的  
  52.                     if (point.getLng() == point1.getLng()) {  
  53.                         // 若点在垂直的边P1P2上,则点在多边形内  
  54.                         return true;  
  55.                     } else if (point.getLng() < point1.getLng()) {  
  56.                         // 若点在在垂直的边P1P2左边,则点与该边必然有交点  
  57.                         ++intersectPointCount;  
  58.                     }  
  59.                 } else {// 若边P1P2是斜线  
  60.                     if (point.getLng() <= Math.min(point1.getLng(), point2.getLng())) {// 点point的x坐标在点P1和P2的左侧  
  61.                         ++intersectPointCount;  
  62.                     } else if (point.getLng() > Math.min(point1.getLng(), point2.getLng())  
  63.                             && point.getLng() < Math.max(point1.getLng(), point2.getLng())) {// 点point的x坐标在点P1和P2的x坐标中间  
  64.                         double slopeDiff = 0.0d;  
  65.                         if (point1.getLat() > point2.getLat()) {  
  66.                             slopeDiff = (point.getLat() - point2.getLat()) / (point.getLng() - point2.getLng())  
  67.                                     - (point1.getLat() - point2.getLat()) / (point1.getLng() - point2.getLng());  
  68.                         } else {  
  69.                             slopeDiff = (point.getLat() - point1.getLat()) / (point.getLng() - point1.getLng())  
  70.                                     - (point2.getLat() - point1.getLat()) / (point2.getLng() - point1.getLng());  
  71.                         }  
  72.                         if (slopeDiff > 0) {  
  73.                             if (slopeDiff < precision) {// 由于double精度在计算时会有损失,故匹配一定的容差。经试验,坐标经度可以达到0.0001  
  74.                                 // 点在斜线P1P2上  
  75.                                 return true;  
  76.                             } else {  
  77.                                 // 点与斜线P1P2有交点  
  78.                                 intersectPointCount++;  
  79.                             }  
  80.                         }  
  81.                     }  
  82.                 }  
  83.             } else {  
  84.                 // 边P1P2水平  
  85.                 if (point1.getLat() == point2.getLat()) {  
  86.                     if (point.getLng() <= Math.max(point1.getLng(), point2.getLng())  
  87.                             && point.getLng() >= Math.min(point1.getLng(), point2.getLng())) {  
  88.                         // 若点在水平的边P1P2上,则点在多边形内  
  89.                         return true;  
  90.                     }  
  91.                 }  
  92.                 /** 
  93.                  * 判断点通过多边形顶点 
  94.                  */  
  95.                 if (((point.getLat() == point1.getLat() && point.getLng() < point1.getLng()))  
  96.                         || (point.getLat() == point2.getLat() && point.getLng() < point2.getLng())) {  
  97.                     if (point2.getLat() < point1.getLat()) {  
  98.                         intersectPointWeights += -0.5;  
  99.                     } else if (point2.getLat() > point1.getLat()) {  
  100.                         intersectPointWeights += 0.5;  
  101.                     }  
  102.                 }  
  103.             }  
  104.             point1 = point2;  
  105.         }  
  106.   
  107.         if ((intersectPointCount + Math.abs(intersectPointWeights)) % 2 == 0) {// 偶数在多边形外  
  108.             return false;  
  109.         } else { // 奇数在多边形内  
  110.             return true;  
  111.         }  
  112.     }  
Read full article from How to check if a given point lies inside or outside a polygon? | GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts