Iterate each point within a polygon

Question

Assuming I have the vertices of some polygon in a grid environment, how can I iterate through each cell it contains (including those on the edge)?

To clarify, I have the following vertices (counted as if the topleft is (0, 0)):

//each point is [x, y]
var verts = [
    [1, 1],
    [3, 1],
    [3, 2],
    [4, 2],
    [4, 4],
    [0, 4],
    [0, 3],
    [1, 3]
];

Which would define a polygon such as this:

grid

Where each green dot is a point I would like to iterate, based on the vertices above. There is no pattern to the direction the vertices will walk along the edge of the polygon, it could go clockwise or counter-clockwise around the polygon. However, they will be in order; that is, if you put down your pen and move to each vertex in order, without lifting up, and it would draw the outline without crossing inside the polygon.

The use case being I have the imageData from a PNG loaded via the canvas API. This PNG is split into "zones", and I need to iterate each pixel of the current "zone". Each "zone" is defined by a vertex array like above.

I tried something like the following, which will create a square to iterate through for each set of 4 vertices in the array.

for(var v = 0, vl = verts.length - 4; v < vl; ++v) {
    //grabbing the minimum X, Y and maximum X, Y to define a square to iterate in
    var minX = Math.min(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]),
        minY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]),
        maxX = Math.max(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]),
        maxY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]);

    for(var x = minX; x < maxX; ++x) {
        for(var y = minY; y < maxY; ++y) {
            //do my checks on this pixel located at X, Y in the PNG
        }
    }
}

Two big problems with that though:

It can repeat points within the polygon, and
It can grab points outside the polygon

I can solve the first issue by tracking which points I check, so I don't repeat a check. The second can only be solved by running a PointInPoly check on each point, which would make this solution much heavier than I want it to be.

EDIT
Iterating each pixel in the entire image and applying a PointInPoly check to each is also unacceptable; it would be even slower than the above algorithm.

1: you're right -- iterating through pixels in a canvas' ImageData, even offscreen, is ROUGH. 2: you've got a bunch of rectangles you're defining, based on each 4 points in your list, which you then brute-force your way through pixels. Instead, why not try creating maximum-area rectangles from your point-data. It's not a trivial solution, but if you take your vertex list and create bounding-boxes from those points, which are guaranteed to be inside of those areas, and push those new boxes into a new array, that's all memory, and then pixels in each box WILL need to be modified. — Norguard, Nov 15 '12 at 17:40
@Norguard I don't think I fully understand what you are saying, or how to implement it. Any way of getting a code sample (even pseudo-code)? — Chad, Nov 15 '12 at 19:43

score 1 · Accepted Answer · edited May 23 '17 at 10:24

1

If your polygons are convex, you can do the following:

Create a line for each edge of the polygon denoting one side inside and one side outside (this is based on the normal, which can be dependent on the winding direction)
For every pixel inside the bounding box that you already calculated, check to see if the pixel is on the in-side of the line. If the pixel is on the out-side of any of the lines, then it is outside the polygon. If it is inside all of them, then it is inside.

The basic algorithm is from here: https://github.com/thegrandpoobah/voronoi/blob/master/stippler/stippler.cpp#L187

If your polygons are not convex, then what I would do is to actually draw the polygon on the canvas in a known colour, and then apply the iterative flood fill algorithm. That requires that you know at least one pixel which is on the inside, but that shouldn't be an expensive test. But this may not be suitable in JavaScript if you can't do it in an offscreen buffer (not familiar with the canvas tag).

edited May 23 '17 at 10:24

Community

1
1

answered Nov 15 '12 at 06:29

syazdani

4,760
1
26
35

No, I don't. This would mean I would iterate each pixel of the entire map and check if each is within the polygon. I am already casting rays for other checks within these zones, but that is not what I want here. I literally only want to hit the pixels within the zone. My loop I put in my question would be much faster than this for large maps (which there are many). – Chad Nov 15 '12 at 12:42
Ahh okay, I misunderstood the requirements. I have updated my answer to another algorithm. – syazdani Nov 15 '12 at 17:21
Creating a bounding box, and applying some kind of `PointInPoly` check to each point within the box is what I am doing right now (though I am creating many smaller bounding boxes, instead of one large one). I was hoping there was a more accurate way to do this; some property that I didn't know about to allow me to *not* use a bounding box method. – Chad Nov 15 '12 at 17:29
I don't know of any. I've always created a binary mask using the iterative flood fill and just done a simple multiplication with the colour value of the pixel. This is in C++ though where iterating through those pixels is parallelizable and speedy though... – syazdani Nov 15 '12 at 17:33
I'm going to combine your method and some advice from Norgaurd. – Chad Nov 22 '12 at 18:05

Iterate each point within a polygon

1 Answers1