nnzzll/RotateNMS

Implementation of RotateNMS

1.已知两点求直线方程

直线方程一般式为: $$ Ax + By + C = 0 \tag{1-1}$$ 已知两个不同的点$P_{1}(x_{1},y_{1})$,$P_{2}(x_{2},y_{2})$ ①$x_{1} = x_{2}$时,直线方程为$x=x_{1}$ ②$y_{1} = y_{2}$时,直线方程为$y=y_{1}$ ③$x_{1} \neq x_{2} \wedge y_{1} \neq y_{2}$ 时,由直线方程两点式$\frac{y-y_{1}}{x-x_{1}} = \frac{y_{2}-y_{1}}{x_{2}-x_{1}}$展开得到: $$(y_{1}-y_{2})x+(x_{2}-x_{1})y+x_{1}y_{2}-x_{2}y_{1}=0 $$

$x_{1} = x_{2} \vee y_{1} = y_{2}$时,上式也成立,因此 $$A = y_{1}-y_{2}, B = x_{2}-x_{1}, C = x_{1}y_{2}-x_{2}y_{1}$$

2.已知两直线方程求交点

已知两直线 $$ A_{1}x + B_{1}y + C_{1} = 0 \tag{2-1}$$ $$ A_{2}x + B_{2}y + C_{2} = 0 \tag{2-2}$$

对(2-1)式乘A2,对(2-2)式乘A1得: $$ A_{1}A_{2}x + A_{2}B_{1}y + A_{2}C_{1} = 0 $$ $$ A_{1}A_{2}x + A_{1}B_{2}y + A_{1}C_{2} = 0 $$

两式相减得: $$ y = \frac{A_{1}C_{2}-A_{2}C_{1}}{A_{2}B_{1}-A_{1}B_{2}}$$ 同理可得 $$ x = \frac{B_{1}C_{2}-B_{2}C_{1}}{A_{1}B_{2}-A_{2}B_{1}}$$

若$ A_{2}B_{1}-A_{1}B_{2} = 0 $则说明两条直线平行

3.判断点是否在线段上

已知线段由$P_{1}(x_{1},y_{1})$,$P_{2}(x_{2},y_{2})$两点构成,求点$P(x,y)$是否在线段$P_{1}P_{2}$上。 ① $P,P_{1},P_{2}$三点共线 $\rightarrow$ $\overrightarrow{P_{1}P_{2}} \times \overrightarrow{P_{1}P} = 0$ ② 点$P$在由$P_{1}P_{2}$作为对角线的矩形范围内 同时满足①②,则点$P$在线段$P_{1}P_{2}$上 由①可得$$(x_{2}-x_{1},y_{2}-y_{1})\times(x-x_{1},y-y_{1}) = (x_{2}-x_{1})(y-y_{1}) - (y_{2}-y_{1})(x-x_{1}) = 0$$ 由②可得$$ (x-x_{1})(x_{2}-x)\geq0 且 (y-y_{1})(y_{2}-y)\geq0$$

4.多边形面积公式Shoelace Formula

$$S = \frac{1}{2} |\sum_{i=1}^n(x_{i}y_{i+1} - x_{i+1}y_{i})| $$