精华内容
下载资源
问答
  • 知识都是环环相扣的, 在阅读这编文章之前, 要求懂两个知识点 1. 会求点到线段的最短距离 传送门 2. 会判断点与线段位置关系 传送门 如果上面两个知识点都懂, 那么就进入正题了 ...(1) 两线段相交成 X...

    知识都是环环相扣的, 在阅读这编文章之前, 要求懂两个知识点

    1. 会求点到线段的最短距离     传送门

    2. 会判断点与线段位置关系     传送门

     

    如果上面两个知识点都懂, 那么就进入正题了

    给出点A1、A2的坐标, 构成线段A1A2, 再给出点B1,B2的坐标, 构成线段B1B2, 求线段A1A2与线段B1B2的最短距离

    两条线段的摆放有很多情况

    (1) 两线段相交成 X 型

    (2) 两线段相交成 T 型

    (3) 两线段相交成 ^ 型, 其中有两点重合

    (4) 四个点在一条直线上, 视为相交

    (5) 两线段不相交

    判断两线段是否相交

    (1)(2)(3)(4)是两条线段相交的例子, 对于两线段相交的情况, 距离为0, 只要对[判断点与线段位置关系]加以应用, 就能轻松判断出两线段是否相交。

    分别检查两条线段, 如果双方都符合"另一条线段的两个端点分别位于当前线段的顺时针方向和逆时针方向", 则两条线段相交。

    判断线段A1A2与线段B1B2是否相交的程序可以像下面这样写

    if (dir(A1, A2, B1)*dir(A1, A2, B2) <= 0 && dir(B1, B2, A1)*dir(B1, B2, A2) <= 0)  
        cout << "相交" << endl;  

    只要事先将 dir 返回值定义为

    逆时针             返回   -1

    顺时针             返回    1

    反向延长线上  返回    -2

    延长线上          返回    2

    线段上              返回    0

    dir(A1,A2,B1)*dir(A1,A2,B2) 在B1、B2位于不同侧时就会得出 -1,B1或B2位于线段A1A2上时得出0。点A1、A2相对于线段B1B2的位置也是同理。接下来, 只要线段A1A2、B1B2的判断均小于等于0, 即可确定他们相交。

    若不相交, 求两线段最短距离

    在了解如何求点到线段的最短距离, 这就好办了

    线段A1A2与线段B1B2的距离为以下四个距离中最小的一个

    1.点A1到线段B1B2的距离

    2.点A2到线段B1B2的距离

    3.点B1到线段A1A2的距离

    4.点B2到线段A1A2的距离

    程序代码参考

    #include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    typedef struct node
    {
    	double x, y;
    }Point, Vector;
    double cross(Point A, Point B, Point P)      //向量AB与向量AP的外积(叉积)
    {
    	Vector AB = { B.x - A.x, B.y - A.y };
    	Vector AP = { P.x - A.x, P.y - A.y };
    	return AB.x*AP.y - AB.y*AP.x;
    }
    double dot(Point A, Point B, Point P)         //向量AB与向量AP的内积(点积)
    {
    	Vector AB = { B.x - A.x, B.y - A.y };
    	Vector AP = { P.x - A.x, P.y - A.y };
    	return AB.x*AP.x + AB.y*AP.y;
    }
    double dis2(Point a, Point b)                //点a、b距离的平方
    {
    	return (a.x - b.x)*(a.x - b.x) + (a.y-b.y)*(a.y-b.y);
    }
    int dir(Point A, Point B, Point P)            //点P与线段AB位置关系
    {
    	if (cross(A, B, P) < 0) return -1;     //逆时针
    	else if (cross(A, B, P)>0) return 1;   //顺时针
    	else if (dot(A, B, P) < 0) return -2;  //反延长线
    	else if (dot(A, B, P) >= 0&&dis2(A,B)>=dis2(A,P))
    	{
    		if (dis2(A, B) < dis2(A, P)) return 2;  //延长线
    		return 0;                          //在线上
    	}                                      
    }
    double disMin(Point A, Point B, Point P)      //点P到线段AB的最短距离
    {
    	double r = ((P.x-A.x)*(B.x-A.x) + (P.y-A.y)*(B.y-A.y)) / dis2(A, B);
    	if (r <= 0) return sqrt(dis2(A, P));
    	else if (r >= 1) return sqrt(dis2(B, P));
    	else
    	{
    		double AC = r*sqrt(dis2(A,B));
    		return sqrt(dis2(A,P)-AC*AC);
    	}
    }
    int main()
    {
    	Point A1, A2, B1, B2;
    	cin >> A1.x >> A1.y;
    	cin >> A2.x >> A2.y;
    	cin >> B1.x >> B1.y;
    	cin >> B2.x >> B2.y;
    	if (dir(A1, A2, B1)*dir(A1, A2, B2) <= 0 && dir(B1, B2, A1)*dir(B1, B2, A2) <= 0)  //两线段相交, 距离为0
    		cout << 0 << endl;
    	else                                                   //如不相交, 则最短距离为每个端点到另一条线段距离的最小值
    		cout << min(min(min(disMin(A1, A2, B1), disMin(A1, A2, B2)), disMin(B1, B2, A1)),disMin(B1,B2,A2)) << endl;  
    	return 0;
    }
    

    参考书籍: 挑战程序设计竞赛2

    展开全文
  • 条未知曲线,求其最短距离

    千次阅读 2016-01-04 11:25:24
    条未知的不规则的的曲线,现在已经获取近似点,如何求得一条曲线的任意一点到另一条曲线的最短距离,用C++算法编程实现。
    有两条未知的不规则的的曲线,现在已经获取近似点,如何求得一条曲线的任意一点到另一条曲线的最短距离,用C++算法编程实现。
    
    展开全文
  • arcgis engine计算点到线最短距离

    千次阅读 2018-05-08 01:36:00
    arcgis engine计算点到线最短距离 IProximityOperator接口用于获取个几何图形的距离,以及给定一个Point,求另一个几何图形上离离给定点最近的点。IProximityOperator接口的主要方法有:QueryNearesPoint,...

    arcgis engine计算点到线的最短距离

    IProximityOperator接口用于获取两个几何图形的距离,以及给定一个Point,求另一个几何图形上离离给定点最近的点。IProximityOperator接口的主要方法有:QueryNearesPoint,ReturnDistance, ReturnNearestPoint
    ReturnDistance方法用于返回两个几何对象间的最短距离,QueryNearesPoint方法用于查询获取几何对象上离给定输入点的最近距离的点的引用,ReturnNearestPoint方法用于创建并返回几何对象上离给定输入点的最近距离的点

    1. IMap pMap = axMapControl1.Map;
    2.            ILayer pLayer = null;
    3.            IPoint po=null;
    4.            IPolyline pl=null;
    5.            IFeatureLayer featurelayer=null;
    6.            IFeatureClass featureclass = null;
    7.            IGraphicsContainer gra;
    8.            IElement ptele;
    9.            IPointCollection lineptcol;
    10.            gra = axMapControl1.Map as IGraphicsContainer;
    11.            lineptcol = new PolylineClass();
    12.            for (int i = 0; i < pMap.LayerCount; i++)
    13.            {
    14.                pLayer = pMap.get_Layer(i);
    15.                 featurelayer = pLayer as IFeatureLayer;
    16.                 featureclass = featurelayer.FeatureClass;
    17.                IFeature feature = featureclass.GetFeature(0);
    18.  
    19.                if (feature.Shape is IPoint)
    20.                {
    21.                    po = feature.Shape as IPoint;
    22.                }
    23.                else {
    24.                     pl = feature.Shape as IPolyline;
    25.                }
    26.                //MessageBox.Show("qqqq");
    27.            }
    28.  
    29.            double dis = GetTwoGeometryDistance(po, pl);
    30.            IPoint po2 = NearestPoint(po, pl);
    31.            object a = Type.Missing;
    32.            lineptcol.AddPoint(po, ref a, ref a);
    33.            lineptcol.AddPoint(po2, ref a, ref a);
    34.            IElement lineele = new LineElementClass();
    35.            IPolyline pline = new PolylineClass();
    36.            pline = lineptcol as IPolyline;
    37.            lineele.Geometry = pline as IGeometry;
    38.            gra.AddElement(lineele, 0);
    39.            axMapControl1.Refresh();
    40.            MessageBox.Show(dis.ToString());

    计算几何图形之间的距离

    1. public double GetTwoGeometryDistance(IGeometry pGeometryA, IGeometry pGeometryB)
    2.         {
    3.             IProximityOperator pProOperator = pGeometryA as IProximityOperator;
    4.             if (pGeometryA != null || pGeometryB != null)
    5.             {
    6.                 double distance = pProOperator.ReturnDistance(pGeometryB);
    7.                 return distance;
    8.             }
    9.             else
    10.             {
    11.                 return 0;
    12.             }
    13.         }

    离给定的几何图形最近的点

    1. //离给定的几何图形最近的点
    2.         public IPoint NearestPoint(IPoint pInputPoint, IGeometry pGeometry)
    3.         {
    4.             try
    5.             {
    6.                 IProximityOperator pProximity = (IProximityOperator)pGeometry;
    7.                 IPoint pNearestPoint = pProximity.ReturnNearestPoint(pInputPoint, esriSegmentExtension.esriNoExtension);
    8.                 return pNearestPoint;
    9.             }
    10.             catch (Exception Err)
    11.             {
    12.                 MessageBox.Show(Err.Message, "提示", MessageBoxButtons.OK, MessageBoxIcon.Information);
    13.                 return null;
    14.             }
    15.         }

    计算出来最近的点,然后和初始的那个点连成一个线,也就做出了直线的中垂线

    posted on 2018-05-08 01:36 gisery 阅读(...) 评论(...) 编辑 收藏
    展开全文
  • 基本上可以认为地球是个球体,如果飞机在个城市之间飞行,最好的飞行线路是取这个城市之间的最短距离。这其实课看成球面上任意点之间的最短距离。过球面上的任意点以及球心可以做一个截平面,与球面的截痕为...

    为何地图上的航线是曲线

    如果我们观察地图上的航线,就会发现航线是弯曲的。

    0d8836265f25acae002ecdfe5b968646.png

    基本上可以认为地球是个球体,如果飞机在两个城市之间飞行,最好的飞行线路是取这两个城市之间的最短距离。这其实课看成球面上任意两点之间的最短距离。过球面上的任意两点以及球心可以做一个截平面,与球面的截痕为一个圆,这个圆的大小不随两点不同而变化,半径都是球半径。这个圆是任意平面与球面相截得到的所有不同的圆中,半径最大的,因此叫做大圆。而只要你沿着球表面做线连接任意两个点,曲线长度最短的一定是这个大圆的劣弧长度。航线按两个城市之间的大圆弧航行才最经济。地图是球面向平面做投影做出来的,所以我们看到的航线就是曲线了。

    定理:球面上任意两点间的距离以大圆最短

    初等几何的观察

    如图AB是连接A,B两点的大圆弧,C是AB弧上的任意一点,过C做以A,B为极点的圆,设AF,GF,GB为一条球面曲线,且BG是大圆弧,AF也是大圆弧

    则CB=BG,AC=AF,但AF+FG+GB>AF+GB=AC+CB=AB.

    如果B,E,D,A是另外一条球面上的曲线,过B,D,A的球面三角形中AD+BD>AB,

    过E,B,A的球面三角形中亦有BE+AE>AB。

    8ea316fa8eba27196d244dfc10eb7b64.png

    微积分证明

    下面我们利用球面坐标系与微积分给出一个精确的证明。

    令A,B是半径为R的球面上的任意两点,C为球心,大圆弧长可以表达为

    dd93967178744ffd126f7215b916d7fb.png

    以C为中心建立直角坐标系,让A在z轴上,则球面上任意一点P的坐标可以写成:

    ecf685580f40d4e3ecb8592426f7e0ae.png
    860a4e599e99c06c7caf0b214d0c423e.png

    空间中任意曲线的长度可以定义为:

    467ba0afe74b81cec1dca2154e352e1a.png

    其中s是参数,对球面曲线就有

    bd7bc58b81d79bf72289dac8bb40025d.png

    所以

    256509900e239dbaf744c1be84af46e9.png

    上式严格成立,也就是要求不论s取值如何都不能离开大圆弧AB时等式严格成立,这就证明了球面上两点的最短距离为大圆弧。这个距离被高斯称为球面测地线。

    展开全文
  • 基本上可以认为地球是个球体,如果飞机在个城市之间飞行,最好的飞行线路是取这个城市之间的最短距离。这其实课看成球面上任意点之间的最短距离。过球面上的任意点以及球心可以做一个截平面,与球面的截痕为...
  • 现在我要获取每个面到线最短距离,怎么做了?用arcgis一般的人还是很难会操作的(很熟练的就别论了)。现在如何简单快速的解决?,降级使用者的门槛?现在打开我们的程序。输入个数据, 点击计算,计算完成后...
  • 就是一个简单的bfs的问题,这里用队列来解决问题,有栈来输出路径。 #include"iostream" #include"stdio.h" #include"algorithm" #include"queue" #include"string.h" #include"cmath" ...int vi...
  • 参考JTS的CGAlgorithms类distancePointLine方法,实现原理是根据向量原理进行计算 利用向量积(叉积)计算三角形...在这里θ表示向量之间的角夹角(0° ≤ θ ≤ 180°),它位于这个矢量 所定义的平面上。 向...
  • function dist(x, y, startx, starty, endx, endy) { var se = (startx-endx)*(startx-endx)+(starty-endy)*...//线段距离平方 var p = ((x-startx)*(endx-startx)+(y-starty)*(endy-starty)); //向量...
  • 直线的信息可以以个端点的形式给出,也可以以一个直线上的点和直线的方向向量给出。本文中假设这条直线不...求直线的最短距离? 直线l0我们可以用方程表示为:  (1) 直线段l1我们也可以用方程表示为:  
  • 光明小学的小朋友们要举行一年一度的接力跑大赛了,但是小朋友们却遇到了一...光明小学的小朋友们希望全盘考虑所有的因素,所以你需要把任意点间经过M条边的最短路径的距离输出出来以供参考。 你需要设计这样一个...
  • 三维空间碰撞问题;空间中两直线的最短距离及最近点   (2013-02-28 16:26:39)   ...分类: 计算机图形学 ...已知空间中两线段,...问题的关键是求出这两条任意直线之间的最短距离,以及在这个距离上的两线最接近点
  • 在我们只知道:如何计算点之间的距离直线上的一个点可以表示为点和一个参数的函数我们知道求函数的最小值(列表与代码块不是朋友)def distance(a, b):"""Calculate a distance between two points."""return n...
  •  通过线段端点,写成参数函数(考虑了斜率不存在的问题) 程序: function practice(points1,points2) g=points1(2)-points1(4); h=points1(1)-points1(3); if g&lt;0|h&lt;0 t1=-1:0...
  • 光明小学的小朋友们要举行一年一度的接力跑大赛了,但是小朋友们却遇到了一个...光明小学的小朋友们希望全盘考虑所有的因素,所以你需要把任意点间经过M条边的最短路径的距离输出出来以供参考。 你需要设计这样一...
  • 线段间最短距离

    2014-05-23 10:14:01
    两线段用其端点s1: (p1a,p1b),s2: (p2a,p2b)表示 ... 若两线段有交点,距离d为0 b. 计算两线段端点到对方线段所在直线l1, l2的距离。  d(p1a,l2), d(p1b,l2), d(p2a,l1),d(p2b,l1)  选择距离最小,且垂足落
  • JavaScript中点到一个直线的最短距离(面积算法)(2D) 这天遇见个问题,平面上计算点到直线的距离,原来数学白学了。不过还是搞出来了。记录一下伤员吗 /** * 点到线的最短距离实际上就是点到线的垂直距离。 *...
  • 设有两空间线段 $L_s$,其起点、终点坐标为$ s_0、s_1 $,方向向量$\vec u = s_1-s_0 $ $L_t$,其起点、终点坐标为$ t_0、t_1 $,方向向量$\vec v =...及两线段对应的直线为$l_s、l_t$,采用向量表示法如下: $l_s ...
  • 2.判断晨昏线的三大技法(1)利用自转方向判断:顺自转方向将要进入白天的为晨线,将要进入黑夜的为昏线。(2)利用地方时判断:赤道上地方时为6时的点所在为晨线,为18时的点所在为昏线。(3)利用昼夜半球位...
  • * 表面上同一经线圈上相差1"点间的距离为 2πR/360/3600 * 表面上同一纬线圈上相差1"点间的距离为 2πR×cos(纬度)/360/3600 * 当R取半径平均值6371km时, * 地球表面上同一经线圈上相差1"点间的距离约为...
  • 大意:求解个凸多边形的最短距离。 分析:依然是旋转卡壳来解决。用一对平行支撑线围绕个凸多边形来寻找最短的距离。 计算P多边形y最小的端点和y最大的端点,即ymin,ymax 通过ymin,ymax构造条支撑射线LP和LQ...
  • /// 根据经纬度值计算出点与直线的距离 /// </summary> /// <param name="x">点的x坐标</param> /// <param name="y">点的y坐标</param> /// <param name="x1">线的第一个...
  • 一个最简单的例子:如果你是一个滑雪运动员,目标是最短时间冲线,你根本就不在乎点间的最短路径,而是最快路径。如果你沿着最佳曲线下滑,你会获得更多的优势……顺势借力 开拓创新从起点到终点,有无数条道路,...
  • 全文共4129字,预计学习...这正是我们三维宇宙空间的运行规律:在平面中,点之间直线距离最短。无论如何旋转、定向或以其他方式定位这个点,这个规律都是成立的。 但是我们的宇宙不仅由三个空间维度组成,而...
  • 通常最短路线问题是以“平面内连结点的线中,直线段最短”为原则引申出来的.人们在生产、生活实践中,常常遇到带有某种限制条件的最近路线即最短路线问题.在本讲所举的例中,如果研究问题的限制条件允许已知的...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 359
精华内容 143
关键字:

两线最短距离