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

#*****************************************************************************80
#
## POLYGON_IS_CONVEX determines whether a polygon is convex.
#
#  Discussion:
#
#    If the polygon has less than 3 distinct vertices, it is
#    classified as convex degenerate.
#
#    If the polygon "goes around" more than once, it is classified
#    as NOT convex.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    18 October 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Peter Schorn and Frederick Fisher,
#    Testing the Convexity of a Polygon,
#    Graphics Gems IV, 
#    edited by Paul Heckbert,
#    AP Professsional, 1994.
#
#  Parameters
#
#    Input, integer N, the number of vertices.
#
#    Input, real V(2,N), the coordinates of the vertices of the polygon.  
#
#    Output, integer VALUE:
#    -1, the polygon is not convex
#     0, the polygon has less than 3 vertices it is "degenerately" convex
#     1, the polygon is convex and counterclockwise
#     2, the polygon is convex and clockwise.
#
  import numpy as np
  from i4_wrap import i4_wrap
  from r8_atan import r8_atan

  RAD_TO_DEG = 180.0 / np.pi

  CONVEX_CCW = 1
  CONVEX_CW = 2
  DEGENERATE_CONVEX = 0
  NOT_CONVEX = -1
  tol = 1.0

  exterior_total = 0.0
#
#  If there are not at least 3 distinct vertices, we are done.
#
  if ( n < 3 ):
    value = DEGENERATE_CONVEX
    return value

  sense = 0.0
#
#  Consider each polygonal vertex I.
#
  for i in range ( 0, n ):

    ip1 = i4_wrap ( i + 1, 0, n - 1 )
    ip2 = i4_wrap ( i + 2, 0, n - 1 )

    dot =   ( v[0,ip2] - v[0,ip1] ) * ( v[0,i] - v[0,ip1] ) \
          + ( v[1,ip2] - v[1,ip1] ) * ( v[1,i] - v[1,ip1] )

    cross =   ( v[0,ip2] - v[0,ip1] ) * ( v[1,i] - v[1,ip1] ) \
            - ( v[0,i]   - v[0,ip1] ) * ( v[1,ip2] - v[1,ip1] )

    angle = r8_atan ( cross, dot )
#
#  See if the turn defined by this vertex is our first indication of
#  the "sense" of the polygon, or if it disagrees with the previously
#  defined sense.
#
    if ( sense == 0.0 ):

      if ( angle < 0.0 ):
        sense = -1.0
      elif ( 0.0 < angle ):
        sense = +1.0

    elif ( sense == 1.0 ):

      if ( angle < 0.0 ):
        value = NOT_CONVEX
        return value

    elif ( sense == -1.0 ):

      if ( 0.0 < angle ):
        value = NOT_CONVEX
        return value
#
#  If the exterior total is greater than 360, then the polygon is
#  going around again.
#
    angle = r8_atan ( -cross, -dot )

    exterior_total = exterior_total + angle

    if ( 360.0 + tol < abs ( exterior_total ) * RAD_TO_DEG ):
      value = NOT_CONVEX
      return value

  if ( sense == 1.0 ):
    value = CONVEX_CCW
  elif ( sense == -1.0 ):
    value = CONVEX_CW

  return value

def polygon_is_convex_test ( ):

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

  n_max = 10
  test_num = 11

  print ( '' )
  print ( 'POLYGON_IS_CONVEX_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  POLYGON_IS_CONVEX determines if a polygon is convex.' )

  for test in range ( 0, test_num ):

    if ( test == 0 ):
      n = 1
      v = np.array ( [ \
        [ 0.0 ], \
        [ 0.0 ] ] )
      title = '  A point:'
    elif ( test == 1 ):
      n = 2
      v = np.array ( [ \
        [ 0.0, 1.0 ], \
        [ 0.0, 2.0 ] ] )
      title = '  A line:'
    elif ( test == 2 ):
      n = 3
      v = np.array ( [ \
        [ 0.0, 2.0, 1.0 ], \
        [ 0.0, 0.0, 0.0 ] ] )
      title = '  A triangle:'
    elif ( test == 3 ):
      n = 3
      v = np.array ( [ \
        [ 0.0, 1.0, 0.0 ], \
        [ 0.0, 0.0, 2.0 ] ] )
      title = '  A CCW triangle:'
    elif ( test == 4 ):
      n = 3
      v = np.array ( [ \
        [ 0.0, 0.0, 1.0 ], \
        [ 0.0, 2.0, 0.0 ] ] )
      title = '  A CW triangle:'
    elif ( test == 5 ):
      n = 4
      v = np.array ( [ \
        [ 1.0, 2.0, 3.0, 0.0 ], \
        [ 0.0, 0.0, 1.0, 1.0 ] ] )
      title = '  Polygon with large angle:'
    elif ( test == 6 ):
      n = 5
      v = np.array ( [ \
        [ 0.0, 0.5, 1.0, 1.0, 0.0 ], \
        [ 0.0, 0.5, 0.0, 1.0, 1.0 ] ] )
      title = '  Polygon with huge angle:'
    elif ( test == 7 ):
      n = 5
      v = np.zeros ( [ 2, n ] )
      for i in range ( 0, n ):
        angle = i * 4.0 * np.pi / float ( n )
        v[0,i] = np.cos ( angle )
        v[1,i] = np.sin ( angle )
      title = '  A five-pointed star:'
    elif ( test == 8 ):
      n = 6
      v = np.zeros ( [ 2, n ] )
      for i in range ( 0, n ):
        angle = i * 2.0 * np.pi / float ( n )
        v[0,i] = np.cos ( angle )
        v[1,i] = np.sin ( angle )
      title = '  A hexagon:'
    elif ( test == 9 ):
      n = 6
      v = np.array ( [ \
        [ 0.0, 2.0, 1.0, 0.0, 2.0, 1.0 ], \
        [ 0.0, 0.0, 1.0, 0.0, 0.0, 1.0 ] ] )
      title = '  A triangle twice:'
    elif ( test == 10 ):
      n = 8
      v = np.array ( [ \
        [ 1.0, 3.0, 3.0, 0.0, 0.0, 2.0, 2.0, 1.0 ], \
        [ 0.0, 0.0, 3.0, 3.0, 1.0, 1.0, 2.0, 1.0 ] ] )
      title = '  Square knot:'

    r8mat_transpose_print ( 2, n, v, title )

    result = polygon_is_convex ( n, v )

    if ( result == -1 ):
      print ( '  The polygon is not convex.' )
    elif ( result == 0 ):
      print ( '  The polygon is degenerate and convex.' )
    elif ( result == 1 ):
      print ( '  The polygon is convex and counterclockwise.' )
    elif ( result == 2 ):
      print ( '  The polygon is convex and clockwise.' )
#
#  Terminate.
#
  print ( '' )
  print ( 'POLYGON_IS_CONVEX_TEST' )
  print ( '  Normal end of execution.' )
  return

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