# 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

C++

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define EPS 0.0000000001
#define fequals(a,b) (fabs((a) - (b)) < EPS)

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (const Vector2 v) const { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (const Vector2 v) const { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (const double k) const { return Vector2(x * k, y * k); }
  Vector2 operator / (const double k) const { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 const v) { return x * v.x + y * v.y; }
  double cross (Vector2 const v) { return x * v.y - y * v.x; }
  
  bool parallel(Vector2 &other) {
    return fequals(0, cross(other));
  }
  
  bool orthogonal(Vector2 &other) {
    return fequals(0, dot(other));
  }
  
  bool operator < (const Vector2 &v) {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

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;
}

Shun

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!

Polygon-Point Containment

# Usage

# Algorithm

# A point is on a polygon

# Code

Comments