Imagine I have a polygon, which represents the countours of a building on an integer 3D map (everything is a 1 meter by 1 meter block in that map). In the image below, you see several buildings without roofs.
In order to draw the roofs, I need to know what points are inside the polygon.
What algorithm can I use for that?
People mentioned convex hull, but it gives me the polygon, which I already have.
Update 1 (01.10.2015 13:34 MSK): I found following potential names:
Update 2 (01.10.2015 14:22 MSK): Imagine I have a rectangle defined by the black line in the image below, drawn on a grid.
I need an algorithm, to find out the coordinates of all points inside the polygon, i. e. all the green points.
Update 3 (01.10.2015 15:09 MSK): Note that this is a Minecraft map, which you can imagine as a 3-dimensional raster with every "pixel" being a block of 1 meter in length, width and height.
The only command, which my renderer accepts is this:
world.setBlock(x, y, z, type),
x,y,zare coordinates and
typeis the material of the block (e. g. cobblestone, grass or bricks).
This command puts one block at exactly those coordinates. The space around it remains free. When I want to draw lines, I need to do several calls like that. When I want to fill an area (e. g. a flat roof), I have to do those calls for all of the internal points of the polygon. My renderer doesn't have a "fill polygon" feature, I have to implement it myself.