PostGIS – Creating Polygon Around Points Without Gaps

concave hullextentspolygon-creationpostgispostgresql

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)

Best Answer

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. :)

Related Question