Get all pixels within a rectangle using corner x,y coordinates

Question

I have a 500 pixel by 500 pixel image that I am using to pull data from a 250,000 index array where each index represents 1 pixel.

The user is able to draw a rectangle at any orientation, and I am capturing the coordinates for each corner.

I am trying to capture each pixel within the rectangle to reference the data array and extract the related data.

I looked at Bresenham algorithm in Javascript and while I can get all the points between each of the coordinates using this solution, I am unable to loop through these points as the paths do not always contain the same number of pixels.

An example of the values I'm looking for using the following coordinates would be:

corner1 = [100,100]
corner2 = [100,105]
corner3 = [105,105]
corner4 = [105,100]

And the result (sort order is not important):

pixelsInRectangle = [
  [100,100],[100,101],[100,102],[100,103],[100,104],[100,105],
  [101,100],[101,101],[101,102],[101,103],[101,104],[101,105],
  [102,100],[102,101],[102,102],[102,103],[102,104],[102,105],
  [103,100],[103,101],[103,102],[103,103],[103,104],[103,105],
  [104,100],[104,101],[104,102],[104,103],[104,104],[104,105],
  [105,100],[105,101],[105,102],[105,103],[105,104],[105,105]
]

One set of coordinates I'm trying to solve for are:

corner1 = [183,194]
corner2 = [190,189]
corner3 = [186,184]
corner4 = [179,190]

Any recommendations would be greatly appreciated!

Answer 1

If rectangle is not axis aligned:

Sort vertices by Y-coordinate.

Get the lowest one. From two next Y-coordinates choose left and right ones.

Start simple line rasterization scan along left edge and along right edge simultaneously: for current integer Y value calculate corresponding rounded X-coordinate for left edge, for right edge, and output all horizonatal line between (xleft, y)-(xright,y)

For edge between vertices (x0,y0)-(x1,y1) formula is

x = x0 + (x1-x0)*(y-y0)/(y1-y0)  

(example for triangle exploiting the same technique)

When some vertex is reached, change equation of corresponding edge, continue.

Using this way, you fill triangle, parallelogramm, another triangle (or just two triangles if two vertices share the same Y)

(You can use Bresenham or DDA, or another line rasterization algorithm if necessary)