PolygonConcavityIndex

This page shows a solution to the problem PolygonConcavityIndex presented by Codility in the lesson 99 “ Future Training”.

Observations:
The boundary of the polygon is made up of segments. Each segment can continue collinearly with the previous segment, or make a left turn, or a right turn. Any point where a turn to the exterior of the polygon occurs will be contained in the convex hull of the polygon.

Strategy:
Create an array which denotes what turn makes the boundary at each point. Then, figure out whether the interior of the polygon is on the right or left side of the segments of the boundary, and lastly, return the index of the first point where the boundary makes a turn to the exterior (if there is any).

Implementation:
In the following code ‘l’ stands for ‘left turn’, ‘r’ for ‘right turn’ and ‘s’ for ‘straight line’

import  math

def whatturn(P, Q, R):
v_1 = (Q.x - P.x, Q.y - P.y)
v_2 = (R.x - Q.x, R.y - Q.y)
numerator = (v_1[0]*v_2[0] + v_1[1]*v_2[1])
length_v1 = math.sqrt(v_1[0]**2 + v_1[1]**2)
length_v2 = math.sqrt(v_2[0]**2 + v_2[1]**2)
denominator = length_v1 * length_v2
quotient = numerator/denominator
if quotient < -1: quotient = -1 # this caps off the error of
if quotient > 1: quotient = 1 # the floating-point number and
angle = math.acos(quotient)# avoids going out of the acos domain

if v_1[0] == 0:
if v_1[1] > 0:
if R.x < Q.x:
return ('l', angle)
elif R.x > Q.x:
return ('r', angle)
else:
return ('s', angle)
else:# Assume v_1[1] != 0 (no duplicate points in A)
if R.x < Q.x:
return ('r', angle)
elif R.x > Q.x:
return ('l', angle)
else:
return ('s', angle)
else:
constant = v_1[1]*P.x - v_1[0]*P.y
value = v_1[1]*R.x - v_1[0]*R.y
if v_1[0] > 0:
if value < constant:
return ('l', angle)
elif value > constant:
return ('r', angle)
else:
return ('s', angle)
else:
if value < constant:
return ('l', angle)
elif value > constant:
return ('r', angle)
else:
return ('s', angle)

def solution(A):

array = []
for i in xrange(len(A)-1):
array.append(whatturn(A[i-1], A[i], A[i+1]))
array.append(whatturn(A[-2], A[-1], A[0]))

total_angles = 0
for i in xrange(len(A)):
if array[i][0] == 'r':
total_angles += array[i][1]
else:
total_angles -= array[i][1]
# "total_angles" should now be 360 degrees or -360 degrees,
# depending on what side is the interior of the polygon on.
if total_angles > 0:
exterior_side = 'l'
else:
exterior_side = 'r'

for j in xrange(len(A)):
if array[j][0] == exterior_side:
return j
return -1

The above solution attains 100% score under Codility’s test.

To test the solution in your machine you can use the following:

class Point2D(object):
def __init__(self, pair):
self.x = pair[0]
self.y = pair[1]

points = [[-1, 3], [1, 2], [3, 1], [0, -1], [-2, 1]] # Example tests 1 & 2
points = [[-1, 3], [1, 2], [1, 1], [3, 1], [0, -1], [-2, 1], [-1, 2]]

input_list = []
for P in points:
input_list.append(Point2D(P))

print solution(input_list)

2 Replies to “PolygonConcavityIndex”

  1. Do you mind if I quote а few of your pоsts as long as I provide credit and sourceѕ back to
    your website? My website is in the exact same area of interest
    as yours and my users would certainly benefit from some
    of the infⲟrmation you provide here. Please let me know if this okay with you.
    Many thаnkѕ!

    1. That’s fine (I am not the kind of person who likes to say “All rights reserved”).

      The idea is that all the content in the blog is under the Creative Commons Attribution-ShareAlike 4.0 Interna-
      tional License. In short, you can copy, transform and redistribute the text on this page for
      any purpose as long as you give credit, indicate if changes were made and the distributed
      text is licensed again under the same license. To view a copy of this license click this link.

      Thank you.

Comments are closed.