本文主要是介绍计算几何基础，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

• (一)点与线段
• (二)线段与线段
• (三)点与多边形

(一)点与线段

1.如何判断点在线段上？

我们用向量 A B → \overrightarrow{AB} AB 表示线段AB，后面都将用向量表示线段。
Q A → × Q B → = 0 \overrightarrow{QA}\times\overrightarrow{QB}=0 QA ​×QB ​=0 判断点Q是否在直线AB上
Q A → × Q B → ≤ 0 \overrightarrow{QA}\times\overrightarrow{QB}\le0 QA ​×QB ​≤0 判断点Q是否落在线段AB之间。

2.如何判断点在线段的那一侧？
先判断点 A A A的纵坐标是否在线段两端点的纵坐标之间。

如果 A C → × A B → > 0 \overrightarrow{AC}\times\overrightarrow{AB}>0 AC ×AB >0，则可以知道点 A A A在线段 B C BC BC左侧。否则点 A A A在线段 B C BC BC右侧。

(二)线段与线段

1.如何求两个线段的交点？

我们先求出直线 A B AB AB和直线 C D CD CD的交点，再判断交点是否在线段 A B AB AB和线段 C D CD CD上。
直线 C D CD CD上的点可以表示为 C + t C D → C +t\overrightarrow{CD} C+tCD ，交点又在直线 A B AB AB上，所以有： B A → × B Q → = 0 \overrightarrow{BA}\times\overrightarrow{BQ}=0 BA ×BQ ​=0 ， B Q → = ( C + t C D → ) − B \overrightarrow{BQ}=(C+t\overrightarrow{CD})-B BQ ​=(C+tCD )−B
由此可以求出 t t t的值为：
t = B A → × C B → B A → × C D → t=\frac{\overrightarrow{BA}\times\overrightarrow{CB}}{\overrightarrow{BA}\times\overrightarrow{CD}} t=BA ×CD BA ×CB ​
所以 Q Q Q点坐标为： C + B A → × C B → B A → × C D → C D → C+\frac{\overrightarrow{BA}\times\overrightarrow{CB}}{\overrightarrow{BA}\times\overrightarrow{CD}}\overrightarrow{CD} C+BA ×CD BA ×CB ​CD 。
但是当两条线段是平行的，这种方法就失效了。因为 B A → × C D → = 0 \overrightarrow{BA}\times\overrightarrow{CD}=0 BA ×CD =0。
此时我们可以通过检查线段端点是否在另一条线段上来判断。
直线平行判断： a → × b → = 0 \overrightarrow{a}\times\overrightarrow{b} =0 a ×b =0

(三)点与多边形

1.如何判断点在多边形内？
射线法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。

如上图，红点左右两边都是奇数个交点。
特殊情况：

边上的点是否与射线相交，我们只需判断线段的两个端点是否在射线的两侧，在射线上或上方的端点我们把它认为是同一种情况。上图中边a的一个端点在射线的下方，另一个端点在射线上或上方，所以边a与射线相交，而边b和边c的两个端点都在射线上或上方，所以边b和边c与射线不相交。

这篇关于计算几何基础的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！