topic maximum distance from a point within a polygon in Spatial Data Science Questions

maximum distance from a point within a polygon

WilliamEllis1 — Sat, 02 Apr 2016 23:08:28 GMT

Hello,

I'm looking for a way to determine the maximum straightline distance from a point within the interior of an irregular polygon to the polygon's edge (any point along the edge) without every leaving the polygon's interior.

If anyone is out there that can help me with this, I'd greatly appreciate it.

Thanks,

William

Re: maximum distance from a point within a polygon

DanPatterson_Retired — Sat, 02 Apr 2016 23:31:24 GMT

This is sometimes called 'polygon fetch' and in some situations, the polygon diameter. Thisis different that the medial axis (can have deviations in the line angle etc) or straight skeleton. Perhaps GME' calculate fetch in polygon will work GME | SpatialEcology.Com

Re: maximum distance from a point within a polygon

WilliamEllis1 — Sun, 03 Apr 2016 00:16:00 GMT

I'll give it a try. Thank you, Dan.

Re: maximum distance from a point within a polygon

JoshuaBixby — Thu, 07 Apr 2016 18:12:12 GMT

For a bit more context, or at least to read an interesting discussion, you should check out a StackExchange thread started by Dan Patterson a couple years back: Antipodal distance (or polygon fetch or polygon diameter) for concave polygons.

Unlike calculating the minimum distance or minimum straightline distance, calculating the maximum straightline distance from a point within a polygon to the polygon's boundary is more involved.

Looking at a simple concave polygon and point example:

Polygon diameter has a common definition in mathematics (Wolfram MathWorld Glossary😞

Polygon Diameter
The diameter of a polygon is the largest distance between any pair of vertices. In other words, it is the length of the longest polygon diagonal (e.g., straight line segment joining two vertices).

For the example above, the polygon diameter can be represented by either of two pairs of vertices: (POINT(0 0), POINT(400 200)) or (POINT(400 0), POINT(0 200). Note that the definition of polygon diameter doesn't speak to convexity or concavity. For concave polygons, it is not uncommon to have the polygon diameter cross over the polygon boundary.

Fetch or fetch length has its origins in the earth sciences, i.e., geography, hydrology, meteorology, etc.... (National Weather Service Glossary😞

Fetch
...
2. In hydrologic terms,
The effective distance which waves have traversed in open water, from their point of origin to the point where they break.

The concept of fetch is fairly straightforward, but computing fetch length isn't as straightforward as polygon diameter. At its most basic, fetch length depends on the shape of the water body surface (polygon) and the direction of wind. In reality other factors like landscape topography and water body bathymetry play into where exactly a wave starts. Typically what is called fetch length is really a potential or idealized fetch length based only on the surface shape of a water body and a given wind direction. Furthermore, since fetch is wind dependent, there is no single fetch length for a water body. Some people use the term fetch length in a singular sense, but what they are typically referring to is the maximum value of all fetch lengths for a water body.

In terms of mathematics or computational geometry, I am not sure what the equivalent term is for maximum potential fetch length of a water body. There aren't a lot of tools that compute fetch length. As Dan Patterson pointed out in an earlier comment, the GME geom.polygonfetch tool is commonly used by folks. As the tool's documentation states, it uses a brute force algorithm "evaluating the lines created by connecting all pairs of non-neighboring vertices and retaining the longest line that does not cross any interior or exterior boundaries of the polygons."

It is important to note that geom.polygonfetch doesn't do densification before computing maximum fetch, or what it just calls polygon fetch. For the example above, geom.polygonfetch will return a line represented by the (POINT(0 0), POINT(400 0)) pair of vertices, but there is a longer maximum fetch represented by (POINT(0 133), POINT(400 0)). The problem is there isn't a vertex at POINT(0 133), so the tool doesn't know there is a longer straightline distance within the polygon that doesn't cross a boundary.

All of that said, polygon diameter and maximum potential fetch length aren't what you are after here. Both are properties of a given polygon, not a spatial relationship between a polygon and another geometry. For points in polygons, a Hausdorff distance line will give the longest straightline from a point to the boundary of a polygon. The Hausdorff distance doesn't speak to convexity or concavity, so it is more similar to polygon diameter than maximum potential fetch length.

Even if your polygons were convex or crossing polygon boundaries wasn't an issue, very few geospatial products have implemented Hausdorff algorithms. In short, you are going to be rolling your own solution. Googling for "maximum distance point in polygon" yields some links to good discussions. Most of what is discussed involves brute force approaches like the geom.polygonfetch tool.

I am an engineer by training, and by mindset, so sometimes I ask myself what answer can I live with rather than what the perfect or correct answer is in theory. One approach you could try, knowing it may miss the true answer:

Determine polygon diameter
Create lines every x degrees originating from point and of length polygon diameter.
Intersect lines on polygon
Return maximum of first line segment from lines.

Re: maximum distance from a point within a polygon

DanPatterson_Retired — Thu, 07 Apr 2016 19:31:22 GMT

Nice summary Joshua. Other areas of application would include robotics and anything doing with line of sight (think of your home alarm system). The skeleton is more common in robotics (make something move within a room without scrapping a wall. A cautionary note about 'fetch' is that it generally pays no attention to the Z axis. Wind blowing across a sandbar really isn't going to be affected by it to any comparative degree. One can bring in visibility analysis into this as a surrogate. Assume a flat surface (zero elevation) extrude some walls (like a mountain), run the visibility analysis with any desired OFFSETA and OFFSETB and the visibility will give you sight lines. From there you can use thinning algorithms to thin the areas down to something that can be used to generate lines.

Re: maximum distance from a point within a polygon

JoeStefanoni — Fri, 24 Apr 2020 12:52:56 GMT

I would like to know if there is an ArcGIS tool to calculate the maximum distance from the centroid of a polygon to the polygon edge. Specifically I'm working with a parcel dataset.

Re: maximum distance from a point within a polygon

JoshuaBixby — Fri, 24 Apr 2020 16:41:33 GMT

Dan might know of recent developments, but I don't think anything has changed on this issue in the past 4 years, i.e., there is still no ArcGIS geoprocessing tool that calculates what you are seeking.

UPDATE: One thing that has changed is that SciPy now includes scipy.spatial.distance.directed_hausdorff — SciPy v1.4.1 Reference Guide . You can use FeatureClassToNumPyArray—Data Access module | Documentation to dump vertices to NumPy arrays and then use SciPy to calculate the Hausdorff distance.