I've got a humongous problem!
I need a function that returns the pixels that are located within an area of 4 points (not just a rectangular area),
example:
Just for examples sake, we make the screen 16x16:
We choose 4 points:
And then to return the pixels inside the polygon (table).
Any suggestions?
EDIT:
Im making a game which has to select a group of grids to display on the screen. The grid is isometric, so i need to choose grids inside a rotated rectangle.
Return pixels in polygon
Forum rules
Before you make a thread asking for help, read this.
Before you make a thread asking for help, read this.
Re: Return pixels in polygon
You can do it with a scan/sweep line algorithm:
The scanline is a vertical line that moves to the right scanning the interior. Initialize it with the x-coordinate of the leftmost point.
Repeat until you hit the rightmost point:
Find the intersections points of the shapes outer segments with the scanline.
Determine the maximum and minimum y-coordinate of these intersection points.
Add pixels with x-coordinates of the scanline and y-coordinates between the max/min to the pixel list.
Move the scanline one pixel to the right.
In (untested) code:
This algorithm will work with any convex polygon, not just with a tetragon. Welcome to computational geometry.
The scanline is a vertical line that moves to the right scanning the interior. Initialize it with the x-coordinate of the leftmost point.
Repeat until you hit the rightmost point:
Find the intersections points of the shapes outer segments with the scanline.
Determine the maximum and minimum y-coordinate of these intersection points.
Add pixels with x-coordinates of the scanline and y-coordinates between the max/min to the pixel list.
Move the scanline one pixel to the right.
In (untested) code:
Code: Select all
-- get the y-coordinate of the intersection of a vertical line and a segment
function intersect(x, x1,y1, x2,y2)
-- assuming x2 and x1 are different:
local t = (x - x1) / (x2 - x1)
if t >= 0 and t <= 1 then
return y1 + t * (y1 - y1)
end
return nil -- explicit nil
end
-- x1,y1, ..., x4,y4 are integer coordinates of the bounding points
function inside_pixels(x1,y1, x2,y2, x3,y3, x4,y4)
local rightmost = math.max(x1,x2,x3,x4)
local leftmost = math.min(x1,x2,x3,x4)
local pixels = {}
for x = leftmost, rightmost do
local i1 = intersect(x, x1,y1, x2,y2)
local i2 = intersect(x, x2,y2, x3,y3)
local i3 = intersect(x, x3,y3, x4,y4)
local i4 = intersect(x, x4,y4, x1,y1)
-- this wont work, you need to account for nil values here
local y_upper, y_lower = math.min(i1,i2,i3,i4), math.max(i1,i2,i3,i4)
for y = y_lower,y_upper do
pixels[#pixels+1] = {x, y}
end
end
return pixels
end
Who is online
Users browsing this forum: Bing [Bot], Google [Bot] and 1 guest