当前位置: 首页 > 工具软件 > iClient-JS > 使用案例 >

iClient for JavaScript求两线交点、线线打断、点打断线

宗政斌
2023-12-01

作者: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账号资料联系我们)。

 类似资料: