test whether a point is inside a polygon represented by a deque + full Melkman's convex hull algorithm

convex_hull_Melkman.py

#! /usr/bin/env python3
"""
Created on Sun Jan 24 2016
Anna M. Kedzierska

"""
import matplotlib.pyplot as plt
import numpy as np
import collections
import math
import unittest

class PointLoc:
    def __init__(self, p):
        self.x, self.y  = p[0], p[1]

def is_left(p0, p1, p2):
                # >0 isLeft, <0 is Right
                vx = p1.x - p0.x
                vy = p1.y - p0.y

                wx = p2.x - p0.x
                wy = p2.y - p0.y

                v = [vx, vy]
                w = [wx, wy]
                sign_eval = np.cross(v,w)

                return sign_eval>0


def is_inside(deq_cubic, pt):
                # input: current deque based on k points (convex hull at k'th stage) +  (k+1)th point
                # is inside if it lies to the left of both bottom and top segments in the deque
                cond_bottom = is_left(PointLoc(deq_cubic[0]), PointLoc(deq_cubic[1]), PointLoc(pt))
                cond_top = is_left(PointLoc(deq_cubic[-2]), PointLoc(deq_cubic[-1]), PointLoc(pt))
                cond = (cond_bottom and cond_top)

                return cond


def tangent_polygon_left(deq, point):
    # while point is right of deq[bot]deq[bot+1] delete deq[bot] from the bottom of deq
    return (is_left(PointLoc(deq[0]), PointLoc(deq[1]), PointLoc(point)) > 0)

def tangent_polygon_right(deq, point):
    #while point is right of deq[top-1]deq[top] pop deq[top] from the top of deq
    return (is_left(PointLoc(deq[-2]), PointLoc(deq[-1]), PointLoc(point)) > 0)

def convex_hull2D(points): 
    num_points = len(points)
    deq = collections.deque()
    
    if(is_left(PointLoc(points[0]), PointLoc(points[1]), PointLoc(points[2]))>0):
        deq.append(points[0])
        deq.append(points[1])
    else:
        deq.append(points[1])
        deq.append(points[0])
        
    deq.append(points[2])
    deq.appendleft(points[2])
    
    for v in range(3, num_points):
        
        if(is_inside(deq, points[v])):
            pass
        
        else:            
            
            while not tangent_polygon_left(deq, points[v]):
                deq.popleft()
            
            # insert new point on the top of deque
            deq.appendleft(points[v])
            
            
            while not tangent_polygon_right(deq, points[v]):
                deq.pop()
                
            # push new point on the top of deque
            deq.append(points[v])
    
    return deq
        

debugged_RC.py

#! /usr/bin/env python3
"""
Created on Mon Sun 24 2016
Anna M. Kedzierska

"""

import numpy as np
import collections
import unittest

class PointLoc:
    def __init__(self, p):
        self.x, self.y  = p[0], p[1]

def is_left(p0, p1, p2):
                # >0 isLeft, <0 is Right
                vx = p1.x - p0.x
                vy = p1.y - p0.y

                wx = p2.x - p0.x
                wy = p2.y - p0.y

                v = [vx, vy]
                w = [wx, wy]
                sign_eval = np.cross(v,w)

                return sign_eval>0


def is_inside(deq_cubic, pt):
                # input: current deque based on k points (convex hull at k'th stage) +  (k+1)th point
                # is inside if it lies to the left of both bottom and top segments in the deque
                cond_bottom = is_left(PointLoc(deq_cubic[0]), PointLoc(deq_cubic[1]), PointLoc(pt))
                cond_top = is_left(PointLoc(deq_cubic[-2]), PointLoc(deq_cubic[-1]), PointLoc(pt))
                cond = (cond_bottom and cond_top)

                return cond

# positive test
square = [(0, 0), (3, 0), (3, 3), (0, 3), (0, 0), (1, 1)] # full sets of points (square)
                                                    # with point (1,1) inside
# negative test
polygon = [(0, 0), (3, 0), (3, 3), (0, 3), (0, 0), (-10, -10)] # all points are part of the convex hull

deque_cubic = [(0, 0), (3, 0), (3, 3), (0, 3), (0, 0)] # deque of square at the 3rd iteration

# we test whether (1, 1) is inside of the already formed convex hull:

# True
assert  is_inside(deque_cubic, square[-1]) == True
# False
assert  is_inside(deque_cubic, polygon[-1]) == False

tests.py

#! /usr/bin/env python3
"""
Created on Mon Sun 24 2016
Anna M. Kedzierska

"""

import matplotlib.pyplot as plt
import numpy as np

poly = [(3, 0), (4, 2), (5, 2), (5.5, 3), (5, 4), (4, 5), (5, 6),
      (7, 5), (7, 3), (8, 2.5), (8, 4), (9, 5), (8, 7), (7, 8), (6, 7),
      (4, 7.75), (3.5, 7.5), (3, 8), (3, 8.5), (2.5, 9), (1, 9), (0, 8),
      (2, 7), (1, 7), (0, 6), (1, 4), (2, 5), (2, 2), (3, 3), (2, 1)]
#hull:([(2, 1), (3, 0), (8, 2.5), (9, 5), (8, 7), (7, 8), (2.5, 9), (1, 9), (0, 8), (0, 6), (2, 1)])
       
hull = convex_hull2D(poly)

def make_plot(hull, points):
    x, y= [], []
    for i in hull:
        x.append(i[0])
        y.append(i[1])
    points_array = np.array(points)
    plt.plot(points_array[:,0], points_array[:,1], 'ro')
    plt.plot(x,y, label='Circle')
    plt.show()
    
make_plot(hull, poly)

assert (7,8) in hull # True
assert (4, 2) in hull # False