 # 2D Convex polygons

## Finding whether a point is inside a convex polygon

Short and efficient algorithm showed and explained here.

```int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
```

### Method summary

I run a semi-infinite ray horizontally (increasing x, fixed y) out from the test point, and count how many edges it crosses. At each crossing, the ray switches between inside and outside. This is called the Jordan curve theorem.

## Finding the intersection point of two line segments

This StackOverflow answer takes from a solution by Ronald Goldman presented in the book Graphics Gems p. 304.
Here is my GDScript implementation.

# Triangulation

## Seidel's Algorithm for concave 2D polygons with holes

This article describes an algorithm for triangulating concave polygons with holes by decomposing the concave polygon into trapezoids, then monotone polygons, and then triangulates those. A C implementation is also provided.