1

I'm looking into a task in ArcGIS 10.2 of which I need to discover the two points on a polygon outline where they would be at the greatest distance from each other.

I have looked at ET Geowizards center-line (then extract end nodes) but it doesn't work as the polygon being so narrow seems to confuse ET so the centerline doesn't reach the "tips".

See the image below, the orange dots indicate the points I need. The polygons are always this shape, i.e. long, slim geomtries

enter image description here

I would need to do this for 500 or so polygons so I need something fairly quick. I looked at using the near tool to loop through a point set for each polygon but it takes too long due to multiple calls of the GP tool.

My other thought is, using Python, use the geometery object to go through a point set for each polygon looping through all the possible pairings of vertices to find the pair that are the furthest distance.

Any thoughts?

I have full licenses of ET, ArcGIS Advanced and Spatial Analyst. Also can do a Python or .NET solution.

Many thanks

Improve this question
2
  • How about get MBG and then loop through vertices to find ones that touch the boundary of the MBG polygon (should be very few) and algebraically calculate which are farthest apart (or use near function). All can be done in Python. – Barbarossa Aug 4 '14 at 15:49
  • Open-source solutions are discussed at gis.stackexchange.com/questions/1885/…. @Barbarossa: good idea, but you have to choose the MBG wisely. Rectangles and circles do not work: the convex hull is needed. That requires O(nlog(n)) effort to find and then the "algebraic calculation" could cost up to O(n^2). There are much faster algorithms: the diameter (furthest distance between any two points) of a simple polygon can be found in *linear time. See Preparata & Shamos, Computational Geometry (1985), Corollary 4.2. – whuber Aug 4 '14 at 20:29
1

For each Polygon,

  • Create a Feature Class from the polygon
  • Convert Vertices to Points using, FeatureVerticesToPoints_management
  • Run PointDistance_analysis, in_features and near_features can be the same feature_class
  • Using the Data Access Search Cursor, Sort the Point Distance Table by Distance, descending
  • Read the first record, it will have the FID for the two points farthest apart
Improve this answer
2
  • for 500 polygons, would need to run the Near tool 500 times, initiating a GP tool many times causes any workflow to take a very large amount of time. I'm thinking of this kind of workflow but using Python geometry objects. – Rob Aug 5 '14 at 7:03
  • Yes, you can improve this workflow using the DA cursor and the DistanceTo() geometry method instead of PointDistance. Should be much faster. – klewis Aug 5 '14 at 13:30

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.