几何
===========

仿射变换
-------------

仿射变换（Affine Transformation）是一个向量空间到另一个向量空间的变换（平移 + 线性变换），变换前后保持以下属性：

- Collinearity ：共线的点仍然共线。

- Parallelism ：平行的线仍然平行。

- Convexity ：凸集仍然是凸集。

- Ratios Of Lengths ：不同线段的长度比值保持不变。

- Barycenters ：点集的重心保持不变。

.. math::
    :nowrap:

    $$
    \begin{bmatrix}
      x^{\prime} \\
      y^{\prime} \\
      1
    \end{bmatrix}
    =
    T
    \begin{bmatrix}
      x \\
      y \\
      1
    \end{bmatrix}
    ,\quad
    T =
    \begin{bmatrix}
      a_1 & a_2 & t_x \\
      a_3 & a_4 & t_y \\
      0 & 0 & 1
    \end{bmatrix}
    $$

恒等变换（Identity）
^^^^^^^^^^^^^^^^^^^^^^^^

.. math::
    :nowrap:

    $$
    T =
    \begin{bmatrix}
      1 & 0 & 0 \\
      0 & 1 & 0 \\
      0 & 0 & 1
    \end{bmatrix}
    $$

平移（Translation）
^^^^^^^^^^^^^^^^^^^^^^^^

.. math::
    :nowrap:

    $$
    T =
    \begin{bmatrix}
      1 & 0 & d_x \\
      0 & 1 & d_y \\
      0 & 0 & 1
    \end{bmatrix}
    $$

缩放（Scaling）
^^^^^^^^^^^^^^^^^^

.. math::
    :nowrap:

    $$
    T =
    \begin{bmatrix}
      s_x & 0 & 0 \\
      0 & s_y & 0 \\
      0 & 0 & 1
    \end{bmatrix}
    $$

当 :math:`s_x=-1` 或 :math:`s_y=-1` 表示翻转（镜像）。

逆时针旋转（Rotation）
^^^^^^^^^^^^^^^^^^^^^^^^^

.. math::
    :nowrap:

    $$
    T =
    \begin{bmatrix}
      \cos \theta & -\sin \theta & 0 \\
      \sin \theta & \cos \theta  & 0 \\
      0 & 0 & 1
    \end{bmatrix}
    $$

错切（Shear）
^^^^^^^^^^^^^^^^^^

.. math::
    :nowrap:

    $$
    T =
    \begin{bmatrix}
      1 & sh_x & 0 \\
      sh_y & 1 & 0 \\
      0 & 0 & 1
    \end{bmatrix}
    $$


线段相交
-------------

**问题** ：给定两条线段四个端点的坐标，判断两条线段是否相交。

.. image:: ./16_lineSegment.jpg
  :align: center
  :width: 600 px

方法一：跨立实验
^^^^^^^^^^^^^^^^^^^^^

**快速排斥**

分别以两条线段为对角线作矩形，如果两个矩形没有重合部分（IoU = 0），则两条线段一定不相交。反之不然。

.. image:: ./16_iou.jpg
  :align: center
  :width: 500 px

.. code-block:: cpp
  :linenos:

  // 计算重合部分的顶点坐标，可用于计算 IoU
  // rec = {x1, y1, x2, y2} 分别表示矩形左下角和右上角的顶点坐标
  bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2)
  {
      int left_x = max(rec1[0], rec2[0]);
      int right_x = min(rec1[2], rec2[2]);
      int bottom_y = max(rec1[1], rec2[1]);
      int top_y = min(rec1[3], rec2[3]);
      return (left_x < right_x && bottom_y < top_y);
  }

**跨立实验**

如果两条线段相交，那么：以其中任意一条线段为标准，另一条线段的两个端点一定在这条线段（延长线）的两端，或者在这条线段上。

如果在两端，利用向量叉乘（ `Cross Product <https://en.wikipedia.org/wiki/Cross_product>`_ ）可表示为：

.. math::

  (\overrightarrow{AB} \times \overrightarrow{AC}) \cdot (\overrightarrow{AB} \times \overrightarrow{AD}) < 0,\quad (\overrightarrow{CD} \times \overrightarrow{CA}) \cdot (\overrightarrow{CD} \times \overrightarrow{CB}) < 0.

.. image:: ./16_crossProduct.jpg
  :align: center
  :width: 600 px


向量叉乘/向量积
  两个向量 :math:`\vec{a},\vec{b}` 的向量积 :math:`\vec{a} \times \vec{b}` 为一个向量，
  它的方向与 :math:`\vec{a},\vec{b}` 都垂直，且使 :math:`\vec{a},\vec{b}, \vec{a} \times \vec{b}` 构成右手系；
  它的模等于以 :math:`\vec{a},\vec{b}` 为边的平行四边形的面积，即 :math:`|\vec{a} \times \vec{b}| = |\vec{a}||\vec{b}|\sin \theta` ，
  其中 :math:`\theta` 为 :math:`\vec{a},\vec{b}` 的夹角。

  性质：

    .. math::

      \vec{a} \times \vec{b} &=\ - \vec{b} \times \vec{a} \\
      \vec{a} \times \lambda \vec{a} &=\ 0


    .. math::
      :nowrap:

      $$
      \vec{a} \times \vec{b}
       =
      \begin{vmatrix}
        \vec{i} & \vec{j} & \vec{k} \\
        a_1 & a_2 & a_3 \\
        b_1 & b_2 & b_3
      \end{vmatrix}
       =
      \begin{vmatrix}
        a_2 & a_3\\
        b_2 & b_3
      \end{vmatrix}
      \vec{i}
      -
      \begin{vmatrix}
        a_1 & a_3\\
        b_1 & b_3
      \end{vmatrix}
      \vec{j}
      +
      \begin{vmatrix}
        a_1 & a_2\\
        b_1 & b_2
      \end{vmatrix}
      \vec{k}
      $$

      $$
      \begin{vmatrix}
        c_1 & c_2 \\
        c_3 & c_4
      \end{vmatrix}
      =
      c_1 c_4 - c_2 c_3
      $$

  其中 :math:`[O; \vec{i}, \vec{j}, \vec{k}]` 是一个直角坐标系；二维向量的第三维可扩展为 0。

**相交判断**

- :math:`(\overrightarrow{AB} \times \overrightarrow{AC}) \cdot (\overrightarrow{AB} \times \overrightarrow{AD}) > 0` ： :math:`C` 和 :math:`D` 在线段 :math:`AB` 的同一侧

  - 若 :math:`(\overrightarrow{CD} \times \overrightarrow{CA}) \cdot (\overrightarrow{CD} \times \overrightarrow{CB}) = 0` ， :math:`A` 或 :math:`B` 在线段 :math:`CD` 的延长线上，不相交。

  - 若 :math:`(\overrightarrow{CD} \times \overrightarrow{CA}) \cdot (\overrightarrow{CD} \times \overrightarrow{CB}) \neq 0` ，不相交。

- :math:`(\overrightarrow{AB} \times \overrightarrow{AC}) \cdot (\overrightarrow{AB} \times \overrightarrow{AD}) < 0` ： :math:`C` 和 :math:`D` 在线段 :math:`AB` 的不同侧

  - 若 :math:`(\overrightarrow{CD} \times \overrightarrow{CA}) \cdot (\overrightarrow{CD} \times \overrightarrow{CB}) \leqslant 0` ，相交；如果等于 0，交点为 :math:`A` 或 :math:`B` 。

  - 若 :math:`(\overrightarrow{CD} \times \overrightarrow{CA}) \cdot (\overrightarrow{CD} \times \overrightarrow{CB}) > 0` ，不相交。

- :math:`(\overrightarrow{AB} \times \overrightarrow{AC}) \cdot (\overrightarrow{AB} \times \overrightarrow{AD}) = 0` 可能是三种情形：

  - :math:`C` 或 :math:`D` 在线段 :math:`AB` 上（交于 :math:`C` 或 :math:`D` ）。

  - :math:`C` 或 :math:`D` 在线段 :math:`AB` 的延长线上（不相交），此时线段 :math:`CD` 和线段 :math:`AB` 可能是共线。

  - 线段 :math:`CD` 和线段 :math:`AB` 部分重合。



方法二：直线交点方程
^^^^^^^^^^^^^^^^^^^^^

:math:`AB` 的直线方程：:math:`\overrightarrow{OA} + \lambda \overrightarrow{AB}` ，
:math:`CD` 的直线方程：:math:`\overrightarrow{OC} + \mu \overrightarrow{CD}` ，

即：

.. math::
  :nowrap:

  $$
  \begin{cases}
     x &=\ x_a + \lambda (x_b - x_a) \\
     y &=\ y_a + \lambda (y_b - y_a)
  \end{cases}
  $$

  $$
  \begin{cases}
     x &=\ x_c + \mu (x_d - x_c) \\
     y &=\ y_c + \mu (y_d - y_c)
  \end{cases}
  $$

交点方程：

.. math::
  :nowrap:

  $$
  \begin{cases}
    x_a + \lambda (x_b - x_a) &=\ x_c + \mu (x_d - x_c) \\
    y_a + \lambda (y_b - y_a) &=\ y_c + \mu (y_d - y_c)
  \end{cases}
  $$

即：

.. math::
  :nowrap:

  $$
  \begin{cases}
    \lambda (x_b - x_a) - \mu (x_d - x_c) &=\ x_c - x_a \\
    \lambda (y_b - y_a) - \mu (y_d - y_c) &=\ y_c - y_a
  \end{cases}
  $$

若行列式

.. math::
  :nowrap:

  $$
  \Delta
  =
  \begin{vmatrix}
    x_b - x_a & -(x_d - x_c) \\
    y_b - y_a & -(y_d - y_c)
  \end{vmatrix}
   = 0
  $$

表示两线段重合或平行。

若 :math:`\Delta \neq 0` ，利用 `Cramer 法则 <https://en.wikipedia.org/wiki/Cramer%27s_rule>`_ 求出：

.. math::
  :nowrap:

  $$
  \lambda
  =
  \frac{1}{\Delta}
  \begin{vmatrix}
    x_c - x_a & -(x_d - x_c) \\
    y_c - y_a & -(y_d - y_c)
  \end{vmatrix}
  $$

  $$
  \mu
  =
  \frac{1}{\Delta}
  \begin{vmatrix}
    x_b - x_a & x_c - x_a \\
    y_b - y_a & y_c - y_a
  \end{vmatrix}
  $$

只有当 :math:`0 \leqslant \lambda \leqslant 1,\ 0 \leqslant \mu \leqslant 1` 两条线段才相交，否则交点在线段的延长线上。


凸多边形
--------------

**问题** ：按逆时针顺序给定多边形 :math:`n` 个顶点的坐标，判断该多边形是否是凸多边形。

**方案** ：凸多边形的特点是：对于任意一条边，其他的边都在它的同一侧；按逆时针顺序，下一条边 :math:`\vec{l}_{i+1}` 一定在当前边 :math:`\vec{l}_i` 的逆时针方向。
判断方法：如果 :math:`\vec{l}_i \times \vec{l}_{i+1}` 符号为正，则在逆时针方向；符号为负，则在顺时针方向；大小为 0，表示平行/共线。


参考资料
-------------

1. 计算几何-判断线段是否相交

  https://www.cnblogs.com/wuwangchuxin0924/p/6218494.html

2. 线段的交点计算

  http://dec3.jlu.edu.cn/webcourse/t000096/graphics/chapter5/01_1.html

3. 何为仿射变换(Affine Transformation)

  https://www.cnblogs.com/bnuvincent/p/6691189.html

4. Affine transformation

  https://en.wikipedia.org/wiki/Affine_transformation#Properties