5

I want to find an PostGIS algorithm to unite points of two geometries that are "near" to each other.

That is: I want a function, that takes as input two geometries, and returns 1 geometry, that consist of points of first geometry, second geometry, and points that are in specified radius of both geometries.

Currently I am using such function for this (tolerance radius is 2 meters):

SELECT ST_AsText( ST_Buffer( ST_Union( ST_Buffer( ST_GeomFromText( 'POLYGON ((0 0, 0 4.5, -2 4.5, -2 5.5, 0 5.5, 0 10, 1 10, 1 0, 0 0))', 3301 ), 2 ), ST_Buffer( ST_GeomFromText( 'POLYGON ((2 5, 5 8, 5 2, 2 5))', 3301 ), 2 ) ) , -2) );

It works reasonably well to unite points of two geometries, that are near to each other.

However, it has side effects. For example:

Input geometries:

Input geometries

Resulting geometry:

Resulting geometry

As can be seen from picture, some extra area is added to the "blue" geometry where the obtuse angles are. This is so, because using

ST_Buffer(ST_Buffer(geom, tolerance), -tolerance) 

adds extra space to places where there are obtuse angles.

Is there an algorithm that would produce my asked result? Exact nature of how the two geometries are "glued" to each other is not so important. Buffering algorithm leaves smooth curve, but something like this would also be valid result (hand-drawn, I tried to add points that are in distance of 2 meters from both geometries):

example of valid result

If there are many algorithms, the fastest one will best suit my needs. But for comparison, slower algorithms will also be welcome (up-voted), if they excel by some other criteria.

2 Answers 2

4

I will try to document things, that I already have tried. Maybe this will help others to provide good ideas.

I read manual about ST_Buffer function: ST_Buffer

There are interesting options about how the ST_Buffer function works:

  • 'quad_segs=#' : number of segments used to approximate a quarter circle (defaults to 8).
  • 'endcap=round|flat|square' : endcap style (defaults to "round", needs GEOS-3.2 or higher for a different value). 'butt' is also accepted as a synonym for 'flat'.
  • 'join=round|mitre|bevel' : join style (defaults to "round", needs GEOS-3.2 or higher for a different value). 'miter' is also accepted as a synonym for 'mitre'.
  • 'mitre_limit=#.#' : mitre ratio limit (only affects mitered join style). 'miter_limit' is also accepted as a synonym for 'mitre_limit'.

I tried to use "join=mitre" when doing a negative buffer. Code:

SELECT ST_AsText(
  ST_Buffer(
  ST_Union(
  ST_Buffer(
  ST_GeomFromText(
  'POLYGON ((0 0, 0 4.5, -2 4.5, -2 5.5, 0 5.5, 0 10, 1 10, 1 0, 0 0))', 3301 
 ), 2 
 )
 , 
 ST_Buffer(
  ST_GeomFromText(
  'POLYGON ((2 5, 5 8, 5 2, 2 5))', 3301 
 ), 2 
 ) 
 )
  , -2, 'join=mitre'
 ) 
);

Result is here:

Result_round_mitre

Not quite what I expected.

Then I tried:

SELECT ST_AsText(
  ST_Buffer(
  ST_Union(
  ST_Buffer(
  ST_GeomFromText(
  'POLYGON ((0 0, 0 4.5, -2 4.5, -2 5.5, 0 5.5, 0 10, 1 10, 1 0, 0 0))', 3301 
 ), 2, 'join=mitre'
 )
 , 
 ST_Buffer(
  ST_GeomFromText(
  'POLYGON ((2 5, 5 8, 5 2, 2 5))', 3301 
 ), 2, 'join=mitre'
 ) 
 )
  , -2, 'join=mitre'
 ) 
);

Interestingly, this returned the original geometry:

Result_mitre_mitre

Using bevel join gave even more unnatural results. It seems to me, that playing with the join type is not enough :)

EDIT: I did one more test and maybe I should reconsider my previous statement. Mitre joining has some interesting properties.

Different input geometries:

Different input geometries

Result using mitre join:

Result using mitre join

As can be seen from the graphics, the shape of joined geometry depends on the size of angle of triangle. If the input geometries were parallel, mitre joining would give desired result.

This needs more testing.

EDIT2: No, mitre joining is not a viable option. Test case:

Initial geometries:

Initial geometries

Result:

After mitre joining

On the left side, the initial geometry has changed shape. So no, mitre joining is not the answer to this problem.

EDIT3: Co-worker added interesting variation:

SELECT ST_AsText(
  ST_Buffer(
  ST_Union(
  ST_Buffer(
  ST_GeomFromText(
  'POLYGON ((0 0, 0 4.5, -2 4.5, -2 5.5, 0 5.5, 0 10, 1 10, 1 0, 0 0))', 3301 
 ), 2 , 'join=mitre'
 )
 , 
 ST_Buffer(
  ST_GeomFromText(
  'POLYGON ((2 5, 5 8, 5 2, 2 5))', 3301 
 ), 2 , 'join=mitre'
 ) 
 )
  , -2, 'join=mitre mitre_limit=1.4141'
 ) 
);

Mitre join 4

This is very close to what I asked in the first post. I will consider using this.

About parameter "mitre-limit=1.4141":

It is 1/sin(a/2), where a is angle between two consecutive segments. 1.4141 means, that when angle is 90 degrees or less, join=bevel will be used instead of join=mitre.

2

ST_ConcaveHull should solve this.

2
  • Very interesting. However, ST_ConcaveHull will connect the two geometries even if they are farer from each other, than tolerance apart. Of course, I could first check the distance of two geometries and then connect them if they are less than tolerance apart. Needs thinking. Other problem, ST_ConcaveHull may insert discrepancies on the sides that are not being connected. See my first post - blue geometry gets some extra "area". But I guess if target_precent is sufficiently low, it should do the trick. But then I need to know the target_precent in advance for my application :)
    – Rauni
    Feb 8, 2013 at 15:24
  • I will still accept Your answer as being best, because it is closest to my original intent that I have found.
    – Rauni
    Feb 8, 2013 at 15:24

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.