Finding all Points inside a rectangle?

Question

I have tried looking at all other articles on this topic however I have turned up with nothing. My question is this, given four corner points of a rectangle, how could I find any points that lie inside or on the rectangle no matter its rotation. My purpose for this is that I have an array representing a map with each index representing a point position, I want to be able to place a rectangle on this map and fill any points that it covers. If pseudo code could be provided as well as the math for this I would greatly appreciate it. I am familiar with java and RBX.Lua

Answer 1

Just google "fill rectangle algorithm" and you'll find plenty of solutions and examples.

One easy way:

For every row (or column) of your raster (image), calculate the intersections with the rectangle.

This leaves you with a set of intervals that you have to fill.

Maybe reading this also helps http://fivedots.coe.psu.ac.th/~montri/Teaching/240-422/filling1.pdf

Answer 2

I don't know if this is what you are looking for...

but still a simple way to solve this problem would be, connect the four points using a line drawing algorithm and apply a simple flood fill or boundary fill algorithm.

Note: All these algorithms come under computer graphics. Also this technique will be a much faster approach than filling inside points one by one and also eliminates computations for points which are outside the rectangle.

Before applying fill you will have to draw boundary lines using line drawing algo and set values of boundary to newcol (newcolour) then the below fill algo can be used.

void floodfill(int x,int y,int old,int newcol)
{
            int current;
            //assign current with the color of x,y point

            if(current==old)
            {

                            //assign x,y point with newcol

                            floodfill(x+1,y,old,newcol);
                            floodfill(x-1,y,old,newcol);
                            floodfill(x,y+1,old,newcol);
                            floodfill(x,y-1,old,newcol);
            }
}

You can use the above method where you just have to pass any inside point(x,y) of the rectangle and old color which is to be replaced with the new color. Assuming color values are integer values in the array you mentioned.

Answer 3

Use Point-In-Polygon (Java sample code) to check if a point is inside the area or not. For your case, the area is a rectangle. If with multiply points, need to loop through and check point by point.