geometry

# # Usage

This algorithm is to determine if a given point is in a given polygon, on the polygon or outside of the polygon.

# # Algorithm

Let the polygon $P$, point $p$, a edge of the polygon $e$.
Let vectors from $p$ to vertices of $e$ $\vec{a}$, $\vec{b}$ (a.y < b.y).

## # A point is on a polygon

$p$ is on $P$ when the predicate below is true.

$\exists e \{e \in P, \vec{a} \times \vec{b} = 0, \vec{a} \cdot \vec{b} < 0\}$

$p$ is in $P$ when the predicate below is true.

$|\{e|e \in P, a.y \leq 0, b.y \geq 0, \vec{a} \times \vec{b}\}| \equiv 1 (\mod 2)$

# # Code

N-polygon

Spec of return value.

• 2: in
• 1: on
• 0: outside
Int contains(Vector2 polygon[], int N, Vector2 &point) {
bool in = false;
loop(n,0,N) {
Vector2 a = polygon[n] - point;
Vector2 b = polygon[(n+1) % N] - point;
if (fabs(a.cross(b)) < EPS && a.dot(b) < EPS) return 1;
if (a.y > b.y) swap(a, b);
if (a.y < EPS && b.y > EPS && a.cross(b) > EPS) in = !in;
}

return in ? 2 : 0;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!