Is vertex in polygon ?

polygon.py

import pygame as pg
import math

W, H = 1000, 600

pg.display.init()
pg.font.init()
font = pg.font.SysFont('serif', 20)

X, Y = 0, 1

def cross(a, b):
    return a[X] * b[Y] - a[Y] * b[X]

def dot(a, b):
    return a[X] * b[X] + a[Y] * b[Y]

def minus(a, b):
    return (a[X] - b[X], a[Y] - b[Y])

def is_CCW(ps):
    """
    Test if polygon ps is in CCW order
    """
    w = 0.
    for i in xrange(len(ps)):
        a = minus(ps[i-1], ps[i-2])
        b = minus(ps[i], ps[i-1])
        t = math.atan2(cross(a, b), dot(a, b))
        w += t
    return w >= 0

def is_vertex_in_polygon(ps, v):
    """
    Test if vertex v in polygon ps
    """
    w = 0.
    for i in xrange(len(ps)):
        a = minus(v, ps[i-1])
        b = minus(v, ps[i])
        t = math.atan2(cross(a, b), dot(a, b))
        w += t
    return abs(w) > math.pi

EPS = 1e-8

def sgn(x):
    return (x > EPS) - (x < -EPS)

def is_vertex_in_polygon_raytrace(ps, p):
    s = (1., 0.)
    cnt = 0
    for i in xrange(len(ps)):
        v1 = minus(ps[i-1], ps[i])
        v2 = minus(ps[i-1], p)
        f1 = cross(s, v1)
        if sgn(f1) == 0:
            if sgn(dot(minus(ps[i], p), v2)) <= 0:
                return True
            continue
        if sgn(f1 * cross(v2, v1)) >= 0:
            r = cross(s, v2) / f1
            if sgn(r) == 0:
                if sgn(cross(s, v1) * cross(minus(ps[i-1], ps[i-2]), s)) > 0:
                    cnt += 1
            elif sgn(r) > 0 and sgn(r - 1) < 0:
                cnt += 1
    return cnt % 2 != 0

test_method = is_vertex_in_polygon_raytrace

def screen_to_math(p):
    x, y = p
    return (x, H - y)

math_to_screen = screen_to_math

class App:
    SELECT_POLY, SELECT_VERTEX, FINISH = 0, 1, 2
    FIELD_DISTANCE = 8

    def __init__(self):
        self.screen = pg.display.set_mode((W, H))
        self.clear()
        self.run()

    def write_at(self, s, pos):
        self.screen.blit(font.render(s, 1, (0, 0, 0)), pos)

    def update(self):
        screen = self.screen
        screen.fill((0xff, 0xff, 0xff))
        if len(self.polygon) > 1:
            closed = self.state == self.SELECT_VERTEX
            polygon = map(math_to_screen, self.polygon)
            pg.draw.lines(screen, self.polyColor, closed, polygon)
            for i, p in enumerate(polygon):
                screen.blit(font.render('#%d'%(i), 1, (0x44, 0x44, 0x44)), p)
            if closed and self.fieldMode:
                d = self.FIELD_DISTANCE
                for x in xrange(d, W, d):
                    for y in xrange(d, H, d):
                        isInside = test_method(self.polygon, (x, y))
                        pg.draw.circle(screen, 
                                (0x4f, 0x8f, 0) if isInside else (0xef, 0xef, 0x9f), 
                                math_to_screen((x, y)), 2)
        if self.vertex:
            pg.draw.circle(screen, 
                    (0, 0x4f, 0) if self.isInside else (0x8f, 0xff, 0), 
                    math_to_screen(self.vertex), 4)

        self.write_at('isCCW?: {}'.format(self.isCCW), (10, 10))
        self.write_at('isInside?: {}'.format(self.isInside), (10, 40))

    def clear(self):
        self.state = self.SELECT_POLY
        self.polygon = []
        self.vertex = None
        self.isInside = None
        self.isCCW = None
        self.fieldMode = True 
        self.polyColor = (0, 0, 0)

    def on_left_click(self, pos):
        if self.state == self.SELECT_POLY:
            self.polygon.append(pos)
            self.update()
        elif self.state == self.SELECT_VERTEX:
            self.vertex = pos
            self.isInside = test_method(self.polygon, self.vertex)
            self.update()

    def close_polygon(self):
        self.isCCW = is_CCW(self.polygon)

    def on_right_click(self, pos):
        if self.state == self.SELECT_POLY:
            self.state = self.SELECT_VERTEX
            self.close_polygon()
            self.update()
        elif self.state == self.SELECT_VERTEX:
            self.clear()
            self.update()

    def run(self):
        timer = pg.time.Clock()
        self.update()
        while 1:
            for e in pg.event.get():
                if e.type == pg.QUIT:
                    exit(0)
                if e.type == pg.MOUSEBUTTONDOWN:
                    pos = screen_to_math(e.pos)
                    if e.button == 1:
                        self.on_left_click(pos)
                    elif e.button == 3:
                        self.on_right_click(pos)
                if e.type == pg.KEYDOWN:
                    if e.key == pg.K_SPACE:
                        self.fieldMode = not self.fieldMode
            pg.display.update()
            timer.tick(30)

# help(font.render)
App().run()