Determine if square cell is inside polygon

Question

For instance, I want the grid cells (squares) inside or partially inside polygon #14 to be associated with #14. Is there an algorithm that will compute if a square is inside a polygon efficiently?

I have the coordinates of the edges that make up the polygon.

Answer 1

If I get it right, this is an implementation of Fortune's algorithm in JavaScript, that takes a set of 2-d points (called sites) and returns a structure containing data for a Voronoi diagram computed for this points. It returns polygons in a list called cells. It seems to use Euclidean distance as measurement. If it's true we know that polygons are always convex (see Formal definition section in Voronoi wiki page).

Now, these are options to solve this problem (hard to simple):

1. Polygon Clipping:

1. Form a polygon for the square.
2. Find its intersection with all cells.
3. Calculate area of this intersections.
4. Find the largest intersection.

2- Point in Polygon:

You also can simply find the cell that center of the square lies inside it. Ray casting is a robust PIP algorithm. Although there's a simpler approach for convex polygons (see Convex Polygons section here).

3. Distance Between Points:

I if you know the site associated to each cell then you just need to calculate distance between center of square to all sites. Regardless of what distance measurement you use to compute the Voronoi, the center point of square lie inside the cell that distance of it's associated site is minimum, since this is actually the idea for partitioning the plane in a Voronoi diagram.

---

Exceptions:

• First approach is computationally expensive but most accurate. Second and third options work fine in most cases, however, there are exceptions that they fail to decide correctly:

• Second and third are pretty much alike, but the down side of PIP is cases where point lies on edges of the polygon that cost you more overhead to detect.