# use points to define a space inside an irregular polyon?

I’m using a matrix(list) to define points on a grid. the matrix is rather large 120x160. I need an algorithm that can tell the matrix what points are inside a polygon and what points are both inside and occupied by an object.

I could easily store the position of every corner and point along each line. what I don’t know, is how to mark every point inside the shape on the matrix as being inside said shape.

here are two images of the kinds of shapes I’m dealing with:

every line is always either horizontal or vertical. there are never any diagonals.

here is a good approximation of what the matrix would look like minus the “[in]” and “[out]”

0 = not checked
1 = edge
2 = inside

000000000000000000000000000
0[OUT]000000000000000000000
0000000011111111111110000000
000000001000000000010000000
000000001000 [IN] 0010000000
000000111000000000010000000
0000001000000011111100000000
000000100000001000000000000
0000001000000011111111100000
000000100000000000000010000

changed to (with algorithm):

000000000000000000000000000
0[OUT]000000000000000000000
000000001111111111110000000
000000001222222222210000000
000000001222 [IN] 2210000000
000000111222222222210000000
000000122222221111110000000
000000122222221000000000000
000000122222221111111110000
000000122222222222222210000

I think I can use a “flood-fill” algorithm.

If you already have the edges marked as you seem to be indicating, then yes a simple flood fill algorithm should be all you need.

There is a relevant common programming/maths concept: PIP which is an acronym for point in polygon, read about it here: http://en.wikipedia.org/wiki/Point_in_polygon

Since you have a monotone polygon you could use horizontal lines for scanning the number of intersections. http://en.wikipedia.org/wiki/Monotone_polygon