11

I want to create a polygon around a set of points which should exactly just contain the set of points without leaving any blank spaces in between. Below is the best output I am getting after using ST_ConcaveHull.

a) With Allow holes set as false

ST_ConcaveHull with allow holes set as false

b) With Allow holes set as true

ST_ConcaveHull with allow holes set as true

As it is clearly visible in these 2 images that the created polygon has a lot of extra blank spaces. Is there any other PostGIS methods or any other way to get a polygon which will exactly contain points without these spaces?

Below is rough drawing on what I am trying to achieve or the desired output.

Rough Diagram of desired output

The MultiPoint Geometry used for this example - SRID-4326

MULTIPOINT(-1.14550839539633 51.349096419770646,-1.145447973240274 51.349051277340756,-1.14539178158296 51.34901358753763,-1.145343972821787 51.348966971200916,-1.145222612554494 51.349086340628475,-1.145157578005767 51.34911251714186,-1.14507017869585 51.3491477407498,-1.144943675904492 51.3472537660354,-1.144919242528779 51.34915120646431,-1.144878766526116 51.347202046136196,-1.144720187793824 51.34919118904576,-1.144683165018423 51.346991976730955,-1.144662816831716 51.34921421827459,-1.144526992373702 51.34878690461452,-1.144511741772054 51.34704541674788,-1.144464001783175 51.349010131013635,-1.144463501471217 51.34706399459523,-1.144462051819252 51.346980230620765,-1.144460629006732 51.34759708434879,-1.144430717433369 51.348946872495574,-1.144407717835232 51.34700119043971,-1.144391229150454 51.34935570032344,-1.144374115025737 51.34873994555251,-1.144345781203042 51.34845885537696,-1.144299396595842 51.34939150931823,-1.144272215351986 51.34875997516049,-1.144261651462714 51.349143941800165,-1.144242439732235 51.348479762737675,-1.144223666010186 51.34944318084656,-1.144204558317098 51.3470437065884,-1.144167633428061 51.34873771316475,-1.144152571210615 51.347527573398935,-1.144141712519119 51.34847072053944,-1.14413633973979 51.349112471129885,-1.144108474521806 51.35017369504347,-1.144103184442185 51.347078576385016,-1.144040226084474 51.34913286337735,-1.144035299266902 51.34757852596799,-1.144005636147613 51.35023993803115,-1.143996516408931 51.34951084077941,-1.143957158865123 51.34890294944334,-1.143954277891866 51.349310975521924,-1.143951438587779 51.34916528445699,-1.143937334954572 51.35028259656979,-1.143933831555771 51.347645383994944,-1.143929055792627 51.348841987254595,-1.1439159198155 51.34713213364151,-1.143905710885557 51.34877237092709,-1.143903619019044 51.348460901443396,-1.143873752414366 51.34840175577038,-1.143855162513264 51.34833608505633,-1.143834166620764 51.34913746980413,-1.143831665603008 51.347921217152695,-1.1437386163883 51.347207992022845,-1.143721895513458 51.3506672984304,-1.143709076021083 51.34772871312751,-1.143638268900347 51.34801845182888,-1.143626620547187 51.34760470907805,-1.143617282882746 51.35047588536541,-1.143579231728186 51.350362250751814,-1.143563280478384 51.35030490535053,-1.143545558884141 51.34991975765717,-1.143535204773802 51.350204299721526,-1.143530209915138 51.347857197663394,-1.143517809327692 51.350141176489956,-1.143506129471963 51.34980096338131,-1.143485899433675 51.350038314777194,-1.143394303155614 51.347345880576825,-1.143295372529182 51.34744404329489,-1.143264875275143 51.34769429442993,-1.143106460590058 51.35076156625117,-1.142970200189679 51.350791619425785,-1.142924537875887 51.350401910608916,-1.142907192056859 51.34931716267006,-1.142898636729378 51.34753763178483,-1.142888221970861 51.35033873241286,-1.142842488795257 51.35028673011974,-1.1428235249613 51.35022626601221,-1.142795322377737 51.350177198463456,-1.142780832026207 51.34757712035511,-1.142770980956128 51.35084010415572,-1.142645351098051 51.3501301555084,-1.14263558073759 51.350067603580875,-1.142612047211917 51.347611647063275,-1.142587435393211 51.35002289482325,-1.14257620485503 51.34996324710596,-1.142522307438992 51.347642185668114,-1.142501663746491 51.34991814449924,-1.142472008375048 51.34986558613821,-1.14244049033591 51.34980705717423,-1.142326478702596 51.34773046006081,-1.142219331615346 51.34779928464388,-1.14211714231714 51.34951893650008,-1.142037325384087 51.34782610162637,-1.141727772841377 51.35055457549599,-1.141407654397489 51.3499700552294,-1.141386689760339 51.3498798174562)
Improve this question
1
  • 1
    @BERA I have the updated my original question and added a rough drawing of the desired output. Hope that helps. And let me know if anything else is required from my side for better understanding of the problem.
    – George V
    Commented Dec 14, 2021 at 11:39

3 Answers 3

Reset to default
10

I was able to get the desired result using Minimum Spanning Tree as @Bera had suggested. I looked into it and followed the steps mentioned in the already answered question in the link Finding the minimum spanning tree (MST)

Then added a buffer to that spanning tree to get the desired polygon.

Below is the output polygon.

Output after using minimum spanning tree and buffer

Below is the PostGIS query I used after creating the types and functions specified in this github link https://gist.github.com/andrewxhill/13de0618d31893cdc4c5 :

WITH cte2 As (
 WITH cte AS (
   Select row_number() OVER () as id,
         (ST_DumpPoints(ST_SetSRID('MULTIPOINT(-1.14550839539633 51.349096419770646,-1.145447973240274 51.349051277340756,-1.14539178158296 51.34901358753763,-1.145343972821787 51.348966971200916,-1.145222612554494 51.349086340628475,-1.145157578005767 51.34911251714186,-1.14507017869585 51.3491477407498,-1.144943675904492 51.3472537660354,-1.144919242528779 51.34915120646431,-1.144878766526116 51.347202046136196,-1.144720187793824 51.34919118904576,-1.144683165018423 51.346991976730955,-1.144662816831716 51.34921421827459,-1.144526992373702 51.34878690461452,-1.144511741772054 51.34704541674788,-1.144464001783175 51.349010131013635,-1.144463501471217 51.34706399459523,-1.144462051819252 51.346980230620765,-1.144460629006732 51.34759708434879,-1.144430717433369 51.348946872495574,-1.144407717835232 51.34700119043971,-1.144391229150454 51.34935570032344,-1.144374115025737 51.34873994555251,-1.144345781203042 51.34845885537696,-1.144299396595842 51.34939150931823,-1.144272215351986 51.34875997516049,-1.144261651462714 51.349143941800165,-1.144242439732235 51.348479762737675,-1.144223666010186 51.34944318084656,-1.144204558317098 51.3470437065884,-1.144167633428061 51.34873771316475,-1.144152571210615 51.347527573398935,-1.144141712519119 51.34847072053944,-1.14413633973979 51.349112471129885,-1.144108474521806 51.35017369504347,-1.144103184442185 51.347078576385016,-1.144040226084474 51.34913286337735,-1.144035299266902 51.34757852596799,-1.144005636147613 51.35023993803115,-1.143996516408931 51.34951084077941,-1.143957158865123 51.34890294944334,-1.143954277891866 51.349310975521924,-1.143951438587779 51.34916528445699,-1.143937334954572 51.35028259656979,-1.143933831555771 51.347645383994944,-1.143929055792627 51.348841987254595,-1.1439159198155 51.34713213364151,-1.143905710885557 51.34877237092709,-1.143903619019044 51.348460901443396,-1.143873752414366 51.34840175577038,-1.143855162513264 51.34833608505633,-1.143834166620764 51.34913746980413,-1.143831665603008 51.347921217152695,-1.1437386163883 51.347207992022845,-1.143721895513458 51.3506672984304,-1.143709076021083 51.34772871312751,-1.143638268900347 51.34801845182888,-1.143626620547187 51.34760470907805,-1.143617282882746 51.35047588536541,-1.143579231728186 51.350362250751814,-1.143563280478384 51.35030490535053,-1.143545558884141 51.34991975765717,-1.143535204773802 51.350204299721526,-1.143530209915138 51.347857197663394,-1.143517809327692 51.350141176489956,-1.143506129471963 51.34980096338131,-1.143485899433675 51.350038314777194,-1.143394303155614 51.347345880576825,-1.143295372529182 51.34744404329489,-1.143264875275143 51.34769429442993,-1.143106460590058 51.35076156625117,-1.142970200189679 51.350791619425785,-1.142924537875887 51.350401910608916,-1.142907192056859 51.34931716267006,-1.142898636729378 51.34753763178483,-1.142888221970861 51.35033873241286,-1.142842488795257 51.35028673011974,-1.1428235249613 51.35022626601221,-1.142795322377737 51.350177198463456,-1.142780832026207 51.34757712035511,-1.142770980956128 51.35084010415572,-1.142645351098051 51.3501301555084,-1.14263558073759 51.350067603580875,-1.142612047211917 51.347611647063275,-1.142587435393211 51.35002289482325,-1.14257620485503 51.34996324710596,-1.142522307438992 51.347642185668114,-1.142501663746491 51.34991814449924,-1.142472008375048 51.34986558613821,-1.14244049033591 51.34980705717423,-1.142326478702596 51.34773046006081,-1.142219331615346 51.34779928464388,-1.14211714231714 51.34951893650008,-1.142037325384087 51.34782610162637,-1.141727772841377 51.35055457549599,-1.141407654397489 51.3499700552294,-1.141386689760339 51.3498798174562)'::geometry,4326))
         ).geom as geom 
 )
 SELECT (minimum_spanning_tree_calc( 
           minimum_spanning_tree(geom ,  id::text ORDER BY id ASC) )).the_geom as geom 
 FROM cte ) 
select st_buffer(st_union(geom),0.0002) 
from cte2;

I really hope this helps someone. :)

Improve this answer
0
6

Just to add some performance; if you want an MST over a point set, use this:

WITH RECURSIVE
  graph AS (
    SELECT
      dmp.path[1] AS id,
      dmp.geom
    FROM
      ST_Dump('MULTIPOINT(-1.14550839539633 51.349096419770646,-1.145447973240274 51.349051277340756,-1.14539178158296 51.34901358753763,-1.145343972821787 51.348966971200916,-1.145222612554494 51.349086340628475,-1.145157578005767 51.34911251714186,-1.14507017869585 51.3491477407498,-1.144943675904492 51.3472537660354,-1.144919242528779 51.34915120646431,-1.144878766526116 51.347202046136196,-1.144720187793824 51.34919118904576,-1.144683165018423 51.346991976730955,-1.144662816831716 51.34921421827459,-1.144526992373702 51.34878690461452,-1.144511741772054 51.34704541674788,-1.144464001783175 51.349010131013635,-1.144463501471217 51.34706399459523,-1.144462051819252 51.346980230620765,-1.144460629006732 51.34759708434879,-1.144430717433369 51.348946872495574,-1.144407717835232 51.34700119043971,-1.144391229150454 51.34935570032344,-1.144374115025737 51.34873994555251,-1.144345781203042 51.34845885537696,-1.144299396595842 51.34939150931823,-1.144272215351986 51.34875997516049,-1.144261651462714 51.349143941800165,-1.144242439732235 51.348479762737675,-1.144223666010186 51.34944318084656,-1.144204558317098 51.3470437065884,-1.144167633428061 51.34873771316475,-1.144152571210615 51.347527573398935,-1.144141712519119 51.34847072053944,-1.14413633973979 51.349112471129885,-1.144108474521806 51.35017369504347,-1.144103184442185 51.347078576385016,-1.144040226084474 51.34913286337735,-1.144035299266902 51.34757852596799,-1.144005636147613 51.35023993803115,-1.143996516408931 51.34951084077941,-1.143957158865123 51.34890294944334,-1.143954277891866 51.349310975521924,-1.143951438587779 51.34916528445699,-1.143937334954572 51.35028259656979,-1.143933831555771 51.347645383994944,-1.143929055792627 51.348841987254595,-1.1439159198155 51.34713213364151,-1.143905710885557 51.34877237092709,-1.143903619019044 51.348460901443396,-1.143873752414366 51.34840175577038,-1.143855162513264 51.34833608505633,-1.143834166620764 51.34913746980413,-1.143831665603008 51.347921217152695,-1.1437386163883 51.347207992022845,-1.143721895513458 51.3506672984304,-1.143709076021083 51.34772871312751,-1.143638268900347 51.34801845182888,-1.143626620547187 51.34760470907805,-1.143617282882746 51.35047588536541,-1.143579231728186 51.350362250751814,-1.143563280478384 51.35030490535053,-1.143545558884141 51.34991975765717,-1.143535204773802 51.350204299721526,-1.143530209915138 51.347857197663394,-1.143517809327692 51.350141176489956,-1.143506129471963 51.34980096338131,-1.143485899433675 51.350038314777194,-1.143394303155614 51.347345880576825,-1.143295372529182 51.34744404329489,-1.143264875275143 51.34769429442993,-1.143106460590058 51.35076156625117,-1.142970200189679 51.350791619425785,-1.142924537875887 51.350401910608916,-1.142907192056859 51.34931716267006,-1.142898636729378 51.34753763178483,-1.142888221970861 51.35033873241286,-1.142842488795257 51.35028673011974,-1.1428235249613 51.35022626601221,-1.142795322377737 51.350177198463456,-1.142780832026207 51.34757712035511,-1.142770980956128 51.35084010415572,-1.142645351098051 51.3501301555084,-1.14263558073759 51.350067603580875,-1.142612047211917 51.347611647063275,-1.142587435393211 51.35002289482325,-1.14257620485503 51.34996324710596,-1.142522307438992 51.347642185668114,-1.142501663746491 51.34991814449924,-1.142472008375048 51.34986558613821,-1.14244049033591 51.34980705717423,-1.142326478702596 51.34773046006081,-1.142219331615346 51.34779928464388,-1.14211714231714 51.34951893650008,-1.142037325384087 51.34782610162637,-1.141727772841377 51.35055457549599,-1.141407654397489 51.3499700552294,-1.141386689760339 51.3498798174562)'::GEOMETRY) AS dmp
  ),
  tree AS (
    SELECT
      g.geom::GEOMETRY AS vtcs,
      NULL::GEOMETRY AS segment,
      ARRAY[g.id] AS ids
    FROM
      graph AS g
    WHERE
      id = 1
    UNION ALL
    SELECT
      ST_Union(t.vtcs, v.geom),
      ST_ShortestLine(t.vtcs, v.geom),
      t.ids || v.id
    FROM
      tree AS t
      CROSS JOIN LATERAL (
        SELECT
          g.id, g.geom
        FROM
          graph AS g
        WHERE
          NOT g.id = ANY(t.ids)
        ORDER BY
          t.vtcs <-> g.geom
        LIMIT
          1
      ) AS v
    )       
SELECT
  segment
FROM
  tree
WHERE
  segment IS NOT NULL
;

Should be much faster.

Improve this answer
7
  • Yes, @geozelot after adding buffer to the final mst segment output - st_buffer(st_union(ST_SetSRID(segment,4326)),0.0002) I got the exact same result as my solution and was even 6 times faster in execution time. I will be using this for sure. Thanks a lot.
    – George V
    Commented Dec 16, 2021 at 7:36
  • 2
    Creating an MST over a point set is fundamentally different than over a graph (in the stricter sense). This query can only work with the former, for the latter you will need an implementation of one of the common greedy MST algorithms (like in that linked function set)! This query can be translated into a single loop within a function, too, which may be even more performant. On large datasets, the recursive subquery is index enhaced (yet, 'fast' is probably still not exactly the right term to describe the overall speed...)
    – geozelot
    Commented Dec 16, 2021 at 8:45
  • 1
    That is wicked clever!
    – dr_jts
    Commented Dec 16, 2021 at 19:01
  • @dr_jts ,) thanks, I had to come up with this a long time ago to circumvent certain API restrictions...All the `ST_Union's hurt, and I have a C implementation lying around, half done. But no time.
    – geozelot
    Commented Dec 16, 2021 at 20:26
  • Yes, agreed about the pain of ST_Union just to add a point to a MultiPoint. It would be nice if PostGIS had a way to do this directly.
    – dr_jts
    Commented Dec 16, 2021 at 20:30
6

By using the native QGIS Concave hull (alpha shapes) with a Threshold of 0,43 I get a result close of your expectation (but in a more "pointy" shape)

enter image description here

You may try different threshold for a more or less fitted hull, you may also use some buffer to get a more rounded shape afterward

(This is not a postgis answer but as you tag QGIS this is probably acceptable)

Improve this answer
1
  • 2
    Yes, Thankyou , this is far better then what I achieved using ConcaveHull in PostGIS. But @BERA who deleted his comment for unknown reasons had suggested to try Minimum Spanning Tree which worked out quite the way I needed. I will try post the the solution I used.
    – George V
    Commented Dec 14, 2021 at 13:48

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.