JTS : distance between two geometries bypassing another one in the middle

Question

Let's say that I want to calculate the distance between two geometries with JTS, but there is another one in the middle that I can't go across (as if it was a wall). It could look like this :

I wonder how I could calculate that.

In this case, these shapes geom1 and geom2 are 38.45 meters away, as I calculate it straight away. But if I don't want go across that line, I should surround it by the Northern sides, and distance would probably be more than 70 meters away.

We can think that we could have a line a polygon or whatever in the middle.

I wonder if there is any built in function in JTS, or some other thing I could you. I guess if there is anything out there, I should check for some other workaround, as trying to solve complex routing problems is beyond my knowledge.

This is the straight away piece of code using JTS for the distance, which would not still take into account the Geometry in the middle.

  import org.apache.log4j.Logger;
  import com.vividsolutions.jts.geom.Geometry;
  import com.vividsolutions.jts.io.ParseException;
  import com.vividsolutions.jts.io.WKTReader;

  public class distanceTest {

  private final static Logger logger = Logger.getLogger("distanceTest");

  public static void main(String [] args) {
    //Projection : EPSG:32631
    // We build one of the geometries on one side
    String sGeom1="POLYGON ((299621.3240601513 5721036.003245114, 299600.94820609683 5721085.042327096, 299587.7719688322 5721052.9152064435, 299621.3240601513 5721036.003245114))";
    Geometry geom1=distanceTest.buildGeometry(sGeom1);

    // We build the geometry on the other side
    String sGeom2=
            "POLYGON ((299668.20990794065 5721092.766132105, 299647.3623194871 5721073.557249224, 299682.8494029705 5721049.148841454, 299668.20990794065 5721092.766132105))";     
    Geometry geom2=distanceTest.buildGeometry(sGeom2);

    // There is a geometry in the middle, as if it was a wall
    String split=
            "LINESTRING (299633.6804935104 5721103.780167559, 299668.99872434285 5720999.981241705, 299608.8457218057 5721096.601805294)";      
    Geometry splitGeom=distanceTest.buildGeometry(split);

    // We calculate the distance not taking care of the wall in the middle
    double distance = geom1.distance(geom2);
    logger.error("Distance : " + distance);
}

  public static Geometry buildGeometry(final String areaWKT) {
        final WKTReader fromText = new WKTReader();
        Geometry area;
        try {
          area = fromText.read(areaWKT);
        }
        catch (final ParseException e) {
          area = null;
        }
        return area;
      }

}

Answer 1

This works for SQL, I hope you have the same or similar methods at your disposal.

In theory, in this instance you could create a ConvexHull containing the two geometries AND your "unpassable" geometry.

Geometry convexHull = sGeom1.STUnion(sGeom2).STUnion(split).STConvexHull();  

Next, extract the border of the ConvexHull to a linestring (use STGeometry(1) - I think).

Geometry convexHullBorder = convexHull.STGeometry(1);

EDIT: Actually, with Geometry you can use STExteriorRing().

Geometry convexHullBorder = convexHull.STExteriorRing();

Lastly, pick one of your geometries, and for each shared point with the border of the ConvexHull, walk the border from that point until you reach the first point that is shared with the other geometry, adding the distance between the current and previous point at each point reached. If the second point you hit belongs to the same geometry as you are walking from, exit the loop and move on to the next to reduce time. Repeat for the second geometry.

When you've done this for all possibilities, you can simply take the minimum value (there will be only two - Geom1 to Geom2 and Geom2 to Geom1) and there is your answer.

Of course, there are plenty of scenarios in which this is too simple, but if all scenarios simply have one "wall" in them, it will work.

Some ideas of where it will not work:

• The "wall" is a polygon, fully enveloping both geometries - but then how would you ever get there anyway?
• There are multiple "walls" which do not intersect each other (gaps between them) - this method will ignore those passes in between "walls". If however multiple "walls" intersect, creating essentially one larger "wall" the theory will still work.

Hope that makes sense?

EDIT: Actually, upon further reflection there are other scenarios where the ConvexHull approach will not work, for instance the shape of your polygon could cause the ConvexHull to not produce the shortest path between geometries and your "walls". This will not get you 100% accuracy.