Point in Polygon

Point-in-polygon queries classify a point as INSIDE, OUTSIDE or BOUNDARY. Boundary deserves its own result: a point on a fence is not merely a numerical inconvenience. Ray casting counts intersections with a ray from the query point, while careful endpoint rules avoid counting a polygon vertex twice. This program uses integer orientations and never computes a floating intersection coordinate.

Prerequisites: Segment Intersection; Polygon Representation.

Build the idea

1. Check the boundary first

   For each edge AB, test cross(A,B,P)==0 together with coordinate ranges. If true, immediately return BOUNDARY. This handles vertices, horizontal edges and points on a slanted edge. Only after excluding boundary can the parity test safely use strict sign decisions. The polygon is simple, may be concave, and can have either orientation.

2. Use parity of crossings

   Cast a ray horizontally rightward from P. Starting far outside the polygon, crossing a boundary edge switches between interior and exterior, so an odd crossing count means inside. Instead of storing the count, toggle a boolean. Winding number is related but tracks signed upward/downward crossings; for simple polygons either nonzero winding or odd parity identifies the interior.

   $$\mathrm{cross}(A,B,P)/(\mathrm{By}-\mathrm{Ay})=\mathrm{crossingX}-\mathrm{Px}$$

3. Avoid double-counting vertices

   An edge is a crossing candidate only if (Ay>Py)!=(By>Py). This half-open vertical interval counts one of two incident edges at a regular vertex and gives no spurious toggle at a tangency. Horizontal edges have both comparisons equal and never enter the crossing branch; boundary detection already handled points lying on them.

4. Locate the crossing without division

   For a candidate edge, cross(A,B,P)/(By−Ay) has the sign of the crossing’s x-coordinate minus Px. Thus the crossing is to the right exactly when the cross sign agrees with the vertical direction. The code compares those signs instead of dividing, preserving exactness for the bounded integers. Reversing an edge reverses both signs, leaving the decision unchanged.

5. Trace three classifications

   In the rectangle (0,0),(4,0),(4,3),(0,3), P=(2,1) sees one rightward crossing and is inside. P=(4,2) lies on the right edge and returns BOUNDARY before parity. P=(5,1) has no rightward crossing and is outside. The same procedure also works in an indentation where a horizontal ray crosses several times.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
struct Point{
    long long x,y;
};
long long cross(Point a,Point b,Point c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool on(Point p,Point a,Point b){
    return cross(a,b,p)==0&&std::min(a.x,b.x)<=p.x&&p.x<=std::max(a.x,b.x)&&
        std::min(a.y,b.y)<=p.y&&p.y<=std::max(a.y,b.y);
}
const char*locate(const std::vector<Point>&poly,Point p){
    bool inside=false;
    int n=poly.size();
    for(int i=0;i<n;++i){
        Point a=poly[i],b=poly[(i+1)%n];
        if(on(p,a,b)){
            return "BOUNDARY";
        }
        if((a.y>p.y)!=(b.y>p.y)){
            long long turn=cross(a,b,p);
            // cross/(b.y-a.y) is positive precisely when crossing is to the right.
            if((turn>0)==(b.y>a.y)){
                inside=!inside;
            }
        }
    }
    return inside?"INSIDE":"OUTSIDE";
}
int main(){
    int n,q;
    std::cin>>n>>q;
    std::vector<Point>p(n);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    while(q--){
        Point a;
        std::cin>>a.x>>a.y;
        std::cout<<locate(p,a)<<'\n';
    }
}

Complexity analysis

O(n) preprocessing to read vertices, O(n) time per query and O(n) stored vertices; O(1) extra query state. Total O(n+nq). Cross products fit long long under the joint vertex/query bound.

Example input and output

Read n q, then n vertices of a simple polygon and q query pairs. 3≤n≤100000, q≥0; all coordinates, including queries, are integers within ±10^6. Print one classification per query.

Input

4 3
0 0
4 0
4 3
0 3
2 1
4 2
5 1

Output

INSIDE
BOUNDARY
OUTSIDE

The three queries are respectively within the rectangle, on its right side, and strictly to its right.

Practical applications

Use for membership in arbitrary simple regions and polygon queries with moderate n·q. For many queries on a convex polygon, the fan binary-search method reduces each to O(log n). General point location structures are more involved.

Check your understanding

Why use a half-open y-range for ray crossings?

Put it into practice

Query rectangle vertices, horizontal-edge midpoints and a concave notch.