文章版权由作者李晓晖和博客园共有，若转载请于明显处标明出处：http://www.cnblogs.com/naaoveGIS/。
1.背景
假设有两条轨迹，一条是预定轨迹，一条是实际轨迹，分别为L1、L2。L1由点（A1、A2、A3、...、AN）组成，L2由（B1、B2、B3、…、BM）组成。现在给出了一个容差范围，即L2上的点能与L1这条预定路线的垂直容差范围Range，求L2上满足要求的实际点。
这个需求我们实际可以分为两种情况来考虑，一种是此需求单纯的仅仅是要求得到与L1能有一定匹配度的点。但是，如果我们深入分析，会发现L1作为一条线，其本身是有方向性的，如果我们还将线的方向性考虑进来，即L2的点不仅要在与L1的Range范围内，还要此时的点的前进趋势与L1是相同的。
当然，我们通过AGS或者GeoServer之类的NA服务是可以实现最邻路径生成的方法的，这个方法我们留在我的从底层谈WebGIS的设计实现系列中跟大家一起探讨。这里我要跟大家讨论一种效率更高的方法，直接通过数据库的存储过程来实现。
我在上面提到的两种情况（不考虑方向性和考虑方向性），这两者是层层递进的。我们首先考虑如何通过不考虑方向性来解决。然后再进一步探讨如果有方向性，我们该用什么思路去实现。
2.不考虑方向性的算法实现
2.1进一步简化问题
这里，首先我们将问题进一步简化，即如何判断一个点是否落在两个点组成的线的容差范围内，距离描述为：a点、b点两个计划点，c点为实际点，现在要判断c点是否在a点和b点连接成的直线的容差范围内。
2.2解决简化问题的思路
我将解决步骤分为三步。分别为：1.粗略判断；2.判断是否落在线外；3.垂线判断。
详细过程便是：
A.粗略判断，c点和a点以及b点的连线是否在容差范围内，即ac或者bc是否在容差范围内。如果是，返回true。否则，进一步判断。
B.判断c点是否在ab直线的外侧，即c点到ab的垂足在ab的延长线上（如果是这种情况，只给一个容差范围是很难确定是否符合标准的，需要多个与容差有关的参数，比如水平容差和垂直容差等，为了简化，此种情况下，直接返回false）。如果垂足在ab上，则进行下一步。
C.算出c点到ab的垂线距离d。判断d是否在容差范围内，如果在，返回true；否则，返回false。
2.3实现判断点是否在线范围内（使用存储过程）
利用海伦公式求点到线段的距离。
传递的参数中。x0、y0、x1、y1为预定轨迹的两个坐标(P0,P1)，x2、y2为第三个坐标（实际位置S）的坐标, fRange为比对距离,return 0 超出，return 1未超出。
function getNearestDistance(x0 in number,y0 in number,x1 in number,y1 in number,x2 in number,y2 in number,fRange in number := 1,distance out number) return integer is
fa number(15,3);
fb number(15,3);
fc number(15,3);
fl number(15,3);
fs number(15,3);
begin
fa := sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
fb := sqrt((x0-x2)*(x0-x2)+(y0-y2)*(y0-y2));
fc := sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
if fa < fRange then --当fa边长度小于警告距离时
distance := fa;
return 1;
end if;
if fb < fRange then --当fb边长度小于警告距离时
distance := fb;
return 1;
end if;
if fc < 0.01 then --当轨迹的两个坐标点重合时
return 0;
end if;
if(fa*fa>=fb*fb+fc*fc) then --P0处角度为（钝（直）角），垂足在外
distance := fb;
return 0;
end if;
if(fb*fb>=fa*fa+fc*fc) then – P1处角度为（钝（直）角），垂足在外
distance := fa;
return 0;
end if;
--利用海伦公式求垂直距离
fl := (fa+fb+fc)/2; --周长的一半
fs := sqrt(fl*(fl-fa)*(fl-fb)*(fl-fc)); --海伦公式求面积，也可以用矢量求
distance := 2*fs/fc;
if distance < fRance then
return 1;
end if;
return 0;
end;
2.4实现整个流程
先查询得到整个预定线路的坐标，再查询出需要判断的点S，遍历整个预定线路判断S是否在整个线路的某条线段的容差范围内。
再查询出实际线路中的第二个实际点，重复上面的过程。
第一个过程的实现如下：
isOutOfRanceErr := 1;
open rs2 for select a.X,a.Y,b.X,b.Y,c.预警距离 from 坐标点表 a, 坐标点表 b, 轨迹表 c where a.轨迹ID=b.轨迹ID and a.轨迹ID = c.轨迹ID and a.坐标ID+1=b.坐标ID order by a.轨迹ID,a.坐标ID;
loop
Fetch rs2 into fP0X,fP0Y,fP1X,fP1Y,fToleRance;
Exit when rs%Notfound;
dummy := getNearestDistance(fP0X,fP0Y,fP1X,fP1Y,fCoordinateX,fCoordinateY,fToleRance,fDistance);
if dummy = 1 then
isOutOfRanceErr := 0;
exit;
end if;
end loop;
close rs2;
3.考虑方向性的算法的实现
如果轨迹的对比还考虑方向性，即线路a-b-c-d与线路a-c-b-d是不同，其实，此时只需要用一个变量来标记每一次吻合时，数组已经对比到的地方，下次对比时应该从标记处开始后推就能实现方向性问题了。
-----欢迎转载，但保留版权，请于明显处标明出处：http://www.cnblogs.com/naaoveGIS/
如果您觉得本文确实帮助了您，可以微信扫一扫，进行小额的打赏和鼓励，谢谢 ^_^
