#! /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 ( )