5

We have a problem that we are not quite sure how to approach, we have a number of polygons contained inside a larger bounding polygon, We need to expand these internal polygons as much as possible but only until a single edge touches the containing polygon.

I hope a diagram will help with my explanation:

enter image description here

The polygons in red can be assumed as already created, the dotted polygons in green indicate the final polygon that we want to create (enlarged just enough until one side touches the walls of the bounding polygon).

This will be run on big data (hundreds of millions of polygons with hundreds of millions of inner polygons) as such efficiency is one problem we are facing. In code this is reasonably trivial, however its not feasible for the dataset we have.

We have a large cluster setup that can process Geospatial SQL efficiently which we intend to use for this task but other than arbitrarily passing a value to an expand function we aren't quite sure how to do this intelligently over massive amounts of data.

I believe we need to scale the polygon using ST_Expand and stop when ST_Intersects on the main polygon is true - I just have no idea how to do that in a single SQL call.

  • 2
    Do you want the polygons to be expanded in the same distance in all directions, according to the closest distance to the nearest containing polygon. If so, you should use ST_Buffer. I mention this because rectangles get curved edges from buffer, but not from ST_Expand. Depending on your answer to this, I think this can be done by finding the distance to the nearest containing polygon (which will be fast, as you can use a spatial index with ST_Contains) and then buffering, expanding, growing your polygons in some way, again, depending on your answer – John Powell Aug 28 '18 at 8:15
  • Yes ideally the same but this doesn't have to be 100% accurate if there is a more efficient way. So you mean find the distance to the nearest edge of the surrounding polygon and then use this as the metric to use ST_Expand / ST_Buffer? Sounds like a good approach - ill take a look! – Voycey Aug 29 '18 at 4:17
  • Also, you will want to use ST_Exteriorring in conjunction with ST_Distance, as, otherwise, for polygons inside other polygons, the distance will be given as 0. You will also want to find the closest distance grouped by contained polygon, as, from you diagram, you could have several closest distances for each polygon to each containing polygon. Maybe I should post all this as an answer? – John Powell Aug 29 '18 at 19:41
  • If there is some proof of concept you can provide go ahead and ill test it and accept it :) I'm running some tests on what you said above today! – Voycey Aug 30 '18 at 1:14
  • 1
    I have put a general proof of concept up, untested of course, though I realize from writing it that I have probably asked more questions than answered. – John Powell Aug 31 '18 at 13:53
5
  1. Find containing polygon
  2. Find closest distance between each contained polygon and it's containing polygon
  3. Buffer the contained polygons by the distance found in 2.

It is assumed, in 1, that there is only one containing polygon. If not, it becomes a bit more complicated, and you'll have to do a group by/distinct on or a partition by in order to get the closest from several possible containing polygons..

There is one immediate gotcha to be aware of here, which is that if you use ST_Distance(geom1, geom2) and geom1 contains geom2, you will get 0. So, in order to determine the distance by which to grow your contained polygons, you should use ST_Exteriorring, which will return a Linestring and give sensible results for ST_Distance.

SELECT ST_Distance(ST_Exteriorring(geom1), geom2).

Putting it all together, and labelling (aliasing) tables as from your diagram as polygons_outer (a) and polygons_inner (b):

WITH 
    to_buffer(distance, b.id) AS (
SELECT
   ST_Distance(ST_Exteriorring(a.geom), b.geom),
   b.id
 FROM 
    polygons_outer a, polygons_inner b 
 WHERE ST_Contains(a.geom, b.geom)
 UPDATE polygons_inner b
   SET geom = ST_Buffer(geom, distance)
  FROM to_buffer tb
  WHERE b.id = tb.id;

This also assumes that you want buffer (grow equally in all directions, according to the nearest distance) or if you want to grow all sides until they reach the containing polygon. This latter situation is potentially much more complicated and would involve dumping your polygons to linestrings, finding the closest distance in both the x and y directions -- assuming they are vertically/horizontally aligned -- and using ST_Expand.

  • This looks great John! I'll be testing this next week and I'll let you know how I get on! The sides only need to grow until one edge reaches the containing polygon which should work fine here I think! – Voycey Sep 2 '18 at 2:02
  • I'm still trying to test this John - not forgotten about it, we are having some problems with generating the first polygons but I think that should be sorted in a couple of weeks then I can try this at scale :) – Voycey Sep 19 '18 at 20:49
  • No worries at all. Let me know if it needs some tweaking. – John Powell Sep 20 '18 at 10:08

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.