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.