Convex Polygons

Convexity means every segment joining two points of a region stays inside it. This removes indentations and gives an ordered fan of triangles from a chosen vertex. After checking a promised simple polygon for strict convexity and normalizing it counterclockwise, the program answers point queries by binary search. It intentionally rejects flat consecutive turns to keep the fan invariant easy to see.

Prerequisites: Orientation; Point in Polygon; binary search.

Build the idea

1. Recognize consistent turns

   Walk consecutive triples around a simple polygon. Strict convexity requires every determinant to be nonzero and all signs equal. A clockwise polygon passes with negative turns and is reversed. Zero turns mean boundary-collinear vertices, while mixed signs identify concavity. The simplicity promise matters: consistent local turn signs alone are not a full test for arbitrary self-crossing input chains.

2. Understand convex combinations

   A point tA+(1−t)B with 0≤t≤1 lies between A and B. A convex region is closed under this operation. Connecting p[0] to the other vertices splits a counterclockwise strict convex polygon into nonoverlapping fan triangles. Their radial directions are ordered, letting orientation replace angle computation.

   $$\mathrm{cross}\left(p\right[0],p[\mathrm{lo}],Q)\ge 0$$

3. Reject outside the outer wedge

   A query must be on or left of p[0]→p[1] and on or right of p[0]→p[n−1]. If it lies on either ray, test the actual edge segment because a point farther along the ray can still be outside. These two boundary edges are special cases before searching the interior fan.

4. Binary-search the containing sector

   Find adjacent indices lo,hi with the query direction between p[lo]−p[0] and p[hi]−p[0]. Each orientation with a middle ray discards half the possible sectors. Finally test the outer triangle edge p[lo]→p[hi]: right means outside, zero means polygon boundary, left means inside. Internal fan diagonals are not polygon boundary and must not be mislabeled.

5. Follow the rectangle example

   In a counterclockwise square, (2,2) is inside even though it lies on a fan diagonal. (4,2) is on a true outer edge and (5,2) lies beyond it. The initial turn scan costs linear time once; each subsequent query uses only two wedge tests and logarithmically many fan tests. No trigonometry or approximate angles appear.

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>&p,Point q){
    int n=p.size();
    long long first=cross(p[0],p[1],q),last=cross(p[0],p[n-1],q);
    if(first<0||last>0){
        return "OUTSIDE";
    }
    if(first==0){
        return on(q,p[0],p[1])?"BOUNDARY":"OUTSIDE";
    }
    if(last==0){
        return on(q,p[0],p[n-1])?"BOUNDARY":"OUTSIDE";
    }
    // Locate the fan sector from vertex zero; internal diagonals are not boundary.
    int lo=1,hi=n-1;
    while(hi-lo>1){
        int mid=(lo+hi)/2;
        if(cross(p[0],p[mid],q)>=0){
            lo=mid;
        }
        else{
            hi=mid;
        }
    }
    long long turn=cross(p[lo],p[hi],q);
    return turn<0?"OUTSIDE":turn==0?"BOUNDARY":"INSIDE";
}
int main(){
    int n,q;
    std::cin>>n>>q;
    std::vector<Point>p(n);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    // Contract: a simple polygon with distinct vertices; do not repeat the first vertex.
    int direction=0;
    bool strict=n>=3;
    for(int i=0;i<n;++i){
        long long t=cross(p[i],p[(i+1)%n],p[(i+2)%n]);
        if(t==0){
            strict=false;
        }
        else{
            int s=t>0?1:-1;
            if(direction&&s!=direction){
                strict=false;
            }
            direction=s;
        }
    }
    if(!strict){
        std::cout<<"NOT STRICTLY CONVEX\n";
        return 0;
    }
    if(direction<0){
        std::reverse(p.begin(),p.end());
    }
    std::cout<<"STRICTLY CONVEX\n";
    while(q--){
        Point a;
        std::cin>>a.x>>a.y;
        std::cout<<locate(p,a)<<'\n';
    }
}

Complexity analysis

O(n) preprocessing for the turn check and possible reversal. O(log n) per query, O(n) stored vertices and O(1) extra query space. Total O(n+q log n).

Example input and output

Read n q, then a simple polygon with distinct integer vertices and no repeated closing point, then q queries. 3≤n≤100000; coordinates within ±10^6. Print NOT STRICTLY CONVEX and stop for flat/mixed turns; otherwise print STRICTLY CONVEX and classifications.

Input

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

Output

STRICTLY CONVEX
INSIDE
BOUNDARY
OUTSIDE

Consistent positive turns establish strict convexity under the simplicity promise. The three points exercise diagonal, edge and exterior cases.

Practical applications

Use for many membership queries in a convex obstacle or hull. Ray casting supports general simple polygons in O(n) per query. Convexity also enables rotating calipers and linear-time Minkowski sums.

Check your understanding

Is an internal fan diagonal part of the polygon boundary?

Put it into practice

Test the same polygon clockwise and with one extra collinear vertex.