8

I have a PostGIS database of polygons representing regions in a 2D space and I'm trying to find a way to generate the closest square of a given size to a given region that doesn't intersect with any of the existing regions. The size of the square is known in advance, its specific orientation doesn't matter, and all the relevant geometries are polygons. To make it more concrete, the regions in question represent search areas for an autonomous vehicle.

What I'm trying to do is identify a safe area for that vehicle to wait after searching a given region that doesn't interfere with any of the other regions or the region it just searched so that all of those regions are free to be searched by other vehicles.

I'm new to PostGIS, so this may just be a problem of not knowing the right search terms to find the correct built-in function. Obviously, I could generate the desired square with a center gradually further and further away and check for intersections until I find one that doesn't intersect, but I'm hoping there is a more efficient way.

Vince
  • 20,017
  • 15
  • 45
  • 64
teddybouch
  • 81
  • 5
  • Could you please clarify your query? Closest square to what object or location? Can the square be rotated or must its sides be parallel to the coordinate axes? Is your "square" a polygon or is it just its polyline boundary? Do you specify its size in advance or could its size vary? – whuber Aug 11 '21 at 17:09
  • 1
    Thank you for asking for the clarification - I edited the main question since I tend to find that most helpful when I look at questions others have asked on Stack Exchange. Does that help? – teddybouch Aug 11 '21 at 17:49
  • 3
    This appears closely related to https://gis.stackexchange.com/questions/27303 and https://gis.stackexchange.com/questions/140217. For efficiency, though, consider approximate solutions. For instance, if you compute the distance grid relative to all polygons and limit it to all values exceeding the square's side times sqrt(1/2), the closest grid cell to your polygon will be the center of a disc than can enclose the square (in any orientation). These grid operations are fast, especially, when you use a coarse grid. Alternatively, find the nearest point outside a buffer of all other polys. – whuber Aug 11 '21 at 18:19
  • 5
    Similiar to @whuber's grid approximation and easily applicable within PostGIS, you could prepare an inverse area geometry, sliced into pieces with shortest lines between your regions, pre-calculate their ST_MaximumInscribedCircle (PG 3.1.0), and (K)NN search the closest one having a radius equal or greater than the squares diagonale. This assumes a more or less static regions data set, or a thorough automated pre-processing step. – geozelot Aug 12 '21 at 07:52

1 Answers1

1

This is a very interesting question. I would try the following calculation strategy:

  1. Start point is a table of polygons ..forests. Region of interest is the space between.

  2. Create the negative polygon shape of your polygon scene, which is the symmetric difference of the envelope + buffer and the union of the polygon scene.

  3. Calculate the straight skeleton for the negative shape.

  4. Assuming that the points between the surrounding polygons and the skeleton vertices is convex decomposed, calculate the shortest distance between each polygon vertex of the forest scene and the skeleton vertices. The shortest distance is the minimal radius of a circle you can bring between the polygons. It marks some kind of a search space.

  5. Find the position between two skeletons vertices, where the circle will fit your radius constraints by a linear calculation. This should be possible, because the skeleton is convex decomposed.

For the last topic I'm not sure because you could find fare more places due to the asymmetry in the the linear progression of the skeleton neighboring polygon segments.

huckfinn
  • 3,583
  • 17
  • 35