点到线段的距离计算方法

小咪咪 2023-10-11 12:38 65阅读 0赞

> 点C到线段AB的距离计算有以下几种计算方法
> 
> 和点到直线的距离计算方式不一样，直线是无限延伸的所以直接计算即可，但由于点和线段的位置不确定，所以我们不管使用何种办法都需要判断点和线段的位置关系，其存在以下几种关系：
> 
> 第一种：点在线段上没啥好说的判断一下即可
> 
> 第二种：点不在线段上：点C向线段AB做垂线，与线段AB所在直线的交点为D
> 
>        第一类：D点不在线段上，一种可能是在A点这边，另一种在B点这边
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlZTM3MTA0Mg_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlZTM3MTA0Mg_size_16_color_FFFFFF_t_70 1][]
> 
>      第二类：D点在线段AB上如下
> 
> ![20190923174933919.png][]
> 
> 第一种最好想到的：数学计算方式，需要高中知识即可求解，先判断点和线段的关系属于哪一种，从在线段上再到上面的，然后进行计算，判断点到线段方向的垂线是否落在线段上的方法是通过比较横纵坐标的方式来判断。这种方法思路简单，比较容易理解，但是由于需要计算的东西比较多，设计的计算量比较大，计算比较复杂，所以我们一般是不会采用这种计算方式。
> 
> 第二种
> 
> 第三种利用叉积点积向量法来做，这种方法感觉有点复杂（PS：实际是自己太菜了）但是是最简单的一种方法
> 
> ![20190923180856334.png][]
> 
> 这个图只是其中一种情况其它的都大差不差，不在一一列举，这里我们用点积判断
> 
> 点积：（是一个标量，不需要考虑方向）
> 
> ### 代数定义 ###
> 
> 设二维空间内有两个向量![format_png][] 和![format_png 1][] ，定义它们的数量积（又叫内积、点积）为以下实数![format_png 2][]
> 
> 更一般地，n维向量的内积定义如下： ![format_png 3][]
> 
> ### 几何定义 ###
> 
> 设二维空间内有两个向量![format_png 4][] 和![format_png 5][]，![format_png 6][] 和![format_png 7][] 表示向量a和b的大小，它们的夹角为![format_png 8][] 则内积定义为以下实数：![format_png 9][]该定义只对二维和三维空间有效。
> 
> 这个运算可以简单地理解为：在点积运算中，第一个向量投影到第二个向量上（这里，向量的顺序是不重要的，点积运算是可交换的），然后通过除以它们的标量长度来“标准化”。这样，这个分数一定是小于等于1的，可以简单地转化成一个角度值。
> 
> 这里可得到角的余弦值=![format_png 4][]![format_png 5][]/（![format_png 6][]![format_png 7][])因为分母肯定大于0所以我们只需要判断向量ab积的正负即可
> 
> 正为锐角，0为垂直，负为钝角
> 
> 代码：
> 
>     #include<set>
>     #include<map>
>     #include<ctime>
>     #include<stack>
>     #include<queue>
>     #include<cmath>
>     #include<string>
>     #include<vector>
>     #include<cstdio>
>     #include<cstring>
>     #include<cstdlib>
>     #include<iostream>
>     #include<algorithm>
>     using namespace std;
>     typedef long long ll;
>     #define inf 0x3f3f3f
>     #define bug  printf("bug\n")
>     const int maxn=1e6+10;
>     const double pi=acos(-1.0);
>     const double esp=1e-6;
>     const int N=2e2+10;
>     struct point
>     {
>         double x,y;
>     };
>     struct line
>     {
>         point st,ed;
>         double k,b;
>     };
>     int sign(double x)
>     {
>         if(fabs(x)<esp)
>             return 0;
>         return x>0?1:-1;
>     }
>     double dis(point a,point b)
>     {
>         return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
>     }
>     double cmult(point a,point b,point c)///叉积
>     {
>         return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
>     }
>     double pmult(point a,point b)///点积 这里的ab表示的是向量
>     {
>         return a.x*b.x+a.y*b.y;
>     }
>     ///如何判断点是否在线段上且距离线段的最短距离是多少
>     double pldis(point a,line l)
>     {
>         point s1,s2,s3;
>         s1.x=l.ed.x-l.st.x,s1.y=l.ed.y-l.st.y;
>         s2.x=a.x-l.st.x,s2.y=a.y-l.st.y;
>         s3.x=a.x-l.ed.x,s3.y=a.y-l.ed.y;
>         if(l.st.x==l.ed.x&&l.st.y==l.ed.y)
>             return dis(a,l.st);
>         if(sign(pmult(s1,s2))<0)///两向量成钝角
>             return dis(a,l.st);
>         else if(sign(pmult(s1,s3))>0)
>             return dis(a,l.ed);
>         else///该处为c在线段上方
>             return fabs(cmult(l.st,a,l.ed))/dis(l.st,l.ed);///两向量组成的三角形的面积为此两向的叉积的二倍，所以知道面积和底边就可以求出高
>     }
> 
>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlZTM3MTA0Mg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190923174422481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlZTM3MTA0Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlZTM3MTA0Mg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190923174627873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlZTM3MTA0Mg==,size_16,color_FFFFFF,t_70
[20190923174933919.png]: https://img-blog.csdnimg.cn/20190923174933919.png
[20190923180856334.png]: https://img-blog.csdnimg.cn/20190923180856334.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS8tZm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vYTFlYzA4ZmE1MTNkMjY5N2U3YTM1MzRiNTNmYmIyZmI0MzE2ZDhiMC5qcGc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS85NG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vZDUwNzM1ZmFlNmNkN2I4OWVlZDY2MTk1MDkyNDQyYTdkOTMzMGU2OS5qcGc?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS8tNG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vOTE1Mjk4MjI3MjBlMGNmMzFiMmUxNWVkMGM0NmYyMWZiZjA5YWFjZi5qcGc?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS83UG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vMjAzZmI4MGU3YmVjNTRlN2I5MWFjOTNmYjIzODliNTA0ZmMyNmExOS5qcGc?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS8tNG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vNGQwODZlMDYxZDk1MGE3YmFlMWIxNGQyMGNkMTYyZDlmMmQzYzlmZS5qcGc?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS8tZm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vMTRjZTM2ZDNkNTM5YjYwMGRjMjQ1NWExZWY1MDM1MmFjNjVjYjczYS5qcGc?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS8tdm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vOTYyYmQ0MDczNWZhZTZjZGM2MDY4NGU4MDNiMzBmMjQ0M2E3MGY4Yy5qcGc?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS8tdm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vZDUwNzM1ZmFlNmNkN2I4OTIzNTMxNDBhMDMyNDQyYTdkOTMzMGU3Zi5qcGc?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS8tNG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vMzdkMTJmMmViOTM4OWI1MDQzY2VhNzQ0ODMzNWU1ZGRlNzExNmVmNi5qcGc?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS85Zm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vNzI4ZGE5NzczOTEyYjMxYjIyMTU4OTNmODAxODM2N2FkYWI0ZTFhZi5qcGc?x-oss-process=image/format,png