How do i find pixels points inside quadrilateral using Java?

Question

Im doing some image processing and I have the coordinates of the 4 points of a quadrilateral. (something like a trapezium) How can i get the coordinates of all the pixels inside it? I'm using Java by the way. Thanks!

Answer 1

You need scanline polygon filling.

Here's a quick PDF lecture on the subject:

http://www.cs.binghamton.edu/~reckert/460/lect11_2009-areafill-transformations.pdf

Here's a web page example with some sample C code and a good illustration of the basic idea:

http://alienryderflex.com/polygon_fill/

Here's the short form. Divide your quadrilateral lines into those that are on the left, and on the right. For each constant-Y-coordinate row, figure out the crossing point for the left line; figure out the crossing point for the right line; all pixels on that row between the two crossing points are inside of your trapezoid.

Just by way of history, this sort of thing was originally (and probably still is) done for rendering 3d scenes in software. I think it had a different name back then, but I can't remember it. However, you don't actually have to draw the pixels; the algorithm will give you the pixels whether you draw them or not.

Answer 2

http://wiki.processing.org/w/Find_which_side_of_a_line_a_point_is_on has pseudocode on how to find which side of a line a point is on.

If your quad is defined by points are A, B, C, D - checking if your point is on the 'left' side of AB, BC, CD and DA should give you the answer.

Edit: Oops, I read your question as finding a point, not all points. Hope this is helpful still.

Answer 3

Is this a collision detection question? Do you want to know if a given point is inside a shape? Or do you you really want the co-ordinates of all the points inside your shape?