计算几何基础

目录

(一)点与线段

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与射线不相交。

上一篇:计算几何入门


下一篇:可数公理