1

I have 3 columns in my table: centerPoint (point), uuid (string), and "areaID".

Each areaID can have multiple uuid's, and each uuid has a corresponding centerPoint. I want to calculate the shortest path through all the centerPoints of a particular "areaID", and I want the relevant uuid's to be listed along the path.

I am following this resource in its implementation, as recommended by @geozealot.

Here is my modified code:

WITH RECURSIVE
  tree AS (
    SELECT
      g."centerPoint"::GEOMETRY AS vtcs,
      NULL::GEOMETRY AS segment,
      ARRAY[g.uuid] AS uuids
    FROM
      potential_missed_areas AS g
    WHERE
      g."areaID"  =  '007af142-75a3-4678-975a-29f78b92af05'
      and g.status = 'approved'
    UNION ALL   
    SELECT
      ST_Union(t.vtcs, v."centerPoint"),
      ST_ShortestLine(t.vtcs, v."centerPoint"),
      t.uuids || v. uuid  
    FROM
      tree AS t
      CROSS JOIN LATERAL (
        SELECT
          g. uuid  , g."centerPoint"
        FROM
          potential_missed_areas AS g
        WHERE
          NOT g. uuid   = ANY(t.uuids)
        ORDER BY
          t.vtcs  <->   g."centerPoint"
        LIMIT
          1
      ) AS v
  )       
SELECT
  segment
FROM
  tree
WHERE
  segment IS NOT NULL
;

The problem is that this generates a result set with 5,184 rows, whereas this particular areaID has only 6 uuid's.

1 Answer 1

2

Add the "areaId" to the filter criteria in the recursive term, or it will consider rows across all "areaId"s to find candidates:

...
CROSS JOIN LATERAL (
  SELECT
    g.uuid,
    g."centerPoint"
  FROM
    potential_missed_areas AS g
  WHERE
    g."areaId" = <area_id>
    AND
    NOT g.uuid = ANY(t.uuids)
  ORDER BY
    t.vtcs <-> g."centerPoint"
  LIMIT
    1
) AS v
...

You also need to pick a single row (uuid) in the driver term, i.e.

SELECT
  g."centerPoint"::GEOMETRY AS vtcs,
  NULL::GEOMETRY AS segment,
  ARRAY[g.uuid] AS uuids
FROM
  potential_missed_areas AS g
WHERE
  g.uuid = <uuid>
...

This query can be enhanced to be more generic, generating MSTs over all partitions you want. But check if MSTs are what you are looking for.


But note that a MST is not the shortest, singular path as in the Traveling Salesman Problem - it is a tree, having branches, with the minimum aggregated connection lengths!

8
  • so the result set can not be used to derive the shortest path?
    – analyst92
    Commented Sep 30, 2023 at 14:32
  • if I only take the row from the result set which has the exact number of items that I want, then it would be the result for the TSP problem right?
    – analyst92
    Commented Sep 30, 2023 at 14:38
  • 2
    RE: too many returned rows: see my update. RE: the TSP: this is much more involved than this point set MST algorithm, and you would need to look into sophisticated graph analytics engines (e.g. pgRouting for PostgreSQL/PostGIS). For 6 points only you could easily brute force the optimal solution (having only 6! = 720 permutations), but double that and your machine will burn.
    – geozelot
    Commented Sep 30, 2023 at 15:05
  • 1
    thanks, may you live a happy and blessed life!
    – analyst92
    Commented Sep 30, 2023 at 15:09
  • 1
    My solution creates a Minimum Spanning Tree, which is not the optimized shortest route through all points as in the Travelling Salesman Problem - please research the difference! With regards to what I said: this is meant for the TSP where you could brute force the optimal solution for only 6 points; for 30 points, however, you're looking at !30 = 2.6 * 10^32 permutations!
    – geozelot
    Commented Oct 9, 2023 at 11:21

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.