iClient for JavaScript求两线交点、线线打断、点打断线
宗政斌
作者：MR.
完整代码[^footnote]在页面底部提供下载
一、求两线交点
###1. 思路
线都是由数量不等的点连起来形成的。计算两条线的交点，我们需要一个基础算子，其中一个办法是判断两条线段（两点相连）是否相交、相交的话算出交点。有了这个算子，我们循环整条线就行了，比较好的办法是把整条线上，每相邻两点取到的线段，按x坐标排下序，再去循环执行算子。
###2. 计算线段交点算子
两条线段求交点使用数学的办法就可以了，这里不再赘述。关于容限的处理可以在下面下载完整代码查看。
//参数seg1、seg2{x1,x2,y1,y2}(x1<x2);options{pOrl:Boolean,tolerance:number}
var pOrl = options && options.pOrl;//是否返回交点或交线
var tolerance = options && options.tolerance;//容限，低于它视为相交
var intersection = false;//返回值，不相交返回false，否则true或
//{SuperMap.Geometry.Point}或{SuperMap.Geometry.LineString}
var x11_21 = seg1.x1 - seg2.x1;
var y11_21 = seg1.y1 - seg2.y1;
var x12_11 = seg1.x2 - seg1.x1;
var y12_11 = seg1.y2 - seg1.y1;
var y22_21 = seg2.y2 - seg2.y1;
var x22_21 = seg2.x2 - seg2.x1;
var d = (y22_21 * x12_11) - (x22_21 * y12_11);
var n1 = (x22_21 * y11_21) - (y22_21 * x11_21);
var n2 = (x12_11 * y11_21) - (y12_11 * x11_21);
if(d == 0) {
// 平行
if(n1 == 0 && n2 == 0) {
// 重合
if(!pOrl){
intersection=true
}else{//返回交线
var spt=seg1.x1>seg2.x1?seg1:seg2;
var ept=seg1.x2<seg2.x2?seg1:seg2;
intersection = new SuperMap.Geometry.LineString(
[new SuperMap.Geometry.Point(spt.x1,spt.y1),
new SuperMap.Geometry.Point(ept.x2,ept.y2)]);
}
}
} else {
var along1 = n1 / d;
var along2 = n2 / d;
if(along1 >= 0 && along1 <= 1 && along2 >=0 && along2 <= 1) {
// 相交
if(!pOrl) {
intersection = true;
} else {
// 计算交点
var x = seg1.x1 + (along1 * x12_11);
var y = seg1.y1 + (along1 * y12_11);
intersection = new SuperMap.Geometry.Point(x, y);
}
}
}
###3. 线上相邻点组成的线段循环代入算子
首先上述算子的线段要求x1 < x2，其次，我们还需要去循环判断两条线上的线段是否分别相交，我们需要先处理下线，使其线段按起点x坐标递增排序，方法如下（采用快速排序）：
function getSortedSegments(line) {//line{SuperMap.Geometry.LineString}
//快速排序
// var quickSort = function(arr) {
// if (arr.length <= 1) { return arr; }
// var pivot = arr[0];
// var left = [];
// var right = [];
// for (var i = 1; i < arr.length; i++){
// if (arr[i] < pivot) {
// left.push(arr[i]);
// } else {
// right.push(arr[i]);
// }
// }
// return quickSort(left).concat([pivot], quickSort(right));
// };
//每相邻两点视为整体执行快速排序
var arr=line.components;
if(!arr.length){return [];}
var pivot=[{
x1: arr[0].x,
y1: arr[0].y,
x2: arr[1].x,
y2: arr[1].y,
}];
if(arr.length==2){
return pivot;
}
var left = {components:[]};
var right = {components:[]};
var i=!line.CLASS_NAME ? 2 : 1;
var spt,ept;
while(i<arr.length-1){
spt=arr[i].x<arr[i+1].x?arr[i]:arr[i+1];
ept=arr[i].x>arr[i+1].x?arr[i]:arr[i+1];
if(arr[i].x<=pivot[0].x1){
left.components.push({x:spt.x,y:spt.y});
left.components.push({x:ept.x,y:ept.y});
}else{
right.components.push({x:spt.x,y:spt.y});
right.components.push({x:ept.x,y:ept.y});
}
if(!line.CLASS_NAME){
i+=2;
}else{
i++;
}
}
return getSortedSegments(left).concat(pivot, getSortedSegments(right));
}
接下来，找出两条线的交点：
//计算两条线交点
function intersects(line1,line2){
var intersect = false;
//无交点返回false，否则[{SuperMap.Geometry.Point}，{SuperMap.Geometry.LineString}]
var type1 = line1.CLASS_NAME;
var type2 = line2.CLASS_NAME;
if(type1 === "SuperMap.Geometry.LineString" ||
type1 === "SuperMap.Geometry.LinearRing" ||
type1 === "SuperMap.Geometry.Point" ||
type2 === "SuperMap.Geometry.LineString" ||
type2 === "SuperMap.Geometry.LinearRing" ||
type2 === "SuperMap.Geometry.Point") {
var segs1;
var segs2;
if(type1 === "SuperMap.Geometry.Point") {
segs1 = [{
x1: line1.x, y1: line1.y,
x2: line1.x, y2: line1.y
}];
} else {
segs1 = getSortedSegments(line1);
}
if(type2 === "SuperMap.Geometry.Point") {
segs2 = [{
x1: line2.x, y1: line2.y,
x2: line2.x, y2: line2.y
}];
} else {
segs2 = getSortedSegments(line2);
}
var seg1, seg1x1, seg1x2, seg1y1, seg1y2,
seg2, seg2y1, seg2y2;
// 判断俩线段位置
for(var i=0, len=segs1.length; i<len; i++) {
seg1 = segs1[i];
seg1x1 = seg1.x1;
seg1x2 = seg1.x2;
seg1y1 = seg1.y1;
seg1y2 = seg1.y2;
for(var j=0, jlen=segs2.length; j<jlen; j++) {
seg2 = segs2[j];
if(seg2.x1 > seg1x2) {
// seg1在seg2左边
break;
}
if(seg2.x2 < seg1x1) {
// seg1在eg2右边
continue;
}
seg2y1 = seg2.y1;
seg2y2 = seg2.y2;
if(Math.min(seg2y1, seg2y2) > Math.max(seg1y1, seg1y2)) {
// seg2在seg1上
continue;
}
if(Math.max(seg2y1, seg2y2) < Math.min(seg1y1, seg1y2)) {
// seg2在seg1下
continue;
}
var result=intersectoperator(seg1, seg2,{pOrl:true})；
result.line=[line1.id,line2.id];//标记结果
if(result) {
if(!intersect){
intersect={
points:[],
lines:[]
};
}
if(result.CLASS_NAME==="SuperMap.Geometry.Point"){
intersect.points.push(result);
}else{
intersect.lines.push(result);
}
}
}
}
} else {
intersect = line1.intersects(line2);
//调用SuperMap.Geometry对象方法返回是否相交bool值
}
return intersect;
}
如果有需要你可以基于上述获取两线交点/线的方法来对更多的线求交点/线，在得到结果时，给结果加上属性标记，标记它是哪两条线的交点/线，还需要判断是否多条线有共同的交点/线，有的话，增加标记属性。
下面示例求出整个Vector图层上所有线之间的交点（未判断该图层上是否都是线）：
//计算多条线交点
function getlinescrosspt(lines){//lines[SuperMap.Geometry.LineString]
var result={points:[],lines:[]},tempresult;
//result{points:[{SuperMap.Geometry.Point}]，lines:[{SuperMap.Geometry.LineString}]}
for(var i =0; i<lines.length-1;i++){
for(int j=i+1;j<lines.length;j++){
tempresult=intersects(lines[i],lines[j]);
if(tempresult){
//判断result是否存在相同结果，是则增加标记
for(var m in tempresult.points){//点
var ptflag=true;
for(var n in result.points){
if(result.points[n].toString()==tempresult.points[m].toString()){
//增加标记
for(var pt1 in tempresult.points[m].line){
var attflag=true;
for(var pt2 in result.points[n].line){
if(tempresult.points[m].line[pt1]==result.points[n].line[pt2]){
attflag=false;
break;
}
}
if(attflag){
result.points[n].line.push(tempresult.points[m].line[pt1]);
}
}
ptflag=false;
break;
}
}
if(ptflag){
result.points.push(tempresult.points[m]);
}
}
//线与点类似
}
}
}
return result;
}
另外，结果是线段的话，需不需要把有共同点的线段连成一条线、结果线如何标记需要根据不同情况做不同调整，这里不做上述处理。
二、线线打断
###1.思路
线线打断还是需要先求交点，上面的例子已经可以得到两线之间的交点并标记了属性，但是我们需要知道交点的精确位置，因此，我们需要把前面的几个方法修改一下，让其返回交点在各条线分别的位置，然后可以根据交点及所在位置拆分一条线为多条。
###2.实现
首先，在getSortedSegments方法里标记每个点在原数组的位置：
function getSortedSegments(line) {//line{SuperMap.Geometry.LineString}
//省略...
var pivot=[{
x1: arr[0].x,
y1: arr[0].y,
pos1:arr[0].pos||[line.id,0],
x2: arr[1].x,
y2: arr[1].y,
pos2:arr[1].pos||[line.id,1]
}];
//省略...
var spt,ept;
while(i<arr.length-1){
//标记点原始位置
if(arr[i].x<=arr[i+1].x){
spt={x:arr[i].x,y:arr[i].y};
ept={x:arr[i+1].x,y:arr[i+1].y};
if(line.CLASS_NAME){
spt.pos=[line.id,i];
ept.pos=[line.id,i+1];
}else{
spt.pos=arr[i].pos;
ept.pos=arr[i+1].pos;
}
}else{
spt={x:arr[i+1].x,y:arr[i+1].y};
ept={x:arr[i].x,y:arr[i].y};
if(line.CLASS_NAME){
spt.pos=[line.id,i+1];
ept.pos=[line.id,i];
}else{
spt.pos=arr[i+1].pos;
ept.pos=arr[i].pos;
}
}
//省略...
其次，在计算交点/线时，返回结果增加交点/线在线中的位置：
//计算线段交点
function intersectoperator(seg1, seg2, options){
//略...
if(intersection&&pOrl){
//判断点位置
var segs=[seg1, seg2];
intersection.pos=[];
var judgepoint=function(segs,intersection){
for(var k in segs){
if(segs[k].x1==intersection.x && segs[k].y1== intersection.y){
if(segs[k].pos1[0]!==true){
segs[k].pos1.unshift(true);
}
intersection.pos.push(segs[k].pos1);
}else if(segs[k].x2==intersection.x && segs[k].y2== intersection.y){
if(segs[k].pos2[0]!==true){
segs[k].pos2.unshift(true);
}
intersection.pos.push(segs[k].pos2);
}else{
intersection.pos.push([false,segs[k].pos1[0],segs[k].pos1[1],segs[k].pos2[1]]);
}
}
return intersection;
}
if(intersection.CLASS_NAME=="SuperMap.Geometry.Point"){
intersection=judgepoint(segs,intersection);
}else{
if(intersection.components[0].toString()==intersection.components[1].toString()){
//线的两点相等
intersection=intersection.components[0];
intersection.pos=[];
intersection=judgepoint(segs,intersection);
}else{
intersection.components[0].pos=[];
intersection.components[1].pos=[];
intersection.components[0]=judgepoint(segs,intersection.components[0]);
intersection.components[1]=judgepoint(segs,intersection.components[1]);
intersection.pos.push(intersection.components[0].pos.concat(intersection.components[1].pos));
}
}
}
return intersection;//点或线pos:[boolen，lineid，pos1，pos2]
}
然后，求多条线交点需要做与上面line属性相同操作，即，多条线共交点/线，增加位置标记。
最后，拿到交点/线，根据其位置从原来的线里取出对应点数组，即可完成线线打断的操作，为了方便处理，交点最好按其标记的位置增序排序。在getlinescrosspt的基础上处理，每趟一条线与后面的线求交点完成后就进行打断线操作，这里偷个懒，直接调用getlinescrosspt方法得到所有交点/线，再根据这些点/线去打断线。
//这里先得到线两两之间的交点
var result=getlinescrosspt(lines);console.log(result,"linexline");
//交点和交线做同样处理（可以只取其中一个点）
for(var x in result.lines){
result.points.push(result.lines[x].components[0]);
result.points.push(result.lines[x].components[1]);
}
var resultlines=[];
var getlinfeas=function(line,sortedpoints){//sortedpoints排序后的点结果
if(!sortedpoints.length){//该线上无断点
return [line];
}
var resultlines=[];
var linecoms=line.geometry.clone().components;
var lineid=line.attributes.ID
var lineflag=1;
var startpos=0,endpos;
var n;
for(n in sortedpoints){//从断点拆分线
var linefea;
//getstyle(label)，返回随机样式，参数为要显示的文本标签
if(sortedpoints[n].pos[0]){//当前断点是线组成点里的点
endpos=sortedpoints[n].pos[2];
if(endpos==0)continue;
linefea = new SuperMap.Feature.Vector(
new SuperMap.Geometry.LineString(linecoms.slice(startpos+1,endpos+1)),
{ID:lineid+"_"+lineflag},getstyle(lineid+"_"+lineflag));
if(n>0 && !sortedpoints[n-1].pos[0]){//上一个断点也不在线组分里
linefea.geometry.components.unshift(sortedpoints[n-1]);
}else{
linefea.geometry.components.unshift(linecoms[startpos]);
}
}else{
endpos=Math.min(sortedpoints[n].pos[2],sortedpoints[n].pos[3]);
linefea = new SuperMap.Feature.Vector(
new SuperMap.Geometry.LineString(linecoms.slice(startpos+1,endpos+1)),
{ID:lineid+"_"+lineflag},getstyle(lineid+"_"+lineflag));
linefea.geometry.components.push(sortedpoints[n]);
if(n>0 && !sortedpoints[n-1].pos[0]){//上一个断点也不在线组分里
linefea.geometry.components.unshift(sortedpoints[n-1]);
}else{
linefea.geometry.components.unshift(linecoms[startpos]);
}
}
resultlines.push(linefea);
startpos=endpos;
lineflag++;
}
n=parseInt(n);
if(startpos!=linecoms.length-1){
var linefea = new SuperMap.Feature.Vector(
new SuperMap.Geometry.LineString(linecoms.slice(startpos,linecoms.length)),
{ID:lineid+"_"+lineflag},getstyle(lineid+"_"+lineflag));
if(!sortedpoints[n].pos[0]){//最后一个断点不是线组成点
linefea.geometry.components[0]=sortedpoints[n];
}
resultlines.push(linefea);
}
return resultlines;//直接返回设置了样式的线要素而不是Geometry对象
};
var sortresultpt=function(result,lineid){//返回匹配的线id排序后的断点
var sortedpoints=[];
for(var j in result.points){//结果点
var rstpt=result.points[j].clone();//Geometry克隆对象方法
for(var k in rstpt.pos){//对比标记
if(rstpt.pos[k][1]==lineid){//是此线交点
//插入排序
rstpt.pos=rstpt.pos[k];
if(!sortedpoints.length){
sortedpoints.push(rstpt);
break;
}
var maxflag=true;
for(var m in sortedpoints){
if(rstpt.pos[2]<sortedpoints[m].pos[2]){
sortedpoints.splice(m, 0, rstpt);
maxflag=false;
break;
}
}
if(maxflag){
sortedpoints.push(rstpt);
break;
}
}
}
}
return sortedpoints;
};
for(var i in vectorLayer.features){//图层上的线
var lineid=vectorLayer.features[i].attributes.ID;//线id
var sortedpoints=sortresultpt(result,lineid);//按线id及位置排序后的点
resultlines=resultlines.concat( getlinfeas(vectorLayer.features[i],sortedpoints) );
}
//resultlines可直接添加到Vector图层上的线要素数组
三、点打断线
###1.思路
还是需要求点与线交点，前面写的求线段之间交点的方法也兼容点和线，并且可以设置容限，直接使用就行。但其实，intersectoperator（计算线段交点）方法调用了另一个方法，distanceToSegment，该方法计算并返回点到线段距离及垂足（点到线的垂线与线的交点），具体实现不再详述，可以在页面底部下载代码查看。所以，点打断线建议可以以distanceToSegment为算子另写个方法，可以提高少许执行效率，这里不再详述，直接使用线线相交的方法。另，SuperMap.Control.DrawFeature可以设置捕捉（snap）对象，方便画点时把点画在线上。
###2.实现
这里不再多说，请下载下面的代码查看。
四、拓展
有了前面的铺垫，我们还可以做别的更多的事情，比如，线打断面，面裁剪线等等。面对象和线对象类似，也是点串，所以上面说的操作都是基于带位置（数组位置）标记的交点/线。
可以看到其中还有不成熟的地方以及算法进一步优化的空间，欢迎大家讨论交流、批评指正。（查看CSDN账号资料联系我们）。
类似资料：