#include stdioh#include stdboolh 引入bool类型typedef struct 定义点的结构体 double x;x坐标 double y;y坐标 Point;typedef struct 定义边的结构体 Point start;起点 Point end;终点 Side;bool isParalleldouble slope 判断是否平

本文将对多边形内部点判断算法进行详细解释。

多边形内部点判断算法

多边形内部点判断算法是判断一个点是否在一个多边形内部的算法。该算法的基本思想是：如果从该点向任意方向发射一条射线，与多边形的边有奇数个交点，则该点在多边形内部，否则在外部。

步骤如下：

• 确定一个点p和一个多边形；
• 从点p向某个方向发射一条射线；
• 判断射线是否与多边形的边相交，如果相交则计数器加1；
• 重复步骤2-3，直到射线发射的方向覆盖了多边形的所有角度；
• 如果计数器是奇数，则点p在多边形内部，否则在外部。

该算法的关键在于如何判断射线与多边形的边是否相交。这里需要用到向量的知识。

向量的叉积

向量的叉积是一个向量，它的大小等于原来两个向量所围成的平行四边形的面积，方向垂直于这两个向量的平面，符号由右手定则决定，即右手四指指向第一个向量，然后弯曲四指到第二个向量，大拇指的方向就是向量的方向。

若有向量a和向量b，则它们的叉积为：

$$\vec{a}\times\vec{b}=\begin{vmatrix}i&j&k\a_{1}&a_{2}&a_{3}\b_{1}&b_{2}&b_{3}\end{vmatrix}=(a_{2}b_{3}-a_{3}b_{2})i-(a_{1}b_{3}-a_{3}b_{1})j+(a_{1}b_{2}-a_{2}b_{1})k$$

其中，i、j、k分别是三个坐标轴的单位向量。

叉积的大小等于原来两个向量所围成的平行四边形的面积，方向垂直于这两个向量的平面，符号由右手定则决定，即右手四指指向第一个向量，然后弯曲四指到第二个向量，大拇指的方向就是向量的方向。

如果两个向量平行，则它们的叉积为0；如果两个向量垂直，则它们的叉积的大小等于原来两个向量的模长的乘积。

点与直线的关系

设点P(x,y)，直线L的一般式为ax+by+c=0，如果点P在直线L上，则有：

$$ax+by+c=0$$

如果点P在直线L上，则点P到直线L的距离为0，即点P与直线L的距离公式为：

$$\frac{|ax+by+c|}{\sqrt{a^{2}+b^{2}}}$$

如果点P在直线L的上方，则有：

$$ax+by+c>0$$

如果点P在直线L的下方，则有：

$$ax+by+c<0$$

两条直线的关系

设直线L1的一般式为a1x+b1y+c1=0，直线L2的一般式为a2x+b2y+c2=0，如果两条直线平行，则有：

$$\frac{a_{1}}{b_{1}}=\frac{a_{2}}{b_{2}}$$

如果两条直线垂直，则有：

$$a_{1}a_{2}+b_{1}b_{2}=0$$

如果两条直线相交，则它们的交点为：

$$\begin{cases}x=\frac{b_{2}c_{1}-b_{1}c_{2}}{a_{1}b_{2}-a_{2}b_{1}}\y=\frac{a_{1}c_{2}-a_{2}c_{1}}{a_{1}b_{2}-a_{2}b_{1}}\end{cases}$$

边的斜率和方程

设边的两个端点分别为P1(x1,y1)和P2(x2,y2)，则边的斜率为：

$$k=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$$

如果边不平行于y轴，则它的方程为：

$$y-y_{1}=k(x-x_{1})$$

即：

$$y=kx+(y_{1}-kx_{1})$$

如果边平行于y轴，则它的方程为：

$$x=x_{1}$$

点是否在边上

判断点是否在边上，需要计算点在边上的纵坐标，如果点的纵坐标等于计算出来的纵坐标，则点在边上。

计算点在边上的纵坐标的方法如下：设点P(x,y)，边的两个端点分别为P1(x1,y1)和P2(x2,y2)，则边的斜率为：

$$k=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$$

如果边不平行于y轴，则它的方程为：

$$y-y_{1}=k(x-x_{1})$$

即：

$$y=kx+(y_{1}-kx_{1})$$

如果点在边上，则有：

$$y=kx+(y_{1}-kx_{1})$$

即：

$$y=k(x-x_{1})+y_{1}$$

计算出来的纵坐标为：

$$y=k(x-x_{1})+y_{1}$$

如果点的纵坐标等于计算出来的纵坐标，则点在边上。

射线是否与边相交

判断射线是否与边相交，需要计算射线与边的交点的横坐标，如果交点的横坐标大于点的横坐标，则相交。

计算交点的横坐标的方法如下：设点P(x,y)，边的两个端点分别为P1(x1,y1)和P2(x2,y2)，则边的斜率为：

$$k=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$$

如果边不平行于y轴，则它的方程为：

$$y-y_{1}=k(x-x_{1})$$

即：

$$y=kx+(y_{1}-kx_{1})$$

假设射线向右发射（如下图所示），则射线的方程为：

$$x=x_{0}$$

其中x0为点P的横坐标。

将射线的方程代入边的方程中，可得到交点的横坐标：

$$x=\frac{y-y_{1}}{k}+x_{1}$$

将点P的横坐标代入上式中，可得到交点的横坐标。如果交点的横坐标大于点的横坐标，则相交。

代码实现

代码实现如下