#! /usr/bin/env python
#
def polygon_diameter ( n, v ):

#*****************************************************************************80
#
## POLYGON_DIAMETER computes the diameter of a polygon.
#
#  Discussion:
#
#    The diameter of a polygon is the maximum distance between any
#    two points on the polygon.  It is guaranteed that this maximum
#    distance occurs between two vertices of the polygon.  It is
#    sufficient to check the distance between all pairs of vertices.
#    This is an N^2 algorithm.  There is an algorithm by Shamos which
#    can compute this quantity in order N time instead.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    17 October 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer N, the number of vertices of the polygon.
#
#    Input, real V(2,N), the vertices.
#
#    Output, real DIAMETER, the diameter of the polygon.
#
  import numpy as np

  diameter = 0.0

  for i in range ( 0, n ):
    for j in range ( i + 1, n ):
      diameter = max ( diameter, \
        np.sqrt ( ( v[0,i] - v[0,j] ) ** 2 + ( v[1,i] - v[1,j] ) ** 2 ) )

  return diameter

def polygon_diameter_test ( ):

#*****************************************************************************80
#
## POLYGON_DIAMETER_TEST tests POLYGON_DIAMETER;
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    17 October 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform
  from r8mat_transpose_print import r8mat_transpose_print

  n = 4
  diameter_exact = 2.0
  v = np.array ( [ \
    [ 1.0, 2.0, 1.0, 0.0 ], \
    [ 0.0, 1.0, 2.0, 1.0 ] ] )

  print ( '' )
  print ( 'POLYGON_DIAMETER_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  POLYGON_DIAMETER computes the diameter of a polygon.' )

  r8mat_transpose_print ( 2, n, v, '  The polygon vertices:' )

  diameter = polygon_diameter ( n, v )

  print ( '' )
  print ( '  Diameter ( computed ) %g' % ( diameter ) )
  print ( '  Diameter ( exact )    %g' % ( diameter_exact ) )
#
#  Terminate.
#
  print ( '' )
  print ( 'POLYGON_DIAMETER_TEST' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  polygon_diameter_test ( )
  timestamp ( )