I want to implement a clustering algorithm in postgis in which new points are incrementally added to an existent polygon and the polygon subsequently increases it's size to a the minimum possible value so as to cover all the points.

One solution that I came up with is:-

1) When there is first point then nothing to do.

2) When the second point comes we simply make a linestring out of it.

3) When the third point come we make a closed linestring (by making any one point the starting point as well as the last point using ST_AddPoint) using the given three points and ultimately make a polygon (using ST_MakePolygon).

4) Now when the third point comes we use the following algorithm:- If the new point is outside the existing polygon and within a threshold distance from it, we find two of closest points of the polygon from the new point. Now we connect the new point to these two points and eventually form the required polygon. Now, how to find the two closest points? We can find distances of all the points constituting the existing polygon from the new point, order them in decreasing order and limit by 2.

  • No, but some ideas are:- (1) we can use ST_MakeEnvelope. 1st point comes, its a new geometry 2nd point comes, just pass each of the points coordinates as min and max to ST_MakeEnvelope. Save current xmin and current xmax. 3rd point comes, check if its inside the envelope. If so, do nothing. Otherwise, determine if its x or y is lower than envelope's current xmin or current ymin. If so, create a new envelope with the new min max coordinates. (2)We can try to make closed linestring with the new incoming points and hence make a polygon using ST_MakePloygon. Jan 8, 2018 at 14:24
  • You might want to use a concave hull rather than an envelope, if you want the minimum enclosing polygon. However, it is unclear how you wish this algorithm to run, from a list of points, or from an existing minimum containing polygon and a new point, something else? Please edit the question with more information. Jan 8, 2018 at 15:16
  • Thanks for responding. Yes I want to add new points to the existing polygon. I will edit my question and provide a new probable idea as well. Jan 8, 2018 at 15:39
  • 3
    Sounds like you want a combination of postgis.net/docs/manual-2.4/ST_ClusterWithin.html and postgis.net/docs/manual-2.4/ST_ConvexHull.html Jan 8, 2018 at 17:09
  • Hi Nicklas! Can you please explain it a bit more with some examples. Thanks! Jan 8, 2018 at 17:49

1 Answer 1


I am not sure I understand what you want and I don't see the use case.

It seems like you want to define the polygons and let them increase in size.

Then you have to decide what identifies a polygon when new points are arriving. Let's say you want points to be not further away than 100 meters from an existing polygon to connect it to that polygon. Ten you have two polygons 150 meters apart and get a new point in between. Should the 2 polygons then be merged? Or shall they still be separate and the new point just joins one of them?

If so, I suggest you say something like "Any point further away from the FIRST points than 100 meters belong to another polygon. Then you define your clusters from that first point.

That will lead to each point more than 100 meters away from any existing "first points" will start a new polygon.

Then you can identify those new "first points" with st_distance from the existing first points. All points within 100 meters from your first points gets the id from the closest first point (that will not change). Then just group by that id and make a polygon with ST_Convexhull from those groups (Use ST_Collect in between to make geometry collections to feed the ST_ConvexHull function).

But if this is not what you want. If you want to use the cluster algorithms from PostGIS you can as I commented use ST_ClusterWithin to get new clusters from each new point comming in which might change all your existing polygons.

Then just use ST_ConvexHull on the geomety collections you get from ST_Clusterwithin.

ST_ConvexHull makes both points, linestrings and polygons depending on the input.

  • Thank you so much for the explanation! I'm sorry I didn't mention about the threshold distance between an existing polygon and the new point. But you are right, I do have a threshold distance of 5 meters i.e if the distance (ST_Distance) between the new point and the existing polygon is less than 5 meters then I want to add this point to the polygon and make a convex hull (preferably) and if it's outside then it will start making a new polygon. Jan 9, 2018 at 10:04
  • @Niklas And also if there there are two conflicting polygons then I want to select that polygon which has more number of xyz. (Here xyz is some value) Jan 9, 2018 at 14:52
  • Can anyon tell what would the query be like if I want to check which locations in a specific table (e.g cartlocations) are within a distance of 1000 meters from the new incoming point? My query is returning the error HINT: No function matches the given name and argument types. You might need to add explicit type casts. My query was :- select locationid from cartlocations where ST_DWithin(ST_GeomFromText('POINT(23.4877191 86.6927571)'),location,1000); Jan 10, 2018 at 6:30

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.