大规模交叉节点判断

Q：给出所有点连接关系（矩阵形式）及节点坐标，找出所有交叉节点

idea：

1缩小范围

四点判断（a-b，c-d），排除①a和b的经度（纬度）最大值<c和d的经度（纬度）最小值②a和b的经度（纬度）最小值>c和d的经度（纬度）最大值的情况

basic knowledge：经度东>西，纬度北>南

如图，经度：max（a,b）<min(c,d)，不可能相交

2.利用两边斜率排除平行状况

3.求解方程组，得出交点坐标

https://wenku.baidu.com/view/9e769d1dc5da50e2524d7f21.html

4.判断交点在四点中心范围（利用经纬度），便记录下来

%% 寻找没名字的交叉点 输入矩阵 名字 坐标    输出 矩阵 名字 坐标
%crosss 序号一-序号二 序号三-序号四 在矩阵中j位置 在矩阵中i位置
% juzhen:direction
% lon_lat:node's coordinate
function [lon_lat_new,crosss]=findcrossbilibili(juzhen,lon_lat)
%% matrix to list:num x1 y1 x2 y2
count=0;
for i1=1:size(juzhen,1)
    for i2=1:size(juzhen,2)
        if juzhen(i1,i2)==1
            count=count+1;
            num(count,1)=i1;
            num(count,2)=i2;
        end
    end
end
% edge1:x1,y1  edge2:x2,y2
for i=1:size(num,1)
    x1(i,1)=lon_lat(num(i,1),1);
    y1(i,1)=lon_lat(num(i,1),2);
    x2(i,1)=lon_lat(num(i,2),1);
    y2(i,1)=lon_lat(num(i,2),2);
end
%% itself circle itself
count=0;
for j=1:size(x1,1)-1
    for i=1+j:size(x1,1)
        % shrink hunting zone
        if (min(x1(j,1),x2(j,1))>max(x1(i,1),x2(i,1)))||(max(x1(j,1),x2(j,1))<min(x1(i,1),x2(i,1)))||(min(y1(j,1),y2(j,1))>max(y1(i,1),y2(i,1)))||(max(y1(j,1),y2(j,1))<min(y1(i,1),y2(i,1)))
            % exclude the situation that one node of two edges
        elseif ((x1(j,1)==x1(i,1))&&(y1(j,1)==y1(i,1)))||((x1(j,1)==x2(i,1))&&(y1(j,1)==y2(i,1)))||((x2(j,1)==x1(i,1))&&(y2(j,1)==y1(i,1)))||((x2(j,1)==x2(i,1))&&(y2(j,1)==y2(i,1)))
        else
            k1=(y2(i,1)-y1(i,1))/(x2(i,1)-x1(i,1));
            k2=(y2(j,1)-y1(j,1))/(x2(j,1)-x1(j,1));
            % exclude equal slope
            if k1~=k2
                % slove cross node's coordinate
                A=[k1,-1;k2,-1];
                b=[k1*x1(i,1)-y1(i,1);k2*x1(j,1)-y1(j,1)];
                Jie=inv(A)*b;
                % confirm cross node in the middle of four nodes again????
                if ((Jie(1,1)<max(x1(i,1),x2(i,1))&&Jie(1,1)>min(x1(i,1),x2(i,1)))&&(Jie(1,1)<max(x1(j,1),x2(j,1))&&Jie(1,1)>min(x1(j,1),x2(j,1))))&&((Jie(2,1)<max(y1(i,1),y2(i,1))&&Jie(2,1)>min(y1(i,1),y2(i,1)))&&(Jie(2,1)<max(y1(j,1),y2(j,1))&&Jie(2,1)>min(y1(j,1),y2(j,1))))
                    count=count+1;
                    lon_lat_new(count,1)=Jie(1,1);% new cross coordinate
                    lon_lat_new(count,2)=Jie(2,1);
                    % record cross node's cross edge to checkout
                    crosss(count,1)=num(j,1);% four cross nodes
                    crosss(count,2)=num(j,2);
                    crosss(count,3)=num(i,1);
                    crosss(count,4)=num(i,2);
                    crosss(count,5)=j;
                    crosss(count,6)=i;
                end
            end
        end
    end
end
end