判断点在四边形内的算法 在网上流传的方法大多是适合矩形 例如链接 并不适合所有的凸四边形。
先说对于矩形常用的方法 也是网上流传比较广的一种方法 是判断点与四边形的边的夹角是锐角 也即点积 0。实现如下
def point_in_box_rect2(point, corners): check if a point lies in a rectangle defined by corners. un-support quadrangle idea: check projection Args: point (2,): coordinate of point corners (4, 2): coordinate of corners Returns: True if point in box assert corners.shape (4, 2) a corners[0, :] b corners[1, :] c corners[2, :] d corners[3, :] ab b - a am point - a bc c - b bm point - b cd d - c cm point - c da a - d dm point - d p_ab np.dot(ab, am) p_bc np.dot(bc, bm) p_cd np.dot(cd, cm) p_da np.dot(da, dm) cond1 p_ab 0 and p_bc 0 and p_cd 0 and p_da 0 cond2 p_ab 0 and p_bc 0 and p_cd 0 and p_da 0 return cond1 or cond2
以上方法不适用平行四边形的情况 例如
对于更一般的情况 可以将四边形考虑成2个三角形 判断点是不是在三角形其中之一内即可 具体参考链接。实现如下
def sign(p1, p2, p3): return (p1[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p1[1] - p3[1])
