判断点在四边形内（Python实现）

#判断点在四边形内（Python实现）| 来源: 网络整理| 查看: 265

判断点在四边形内的算法，在网上流传的方法大多是适合矩形，例如链接，并不适合所有的凸四边形。

先说对于矩形常用的方法，也是网上流传比较广的一种方法，是判断点与四边形的边的夹角是锐角，也即点积>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]) def point_in_triangle(point, corners): d1 = sign(point, corners[0, :], corners[1, :]) d2 = sign(point, corners[1, :], corners[2, :]) d3 = sign(point, corners[2, :], corners[0, :]) has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0) has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0) return not(has_neg and has_pos) def point_in_box(point, corners): triangle1 = corners[:3, :] ind = [2,3,0] triangle2 = corners[ind, :] is_in1 = point_in_triangle(point, triangle1) is_in2 = point_in_triangle(point, triangle2) return is_in1 or is_in2

【本文地址】

公司简介

联系我们