Creating polygons layer from point layer with conveks buffer

Question

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.

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.

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

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
  install.packages("fpc")
  
  # load library
  library(fpc)
  
  # set plots bg-color
  par(bg="grey80")
  
  # import your point data
  data = read.csv("/home/ymirsson/R/projects/DBSCAN_Test/point_sample.csv",sep=";",header=T)
  
  # create a working object
  data2=data
  
  # delete all variables you do not want to be used to cluster the points
  data2$ID = NULL
  
  # plot points
  plot(data2)
  
  # 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.

EDIT:
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:


Idea:
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):


Comparison:


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.