I have a point layer of >750000 points representing dwellings with district heating.

Now, I want to create polygons for every n of points with a distance of n meters to the next point.

I have a polygon layer from a municipality, but the polygons are wrong in some places. enter image description here

The points outside the dotted-polygon, should have a polygon of themselves. Note this is only a very small fraction of the data.

Also there are polygons where there are no points intersecting. enter image description here

So, my question is: Is there somehow a function or something else, which can create the polygons for every eg. >=5 points with a distance og eg. 10 meters to the next point?

I have tried working it out with the convex hull function, but it doesn't do the trick, because I have to select the points by hand, it that process will take ages for the whole dataset.

I'm using QGIS 2.6

  • You can use the Vector>Research Tools>Select by Location to select those points that intersect with a polygon within your polygon layer. Than switch selection and save selected to a new layer. Using convex hull than will create polygons only for points that are not within a polyogn.
    – dof1985
    Commented Mar 18, 2015 at 11:53
  • Thanks. But the real problem is that the polygon layer I already have is not sufficient enough. I need to make a new polygon layer, as described above.
    – Kasper
    Commented Mar 18, 2015 at 12:36
  • Take a look at the DBSCAN or OPTICS algorithm. I don't think, there is anything in QGIS, but there is a library in R, so it may need some intermediate steps.
    – ymirsson
    Commented Mar 18, 2015 at 13:00
  • @yrmirsson, thanks! I'll look into it. I also have access to AcrMap. Is there any functions here I could use?
    – Kasper
    Commented Mar 18, 2015 at 13:05
  • Maybe .. but i don't know. I don't have access to the ESRI package ;)
    – ymirsson
    Commented Mar 18, 2015 at 13:07

1 Answer 1


Try this:

  • Install R, and if you want a (slightly) more GUI style R-Studio
  • Open R (Studio) and run this script (modify to your need) (there is an option to run it step-by-step, if you prefer):
    # install dbscan package
    # load library
    # set plots bg-color
    # import your point data
    data = read.csv("/home/ymirsson/R/projects/DBSCAN_Test/point_sample.csv",sep=";",header=T)
    # create a working object
    # delete all variables you do not want to be used to cluster the points
    data2$ID = NULL
    # plot points
    # run DBSCAN clustering
    ds <- dbscan(data2, eps=100, MinPts=3, showplot=1)
    # create a vector with the cluster prediction
    pre <- predict(ds,data2)
    # join the prediction to your base data-object
    exp <- data.frame(data,pre)
    # export
    write.table(exp, "/home/ymirsson/R/projects/DBSCAN_Test/point_sample_clustered.txt", sep="\t")
    Note: The clustering will take a lot of time .. so it may be better to experiment with a smaller sample until you have your paramters for eps/min-points.
  • Import your clustered points in QGIS
  • Select only those with "pre">0 (b/c there will be outliers, and they will screw up your polygons ;) )
  • Run Vector>Geoprocessing Tools>Convex Hulls, with only your selected points and set your cluster-variable
  • Will look smth. like this:
    or zoomed:
  • You may want to extend the borders with a buffer:

Please note:

  • I'm not aware of a QGIS implementation of dbscan or a c&p python script .. but that doesn't mean it doesn't exist, so maybe you can skip the R part ;)
  • I'm more of a "fun user" in R, and mostly for data statistics. There may be a better script and maybe you can create the polygons in R .. i don't know.

The surrounding borders of the convex hulls are very rough, so i propose an improvement idea:
This shows the "current" state of the resulting polygons, which include a lot of unnecessary empty space:

In a subsequent step mark the outlining points and ID them (counter)clockwise:

Create a line vector with one of the "point 2 line/path" plugins:

And convert it into a more suitable polygon (incl. a buffer):


I'm not aware of a plugin to fetch the outline-points, but i think it wouldn't be that hard to write a little script.

  • Awesome!!! It worked perfectly for the test data (n=6679) Thanks!
    – Kasper
    Commented Mar 19, 2015 at 9:01
  • Gave it a little more thought .. see edit for a slightly better(?) approach.
    – ymirsson
    Commented Mar 19, 2015 at 12:37
  • Hmm, looks very interesting. I'll look into it. Thanks!
    – Kasper
    Commented Mar 19, 2015 at 13:43
  • 1
    The Concave Hull plugin might work for the "nicer" polygons: plugins.qgis.org/plugins/concavehull Actually, it offers clustering as well so it might be a fully working alternative to the R workflow. Commented Aug 4, 2015 at 15:06
  • That really does the trick, at least for the polygons. Nice, thx :)
    – ymirsson
    Commented Aug 6, 2015 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.