2d_geometry

平面几何 §

线段 §

直线的角度 §

• 用角度进行表示

angle = math.atan2((start[1]-end[1]),(start[0]-end[0]))*180/math.pi

点[x,y]到直线y=ax+b的距离 §

dist = abs(a*x-y+b)/sqrt(a**2+1)

直线的方程 §

• 下文中讨论的直线化简后默认形式为，若非垂线，则，若为垂线，则

def line_from_2pts(p1, p2):
    a, b, c = 0, 0, 0
    [x1, y1] = p1
    [x2, y2] = p2
    if abs(x2-x1) > 1e-5:
        ## ax+by+c=0
        a = -(y2-y1)/(x2-x1)
        b = 1
        c = -y1-a*x1
    else:
        ## x+c=0
        a, b, c = 1, 0, -x1
 
    return a, b, c
    
####====
a, b, c = line_from_2pts(start, end)
if b == 1:
    ## ax+by+c=0, none-verticle line
    y = -a*x-c
else:
    ## need to make up this for your own purpose
    ## x+c=0, verticle line
    ...

判断点在直线的哪一侧 §

• 已知直线方程ax+by+c=0，计算d=ax'+by'+c，根据d的符号判断，分情况讨论
  • 若为垂线，即，则在左侧，在右侧
  • 若为水平线，即，则在下方，在上方
  • 若（），则在右下，在左上
  • 若（），则在左下，在右上

二维空间内两直线是否相交 §

• 参考 https://blog.csdn.net/HelloZEX/article/details/80880385
• 基本思路，假设两个向量分别为和：
  1. 两个向量投影至坐标轴时应有重叠部分，否则说明两者共线但不相交。
  2. 判断所使用的基本原理：叉积。若矢量，矢量，则。通过项的正负号可以得知
     • 若，则在的顺时针方向（）
     • 若，则在的逆时针方向（）
     • 若，则与共线（或）
  3. 判断、是否在的两侧。换言之，判断与是否异号。
     • 若异号，则在两侧。
     • 若为0，则或二者其一在上。
     • 若同号，则在同侧（不相交）。
  4. 判断、是否在的两侧。
• 示例代码

def check_cross(seg1, seg2):
    eps = 1e-6 ## Need to take the error of float into account
    ## two 2D list, line1 and line2.
    ## seg1: [[a_x, a_y], [b_x, b_y]]
    ## seg2: [[c_x, c_y], [d_x, d_y]]
    [[a_x, a_y], [b_x, b_y]] = l1
    [[c_x, c_y], [d_x, d_y]] = l2
    
    no_projection = max(c_x,d_x)-min(a_x,b_x) < -eps\
                 or max(c_y,d_y)-min(a_y,b_y) < -eps\
                 or max(a_x,b_x)-min(c_x,d_x) < -eps\
                 or max(c_y,d_y)-min(a_y,b_y) < -eps
    if no_projection == True:
        pass
    else:
        ## calculate the cross product
        c1 = (((a_x - c_x)*(d_y - c_y) - (a_y - c_y)*(d_x - c_x))*\
             ((b_x - c_x)*(d_y - c_y) - (b_y - c_y)*(d_x - c_x))) > eps 
        c2 = (((c_x - a_x)*(b_y - a_y) - (c_y - a_y)*(b_x - a_x))*\
             ((d_x - a_x)*(b_y - a_y) - (d_y - a_y)*(b_x - a_x))) > eps
        if c1 or c2:
            pass
        else:
            ## if c1<=0 and c2<=0, there is an intersection
            ## marginal condition: c1==0 or c2==0, form a "T" shape
            return True
    return False

两直线交点（需先判断是否相交） §

def seg_x(seg1, seg2):
    # segment crossing
    ## seg1: [[a_x, a_y], [b_x, b_y]]
    ## seg2: [[c_x, c_y], [d_x, d_y]]
    [[a_x,a_y], [b_x,b_y]] = seg1
    [[c_x,c_y], [d_x,d_y]] = seg2
 
    denominator = (b_y - a_y)*(d_x - c_x) - (a_x - b_x)*(c_y - d_y)
 
    x = ( (b_x - a_x) * (d_x - c_x) * (c_y - a_y)\
        + (b_y - a_y) * (d_x - c_x) * a_x\
        - (d_y - c_y) * (b_x - a_x) * c_x ) / denominator ;  
    y = -( (b_y - a_y) * (d_y - c_y) * (c_x - a_x)\
        + (b_x - a_x) * (d_y - c_y) * a_y\
        - (d_x - c_x) * (b_y - a_y) * c_y ) / denominator; 
 
    return  x, y

平行线间的距离与相对位置关系 §

• 若两直线为和，则其间距为
• 相对位置关系（为了简化讨论，对系数进行归一化，即的系数，若，则的系数）
  • 若，则与中较小的那条线在另一条线的左侧
  • 若，，则与中较小的那条线在另一条线的上方/左侧
  • 若，，则与中较小的那条线在另一条线的上方/右侧

二维图形 §

最大内接长方形 §

• 参考填充给定目标的最大内接长方形（带旋转角度）