6

I have a series of points in a horizontal line, arranged into discrete spatial clusters by the underlying data pattern. Here's an example of what they look like:

enter image description here

How can I use PostGIS to group them spatially into the highlighted sets A, B and C?

This is a harder problem than it initially seemed to me. So far I've tried:

  • Using ST_X() to order them, then lag() to identify points between which there are gaps. Unfortunately this just groups the points into "gap" groups and "interior" groups.

  • Using convex hulls around arbitrary spatial thresholds. This both failed to separate all clusters and had the side effect of creating mid-cluster separations. (For future reference, this was a dumb idea.)

  • Using ST_GeoHash() to cluster them. This doesn't accurately catch the linear nature of the geometry.

  • 2
    Not smart enough to plop out an answer but the two terms that percolate in my brain are "inter-point distance" and "windowing" (see PostgreSQL manual). – Paul Ramsey Mar 27 '14 at 14:54
  • @PolyGeo - I'm curious; why the edit on this? – Bill Morris Oct 21 at 1:07
  • The trigger for an edit was the unnecessary appreciation offered at the end. I think it falls under "no chit chat" of the Tour. Imagine if every question ended with a flurry of gratitude rather than staying focused on the question content. – PolyGeo Oct 21 at 1:22
5

I'm not at a computer that has access to PostGIS right now, but I feel as though this algorithm might work. Of course if you have vertical groups, you would need to use an exclusion or inclusion clause for ST_Y().

DECLARE @totalUnique int = 0
DECLARE @lastUnique int = 1

CREATE TABLE #TABLEX (ID1 int, ID2 int)
CREATE TABLE #TABLEX2 (ID1 int, ID2 int)

--Get distances of objects
INSERT INTO #TABLEX
SELECT ID1, ID2
FROM   (
         SELECT T1.ID AS ID1, 
                T2.ID AS ID2
         FROM   BaseTable AS T1
                INNER JOIN
                BaseTable AS T2
                    ON  ST_Distance(T1.Shape, T2.Shape) <= SeparationDistance
       ) AS X

--Loop for as long as new connections can be made
WHILE(@lastUnique <> @totalUnique)
BEGIN
  --Count the number of current connections
  SELECT @lastUnique = COUNT(*)
  FROM (
         SELECT * FROM #TABLEX
         GROUP BY ID1, ID2
       ) AS XX 

  --Look for new connections via current known paths
  INSERT INTO #TABLEX (ID1, ID2)
  SELECT A.ID1, B.ID2
  FROM #TABLEX AS A
       INNER JOIN
       #TABLEX AS B
       ON A.ID2 = B.ID1
          AND
          A.ID1 <> B.ID2

  --Count the number of current connections   
  SELECT @totalUnique = COUNT(*)
  FROM (
         SELECT * FROM #TABLEX
         GROUP BY ID1, ID2
       ) AS XX

  --Group each path set by the lowest ID
  INSERT INTO #TABLEX2(ID1, ID2)
  SELECT MIN(ID1) AS theGroup, ID2
  FROM   #TABLEX
  GROUP BY ID2

  TRUNCATE TABLE #TABLEX

  --Reload our new path sets
  INSERT INTO #TABLEX (ID1, ID2)
  SELECT ID1, ID2 FROM #TABLEX2

  TRUNCATE TABLE #TABLEX2
END

--Show final results        
SELECT ID1 AS theGroup, ID2
FROM   #TABLEX

DROP TABLE #TABLEX
DROP TABLE #TABLEX2
1

Is the mean point spacing in X consistent within a group, like these are mile markers?

I'd create rectangles centered on each point with a width slightly larger than the point spacing, and a very small height. Then union them, and use the new polygons to group the points.

This assumes the points are in groups in X, but may have other points nearby in Y. If your dataset is a single line of data points, you could just use a circular buffer.

  • Yeah, definitely have other rows running parallel. I'll try the boxes; any idea how to assign unique values to them post-union? Man, who knew this would be so hard? :) – Bill Morris Mar 27 '14 at 18:18
  • Insert the unioned geometry into a table with an autoincremented id column. – Marc Pfister Mar 27 '14 at 18:22
  • Oh man; I think the answer above covers it, but I had already run with your boxes idea and it worked great :) – Bill Morris Mar 28 '14 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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