判断点是否在矩形内的算法

需求描述：
有一个 4*4 的方格，用户可以选择起点和落点形成矩形，每次形成的矩形不能重叠，起点可以和落点坐标一样。现已知起点、未选点集合和已选点集合，求落点的集合。

算法重点：转换为判断点P是否在一个矩形内。

---

###方法一：建立平面直角坐标系，根据横坐标和纵坐标判断点是否在矩形内。

/**
 * 判断点是否在矩形内（含边）。p1、p2是矩形的两个对角点。
 * 该算法和平面直角坐标系怎么建立无关
 * @param $rc
 * @param $p
 * @return bool
 */
function isInRect($rc, $p)
{
    $xi = ($p->x - $rc->p1->x) * ($p->x - $rc->p2->x);
    $yi = ($p->y - $rc->p1->y) * ($p->y - $rc->p2->y);
    return ($xi <= 0) && ($yi <= 0);
}

---

###方法二：假设矩形左、右、上、下分别在直线 L₁、L₂、L₃、L₄ 上，只需要证明点 P 同时在上下、左右直线之间即可。

过P作一条直线相交于 L₁、L₂ 的 C₁ 、C₂ ，向量PC₁ 、PC₂ 同向则P在 L₁、L₂ 之外，反向则在 L₁、L₂ 之内。同理可判断P是否在 L₃、L₄ 之间。

$$ PC_1 = （C_1x - P_x , C_1y - P_y）; PC_2 = （C_2x - P_x , C_2y - P_y）;$$
$$ \frac{C_2x - P_x}{C_1x - P_x } > 0 或 \frac{C_2y - P_y}{C_1y - P_y } > 0 => PC_1、PC_2 同向 $$
$$（C_1x-P_x）^2 + （C_1y-P_y）^2 = 0 => PC_1为零向量 => PC_1、PC_2 同向$$
$$（C_2x-P_x）^2 + （C_2y-P_y）^2 = 0 => PC_2为零向量 => PC_1、PC_2 同向$$

如果：
$$ L_1: y = mx + t_1; $$
$$ L_2: y = mx + t_2; $$
$$ C_1C_2: y = (m+1)x; $$
$$ P_1:(P_1x, P_1y); P_2:(P_3x, P_3y) 是L_1上的两个矩形顶点；$$
$$ P_3:(P_3x, P_3y); P_4:(P_4x, P_4y) 是L_2上的两个矩形顶点；$$

则：

$$ 若点P和{P_1,P_2,P_3,P_4}中的某一点重合，则P在矩形内；$$
$$ 若(t_2 - P_x)(t_1 - P_x)>0, t_1=\frac{P_1yP_2x-P_1xP_2y}{P_2x-P_1x},t_2=\frac{P_3yP_4x-P_3xP_4y}{P_4x-P_3x}则P在矩形内；$$
$$ 若(t_2 - P_x)(t_1 - P_x)>0, t_1=\frac{P_1yP_2x-P_1xP_2y}{P_2x-P_1x},t_2=\frac{P_3yP_4x-P_3xP_4y}{P_4x-P_3x}则P在矩形内；$$

/**
 * 此处省略n行代码
 */

###方法三：以点P为起点，向左作射线，如果射线和矩形的焦点个数是奇数，则P在矩形内。
PS：对以下特例不做考虑：1、对于矩形的水平边不作考虑；2、对于矩形的顶点和L相交的情况。

/**
 * 此处省略m行代码
 */

总结：方法一简单实用，方法三可以推广到判断点是否在任意多边形内。

---

本文涉及资料：
计算几何算法概览

---