Distance to Polygon / MultiPolygon from Point

[lostpebble]

Opened new issue as requested by @rowanwins from #252 .

Currently there is no native way to achieve distance to Polygon (and Multi-Polygon) from a point using Turf.

There was a suggestion in the previous issue to use the vertexes and measure the distance to those, but we end up with the following issue:

In this image, B is clearly the closest point to the polygon, but using the above algorithm we'd end up with point A.

I've come up with the following solution for now:

const distanceKm = pointToLineDistance(point, polygonToLineString(polygon));

if (booleanPointInPolygon(point, polygon)) {
  return  distanceKm * -1;
} else {
  return distanceKm;
}

Using this over an array of Polygons allows me to achieve what I want. (I want to compare the distances of an array of Polygons to a Point and pick out the one which is the closest).

Still need to add support for MultiPolygons (as polygonToLineString doesn't support them) - but that's as easy as splitting the geometry's coordinate array into multiple regular Polygons and finding the shortest distance within that group and choosing the shortest.

Since there is no direct function for Polygons, it makes use of polygonToLineString() to convert them to lines first and run the distance checks on that.

If the point is inside the Polygon, I return the negative value of the distance (how far inside the polygon the point is).

[rowanwins]

Thanks for reopening @lostpebble

[slachtar]

Hi @lostpebble ,
did you come up to a solution for MultiPolygon as this does'nt work in such case.
thank you,

[lostpebble]

Hi @slachtar ,

I did manage to come up with a solution:

import {
  booleanPointInPolygon,
  MultiPolygon,
  Point,
  pointToLineDistance,
  polygon as makePolygon,
  Polygon,
  polygonToLineString,
} from "@turf/turf";

interface IODistanceToPolygonInput {
  point: Point;
  polygon: Polygon | MultiPolygon;
}

// Returns distance in meters (negative values for points inside) from a point to the edges of a polygon
export function distanceToPolygon_direct({ point, polygon }: IODistanceToPolygonInput): number {
  let distance: number;

  if (polygon.type === "MultiPolygon") {
    distance = polygon.coordinates
      .map(coords => distanceToPolygon_direct({ point, polygon: makePolygon(coords).geometry! }))
      .reduce((smallest, current) => (current < smallest ? current : smallest));
  } else {
    if (polygon.coordinates.length > 1) {
      // Has holes
      const [exteriorDistance, ...interiorDistances] = polygon.coordinates.map(coords =>
        distanceToPolygon_direct({ point, polygon: makePolygon([coords]).geometry! })
      );

      if (exteriorDistance < 0) {
        // point is inside the exterior polygon shape
        const smallestInteriorDistance = interiorDistances.reduce(
          (smallest, current) => (current < smallest ? current : smallest)
        );

        if (smallestInteriorDistance < 0) {
          // point is inside one of the holes (therefore not actually inside this shape)
          distance = smallestInteriorDistance * -1;
        } else {
          // find which is closer, the distance to the hole or the distance
          // to the edge of the exterior, and set that as the inner distance.
          distance =
            smallestInteriorDistance < exteriorDistance * -1
              ? smallestInteriorDistance * -1
              : exteriorDistance;
        }
      } else {
        distance = exteriorDistance;
      }
    } else {
      // The actual distance operation - on a normal, hole-less polygon (converted to meters)
      distance = pointToLineDistance(point, polygonToLineString(polygon)) * 1000;

      if (booleanPointInPolygon(point, polygon)) {
        distance = distance * -1;
      }
    }
  }

  return distance;
}

Basically, for multi-polygons we need to iterate over their inner polygons and run the algorithm on each one - and then we pull out the smallest distance (which could also be negative, showing the deepest distance this point is inside the polygon).

Its been a while since I've reviewed this part of my code, but I remember it working without any issues.

Hope that helps!

[slachtar]

@lostpebble thank you, nice work, will try it out for my use case.

[pachacamac]

Seems to work nicely. Thank you @lostpebble !

In case someone sees this and just wants to use it in place without having to recompile turf, this version works with turf ~5.1.6:

// Returns distance in meters (negative values for points inside) from a point to the edges of a polygon
function distanceToPolygon({ point, polygon }) {
  if (polygon.type === "Feature") { polygon = polygon.geometry }
  let distance;
  if (polygon.type === "MultiPolygon") {
    distance = polygon.coordinates
      .map(coords => distanceToPolygon({ point, polygon: turf.polygon(coords).geometry }))
      .reduce((smallest, current) => (current < smallest ? current : smallest));
  } else {
    if (polygon.coordinates.length > 1) {
      // Has holes
      const [exteriorDistance, ...interiorDistances] = polygon.coordinates.map(coords =>
        distanceToPolygon({ point, polygon: turf.polygon([coords]).geometry })
      );
      if (exteriorDistance < 0) {
        // point is inside the exterior polygon shape
        const smallestInteriorDistance = interiorDistances.reduce(
          (smallest, current) => (current < smallest ? current : smallest)
        );
        if (smallestInteriorDistance < 0) {
          // point is inside one of the holes (therefore not actually inside this shape)
          distance = smallestInteriorDistance * -1;
        } else {
          // find which is closer, the distance to the hole or the distance to the edge of the exterior, and set that as the inner distance.
          distance = smallestInteriorDistance < exteriorDistance * -1
            ? smallestInteriorDistance * -1
            : exteriorDistance;
        }
      } else {
        distance = exteriorDistance;
      }
    } else {
      // The actual distance operation - on a normal, hole-less polygon (converted to meters)
      distance = turf.pointToLineDistance(point, turf.polygonToLineString(polygon)) * 1000;
      if (turf.booleanPointInPolygon(point, polygon)) {
        distance = distance * -1;
      }
    }
  }
  return distance
}

[slachtar]

@pachacamac nicely done, very helpful, thank you

[kachkaev]

Thanks for sharing your code @lostpebble and @pachacamac 🙌 I made a typescript version of the function if anyone would want to copy-paste it.

[frastlin]

This is great! I wish it would get merged into turf.
How would you recommend I get the angle of this line from the external point? I need to get the nearest point, distance and angle all in the same function.

[GeekyMonkey]

Here's another solution which is a bit more verbose, but also easier to understand:

export const TurfDistanceToPolygon = (
  featureCollection: turf.FeatureCollection,
  point: turf.Feature<turf.Point>
): number => {
  let bestDistanceKm = Number.MAX_VALUE;

  // Covert single polygon or multi-polygon into consistent array
  for (const f of featureCollection.features) {
    let polygons: any[] = [];
    switch (f.geometry.type) {
      case "MultiPolygon":
        polygons = f.geometry.coordinates;
        break;
      case "Polygon":
        polygons = [f.geometry.coordinates];
        break;
    }

    for (const polygon of polygons) {
      // First item is the outer perimeter
      const outer = polygon[0];
      const outerLine = turf.lineString(outer);

      // Inside outer and not in a hole
      const isInsidePolygon = turf.booleanPointInPolygon(point, turf.polygon(polygon));
      let distanceKm = turf.pointToLineDistance(point, outerLine) * 1000;
      if (isInsidePolygon) {
        distanceKm *= -1;
      }

      // Not in the outer, but could be in one of the holes
      if (!isInsidePolygon) {
        for (const hole of polygon.slice(1)) {
          const holePoly = turf.polygon([hole]);
          const isInHole = turf.booleanPointInPolygon(point, holePoly);
          if (isInHole) {
            const distanceInsideHoleM = turf.pointToLineDistance(point, turf.lineString(hole));
            distanceKm = distanceInsideHoleM * 1000;
          }
        }
      }

      if (distanceKm < bestDistanceKm) {
        bestDistanceKm = distanceKm;
      }
    }
  }

  return bestDistanceKm * 1000;
};

[jfoclpf]

any plans for merging this into turf into a new module @turf/distance-to-polygon ?

[jfoclpf]

@pachacamac or @lostpebble maybe you can do some PRs?

[jfoclpf]

@kachkaev I don't domain TS and turf modules are written in TS

Would you be so kind to open a PR with this new very useful function ?

Check for example packages/turf-point-to-line-distance

You would only need to adapt this into a new folder packages/turf-point-to-polygon-distance

The TURF community thank you so very much ;)

[kachkaev]

Hi @jfoclpf! Glad that you are open to accept this change! I don’t have a lot of extra capacity in the coming weeks, so happy for you copy-paste my solution into a PR (hope that it does not need much tweaking). If anyone else reading this would like to volunteer, feel free to step up! 🙌

[jfoclpf]

Just for the clarification, I am not the maintainer of the package, just an end user :)

[smallsaucepan]

Once #2717 (which includes fixes to pointToLineDistance) is merged will look into bringing one of the implementations above into Turf.

[jampy]

@GeekyMonkey I think in your solution both distanceKm = lines should be a division, not a multiplication:

      let distanceKm = turf.pointToLineDistance(point, outerLine) / 1000;

            distanceKm = distanceInsideHoleM / 1000;

[smallsaucepan]

@kachkaev @lostpebble @pachacamac @jampy @GeekyMonkey Would one of you like to take the lead on a PR for this?

[pachacamac]

@smallsaucepan I can probably do that. What would be the preferred way? I'm thinking new package similar to https://github.com/Turfjs/turf/tree/master/packages/turf-point-to-line-distance but point-to-polygon-distance?

[smallsaucepan]

That sounds great @pachacamac. Really appreciate you taking a look!

We could go a couple of ways:

1. add a new package for every permutation we need e.g. point-to-polygon-distance, (imagine later on) line-to-polygon-distance, polygon-polygon, etc. Do other variations even make sense?
2. expand the existing turf-distance package so it can get the distance between anything we throw at it, rather than just two points

What are your thoughts? Pros and cons that you can see?

[pachacamac]

@smallsaucepan for easier testability, readability (not a fan of big if/case blocks) and maybe tree-shakeablity I think I would much prefer the first option.
Also given the nature that turf already has a lot of packages I assumed this would be the preferred way of doing things.
Not sure if it makes sense but one could, afterwards, create a meta-distance package that does what you describe in the second option by utilizing the other distance packages. Wdyt?

[smallsaucepan]

Happy to go with option 1. Only wanted to go through the thought process first to make sure we aren't over splitting the namespace. Looking through old issues I couldn't find anything requesting nearestLineToWhatever or nearestPolygonToWhatever anyway, so three nearestPointToWhatever functions isn't so bad.

Looking at the original use case I've realised it's really asking for nearestPointToPolygon, rather than only distanceToPolygon. Would you be ok to add the pair - pointToPolygonDistance and nearestPointToPolygon?

When you get under way, I'm not sure how up to date scripts/create-new-module is. You may be best off copying an existing package sideways.

[pachacamac]

@smallsaucepan please have a look #2735

This should be the basic stuff, with tests (and some additional fixes for bugs discovered by the tests).

Also thanks to everyone else who contributed! Feel free to add yourselves to the contributors. @kachkaev @lostpebble @jampy @GeekyMonkey