I have a table with all the hotels in Paris. The columns are the name of the hotel, the geocode and the neighborhood (arrondissement) of Paris that hotel is in.

I've plotted all these points in GQIS and then selected all those hotels that have neighbourhood = 1st arrondissement (highlighted in yellow).

My problem is that it seems my data has some points that have the neighborhood value = 2nd arrondissement within the area where the 1st arrondissement is - as you can see there are orange points within the yellow points.

What would be the best alternative to Voronoi polygons in this case? Perhaps some kind of 2d clustering algorithm for which there is a QGIS plugin?

UPDATE: Here's where I am now:enter image description here

So soon I'll have the whole of Paris covered with these overlapping polygons. My final question is, how do I take the 'averages' of these polygons so that I'm left with a series of non-overlapping, interlocking polygons (kind of a 'mosaic' with no spaces between the polygons) so I have complete coverage with no overlap or gaps?

I guess where two polygons are overlapping I want the border to me the average of the two.

enter image description here

  • Convex hull based on arrondissement field may help. But it seems you have yellow points at the opposite side of the river, so some workaround would be needed...
    – Kazuhito
    Feb 24, 2017 at 0:11
  • why not use the adrondisimont boundaries to do the selection?
    – Ian Turton
    Feb 24, 2017 at 9:12
  • I can't use the arrondissement boundaries as I can't replicate that process across the other cities in my project...it seems only Paris has such a well defined 'neighborhood' concept. I'll try the convex hull suggestion...but I think the solution needs to have a statistical element in order to discount the outliers Thanks for your responses
    – Steven
    Feb 24, 2017 at 15:25
  • How about QGIS Scipy Clustering?
    – Steven
    Feb 24, 2017 at 15:49
  • Sorry I missed you were using QGIS. Then Concave Hull (not Convex Hull) may come in handy (it's in Processing | QGIS geoalgorithms | Vector geometry tools). You may be able to separate out those outliers. (Will need some trials to find the best threshold value.)
    – Kazuhito
    Feb 24, 2017 at 16:26

1 Answer 1


Check out Converting cluster of Points to Polygons using QGIS? for the answer by underdark, in which Concave Hull plugin was recommended.

Unlike Concave Hull geoalgorithm (Processing) in my comment above, you can choose your field to perform clustering with Concave Hull plugin.

Upon the installation, you will find its button in the Plugins Toolbar, however,

enter image description here <- please do not use this (not this time).

In the Processing Toolbox, you will find Concave hull group, with 2 geoalgorithms.

enter image description here

Now probably there are two options you can try;

1) Concave hull (kNN). Please try this first. You can choose your arrondissement field to set your group. If it is not satisfactory, then

2) Grouping by Shared Nearest Neighbor Clustering and then create Convex Hull by clusterID (output of this SNN Clustering).

  • Awesome! Will try this out now. Thanks for your response
    – Steven
    Feb 27, 2017 at 12:37
  • I've added a picture above of where I am now. I think my questions now are: 1) what method should I use for choosing the optimal k for the SNN clustering? 2) What methods are there for turning the resulting overlapping polygons into non-overlapping polygons? 3) In the above screenshot, I've done 1 with the convex hull by cluster ID. Is there another step after that would get rid of the outlier clusters (i.e. the one at the bottom) and then give me a nice complete polygon? Thanks so much for your help!
    – Steven
    Feb 27, 2017 at 19:06
  • @Steven I do not have clear answer to your query. It seems 1) k is data dependent and optimizing algorithm for this tool is not readily available. Generally by increasing k it becomes insensitive to noise, 2) Overlaps of polygons represent that the attribute (arrondissement field in your case) are interspersed. There is only way available in this tool is to manually limit the input points by checking Use selected features only. 3) I was hoping SNN could get rid of outliers (noise), but i am not sure if it can also eliminate small clusters.
    – Kazuhito
    Feb 27, 2017 at 21:45
  • @Steven Overall, what I can think of is just picking this outlier and remove manually. Sorry I could not be of much help. Looking at your result I felt the tool was working well. If you need more detailed polygons, you may be able to try SNN followed by Concave Hull (not Convex Hull)... This was actually the way recommended by the plugin author.
    – Kazuhito
    Feb 27, 2017 at 21:46
  • Thanks so much for your help! I agree I think the current situation (SNN then convex hull, giving above results) is a pretty good result. One last question - do you have a recommendation on how to create 3 non-overlapping polygons with no gaps from the output I show in the image above? Maybe something like this? michaelminn.com/linux/mmqgis
    – Steven
    Feb 27, 2017 at 23:40

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.