Antipodal Distance Demo

This is a variant of the antipodal distance which allows you to isolate points pairs within a convex polygon forming the longest path from one side to the other side of a polygon without following the polygon edge.  If this algorithm were applied to concave polygons, then there would be no guarantee that the formed vector would be fully contained within the polygon.

Other variants of the antipodal distance can consider travel along the polygon edges, and there are many examples on the web.  Enjoy
'''
AntipodalDistDemo.py
Author
  Dan Patterson
  obidangis@gmail.com
  Dan_Patterson@carleton.ca
Purpose:
  To calculate the largest distance between the points the form
  a convex hull.
Requirements:
  - A list of list of xy pairs eg [ [1,1],[3,4,[2,6], [1,1] ]
    first and last points must be the same to close the polygon
  - numpy
Limitations:
  Does not account for donuts or multi-part polygons
'''
#-------------------------------------------------------------------
def antipodalDistance(pnts):
  '''
  Calculates the largest distance between the points
  that make up a convex hull
  Requires: a list of list of xy pairs eg [[1,1],[3,4,[2,6],[1,1]]
  '''
  N = len(pnts)
  #thePairs = itertools.combinations(range(N), 2)   #pairs of numbers in the range N
  distList = []
  edgeList = []
  dmax = 0.0
  for i in range(0,N-2):
    for j in range(i+1, N-1):
      dist = numpy.math.hypot(pnts[i][0] - pnts[j][0], pnts[i][1] - pnts[j][1])
      diff = abs(i - j)
      if (diff == 1) or diff == abs(N-2) :
        edgeList.append( [dist, [i,j]] )
      else:
        distList.append( [dist, [i,j]] )   # compute the lower triangle of the matrix
        #distList.append( [dist, [j,i]] )   # form the upper triangle of the matrix
       
  distList.sort()
  distList.reverse()
  edgeList.sort()
  dmax = distList[0]
  return [dmax, distList, edgeList]
#---------------------------------------------------------
if __name__ == "__main__":
  import numpy
 
  pnts = [ [0,0], [0,1], [1,4],[3,5],[5,4],[4,1],[0,0] ]  # a closed-loop convex polygon
  #pnts = [ [0,0], [2,1], [1,4],[3,5],[5,4],[4,1],[0,0] ]  # a closed-loop concave polygon
  dmax, distList, edgeList = antipodalDistance(pnts)
  print "\ndmax and index pair ", dmax
  print "\nDistList"
  for i in distList:
    print i
  print "\nedgeList:"
  for i in edgeList:
    print i