# What algorithm allows me to calculate the set of all points inside a polygon?

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:

1. Spatial joining (suggested by Joseph)
2. Scan line algorithm (another explanation)
3. Z-buffering

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)`,

where

• `x,y,z` are coordinates and
• `type` is 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.

• Are you looking for creating points in a polygon (e.g. where the vertices lie) or do you already have a points layer and you want to see which polygon it is in? – Joseph Oct 1 '15 at 9:28
• I have a polygon defined by 1) points and 2) lines between them (derived from 1 using Bresenham algorithm). Those are the input data. I need to find all points inside the polygon. Look at the image - if you want to put a roof on a building, you need (in its simplest form) put blocks in its entire area. – DP_ Oct 1 '15 at 9:41
• In QGIS, you could try using Join attributes by location with your point layer as the Target layer. This would create a point output file with attributes from the polygon it resides in. Or alternatively, you could use the SAGA tool - Add polygon attributes to points which does the same thing except you choose a single attribute field to identify which point belongs to a polygon. – Joseph Oct 1 '15 at 9:52
• Thanks. Do you know what algorithms (a name is sufficient) these tools use? I need to implement this thing myself (or find a Java library, which does it). Maybe there is a specific name for this task? – DP_ Oct 1 '15 at 10:07
• These tools are, more or less, spatial joining algorithms if it needs some kind of a name (if there's a special name for it then I don't know it). As QGIS is opensource, you could check the python scripts used for tools like this. – Joseph Oct 1 '15 at 10:13

In you comments you have stated you have the points and lines of your polygons. I don't know why you would need all the green points inside your polygon to create your roof. I would suggest to build Medial Axis (skeleton) of your polygon and use its points to build up your roofs (Images). This is the algorithm, many 3-Dimensional software use to build 3D building.

Update

To have a flat roof, you don't need polygon internal points to create a flat roof. Just connect the dots (e.g. polygon vertices) like the floor of the building. The simple procedure would be to extract polygon vertices and then extrude it to build the 3D buildings.

• The simplest possible roof is flat. Many buildings in cities have flat roofs. That's why first I want to create plain, flat roofs. – DP_ Oct 1 '15 at 11:56
• You don't need polygon internal points to create a flat roof. Just connect the dots (e.g. polygon vertices) like the floor of the building. – Farid Cheraghi Oct 1 '15 at 11:57
• 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)`, where `x,y,z` are coordinates and `type` is the material of the block. 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. – DP_ Oct 1 '15 at 12:03
• Please include this information in your original question. – Farid Cheraghi Oct 1 '15 at 12:06
• Done. See update 3. – DP_ Oct 1 '15 at 12:16

The algorithms for this are called flood fill. It's interesting that we use it every day, but don't know it by name.