[算法]Python实现，,题目：代码：# -*

[算法]Python实现，,题目：代码：# -*

题目：

代码：

# -*- coding:utf-8 -*-def rayCasting(p, poly):    px = p[‘x‘]    py = p[‘y‘]    flag = False    i = 0    l = len(poly)    j = l - 1    #for(i = 0, l = poly.length, j = l - 1; i < l; j = i, i++):    while i < l:        sx = poly[i][‘x‘]        sy = poly[i][‘y‘]        tx = poly[j][‘x‘]        ty = poly[j][‘y‘]        #点与多边形顶点重合        if (sx == px and sy == py) or (tx == px and ty == py):            return (px, py)        #判断线段两端点是否在射线两侧        if (sy < py and ty >= py) or (sy >= py and ty < py):            #线段上与射线 Y 坐标相同的点的 X 坐标            x = sx + (py - sy) * (tx - sx) / (ty - sy)            #点在多边形的边上            if x == px:                return (px,py)            #射线穿过多边形的边界            if x > px:                flag = not flag        j = i        i += 1    #射线穿过多边形边界的次数为奇数时点在多边形内    return (px,py) if flag else ‘out‘#根据数组下标奇偶数得到点的坐标def getpoint(a):    i = 0    zhima = []    while i < len(a.split(‘,‘)[1::2]):        zhima.append({‘x‘: float(a.split(‘,‘)[::2][i]),‘y‘: float(a.split(‘,‘)[1::2][i])})        i += 1    return zhima#根据输入的点循环判断芝麻是否在多边形里面，如果全部在外面则输出no,否则输出芝麻的坐标def rs(zhima, duobianxing):    zm = getpoint(zhima)    dbx = getpoint(duobianxing)    count = 0    for point in zm:        rs = rayCasting(point, dbx)        if rs == ‘out‘:            count += 1        else:            print rs    if count == len(zm):        print "no"zhima = "6,4,8,8,9,9"duobianxing = "1,1,7,3,5,7"rs(zhima,duobianxing)

结果：

[算法]Python实现