• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

How to check if a point is inside of a polygon?

Contents

  • Basics about polygones
  • Is a point in a triangle / a rectangle
  • Is a point inside of a n-glon?
    • Count Crossing Line Segments
    • Triangularization

Suppose you have a with $n$ sides. This is called a $n$-glon.

Basics about polygones

A $n$-glon can be defined by a list of $n$ points.

Note that the order is important:

The order of points is important for the definition of a polygon
[A, B, C, D, E, F, G] != [A, B, C, D, F, E, G]

I will not consider self-intersecting polygones for the following statements. I'm aware of them, but whenever you have a self-intersecting polygon you can create multiple polygones that cover the same area and don't intersect each other (some pairs might have a finite number of points in common, but not an infinite number).

Is a point in a triangle / a rectangle

It is quite easy to check weather a point is inside of a triangle or inside of a rectangle. I have already written an article about how to check if a point is inside of a rectangle.

Is a point inside of a n-glon?

Let $P$ be a point and $N = [P_1, P_2, \dots, P_n]$ be a $n$-glon. It is now much more difficult to check if $P$ is inside of $N$. The area-approach works for convex $n$-glons, but that's it.

Count Crossing Line Segments

However, you can try another approach which I have visualized in the following image:

Check if P is inside of N
Check if P is inside of N

When $P$ is inside of $N$, every line $P_{1}P, P_{2}P, \dots, P_{n}P$ will cross the polygon lines $P_{1}P_2,P_{2}P_3, \dots, P_{n}P_1$ an even number of times. If P is outside, at least one of the lines $P_{i}P$ will cross a polygon line $P_{j}P_{j+1}$ once.

This means, for every check you have to check $n^2$ pairs of line segments for crossings. How you can do that is explained in my article How to check if two line segments intersect.

This algorithm is in $\mathcal{O}(n^2)$ time complexity (it does need a constant amount of additional space).

Triangularization

When you have a lot of querys, you might want to divide your polygon into convex polygones. The easiest way to do this might be dividing $N$ into triangles.

That way, you can check for every triangle if $P$ is inside of it. I assume that the number of triangles is not bigger than $n$. As the check is in constant time for one triangle, you would have an algorithm that needs $\mathcal{O}(n)$ time and space for its checks (+ some preprocessing which is done only once).

Published

Nov 18, 2013
by Martin Thoma

Category

Code

Tags

  • algorithms 13
  • Geometry 5
  • Python 141

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor