连通不规则多边形算法

我会带着你远行 2022-03-30 14:50 209阅读 0赞

多边形连通和最小生成树本质上是一样的，问题在于确定权值。

下面算法由js实现，演示由svg提供。

<html>
    <head>
        <script>
            let shown='hidden';
            //核心算法
            let caculatePath=function(){
                /*显示和隐藏，算法无关*/
                for(let i=0;i<panel.children.length;i++){
                    panel.children[i].style.visibility=shown;
                }
                lineGroup.innerHTML=null;
                if(shown=='hidden'){
                    shown='visible';
                }else{
                    shown='hidden';
                    return;
                }
                getEvent().target.style.visibility='visible';
                let gons=getPolygons(getEvent().target);
                let target=document.getElementById('target');
                /*----------END----------*/
                
                //closeList表示已经连通的图形，无需再连通
                let closeList=[];
                //未连通的图形
                let openList=[];
                
                //放入外框图形
                closeList.push(gons[0]);
                //放入其他图形
                for(let i=1;i<gons.length;i++){
                    openList.push(gons[i]);
                }
                let cache={};
                while(openList.length>0){
                    let min={dist:Number.MAX_SAFE_INTEGER};
                    let imin,jmin;
                    for(let i=0;i<openList.length;i++){
                        for(let j=0;j<closeList.length;j++){
                            //缓存之前的计算值,提高计算效率，这里应该利用最小堆，但是js没有默认实现，先不管
                            let cacheKey=openList[i].index+':'+closeList[j].index;
                            let d=cache[cacheKey];
                            if(!d){
                                d=polygon2Polygon(openList[i],closeList[j]);
                            }
                            cache[cacheKey]=d;
                            if(d.dist<min.dist){
                                min=d;
                                imin=i;
                                jmin=j;
                            }
                        }
                        
                    }
                    
                    //构建父子级
                    if(closeList[jmin].child==null){
                        closeList[jmin].child=[];
                    }
                    closeList[jmin].child.push(
                    {
                        node:openList[imin],
                        target:min.target,
                        source:min.source,
                    });
                    
                    closeList.push(openList[imin]);
                    openList.splice(imin,1);
                    
                }
                //测试
                collect(gons[0],getEvent().target);
    
                return gons[0]
            };
    
            /**
             * 返回{ dist:最小距离,source:parent链接点，target：child链接点}
             * @param poly1
             * @param poly2
             */
            let polygon2Polygon=function(poly1,poly2){
                let point,min={dist:Number.MAX_SAFE_INTEGER};
                for(let i=0;i<poly1.length;i++){
                    point=poly1[i];
                    let d=point2Polygon(point,poly2);
                    if(d.dist<min.dist){
                        min=d;
                        min.target=point;
                        min.source=d.anchor;
                    }
                }
    
                for(let i=0;i<poly2.length;i++){
                    point=poly2[i];
                    let d=point2Polygon(point,poly1);
                    if(d.dist<min.dist){
                        min=d;
                        min.target=d.anchor;
                        min.source=point;
                    }
                }
    
                return min;
            };
    
            //计算图形和点之间的最小距离，返回线，距离
            let point2Polygon=function(point,poly){
                let min=Number.MAX_SAFE_INTEGER;
                let anchor,d;
                for(let i=0;i<poly.length;i++){
                    let p1=poly[i],p2;
                    let i1;
                    if(i==poly.length-1)
                        i1=0;
                    else
                        i1=i+1;
                    p2=poly[i1];
                    
                    d= distToSegment(point,p1,p2);
                    if(min>d.dist){
                        min=d.dist;
                        anchor=d.p;
                    }
                    
                }
                return {
                    dist:min,
                    anchor:anchor,
                }
            };
    
            /*-------------点到线段距离------------*/
            function sqr(x) { return x * x }
            function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
    
            //返回距离和连接点
            function distToSegment(p, v, w) {
                let l2 = dist2(v, w);
                if (l2 == 0) return dist2(p, v);
                let t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
    
                t = Math.max(0, Math.min(1, t));
                let w1={ x: v.x + t * (w.x - v.x),
                    y: v.y + t * (w.y - v.y) };
                return {dist:Math.sqrt(dist2(p, w1)),
                    p:w1};
            }
            /*-------------END---------------*/
    
    
    
            /*-------无关算法分界线--------*/
    
            //创建连线
            let createLineElement=function(){
                let line= document.createElementNS('http://www.w3.org/2000/svg','line');
                line.style.stroke='black';
                line.style['stroke-width']=2;
                line.setAttributeNS('','marker-end','url(#arrow)');
                return line;
            };
    
    
            let collect=function(p){
                if(p.child){
                    for(let i=0;i<p.child.length;i++){
    
                        let np=createLineElement();
                        let s=p.child[i].source;
                        let t=p.child[i].target;
    
    
                        let x1,y1,x2,y2;
                        if(s instanceof Array){
                            x1=(s[0].x+s[1].x)/2;
                            y1=(s[0].y+s[1].y)/2;
                        }else{
                            x1=s.x;
                            y1=s.y;
                        }
    
                        if(t instanceof Array){
                            x2=(t[0].x+t[1].x)/2;
                            y2=(t[0].y+t[1].y)/2;
                        }else{
                            x2=t.x;
                            y2=t.y;
                        }
    
    
                        np.setAttribute('x1',x1);
                        np.setAttribute('y1',y1);
    
                        np.setAttribute('x2',x2);
                        np.setAttribute('y2',y2);
                        lineGroup.appendChild(np);
    
                        collect(p.child[i].node);
                    }
                }
            };
    
            let getEvent = function(){
                return window.event || arguments.callee.caller.arguments[0];
            };
    
            let printChild=function(p){
                console.log('node:',p.index);
                if(p.child){
                    console.log('{',p.index,'--child:');
                    for(let i=0;i<p.child.length;i++){
                        console.log('source:',p.child[i].source);
                        console.log('target:',p.child[i].target);
                        printChild(p.child[i].node);
                    }
                    console.log('--',p.index,'}');
                }
            }
            //从path里获取所有的多边形
            let getPolygons=function(p){
                let d=p.getAttribute('d');
                if(d){
                    let polygons=d.split('M');
                    let result=[];
                    for(let i=1;i<polygons.length;i++){
                        let seg = polygons[i];
    
                        let plist=[];
                        result.push(plist);
                        plist.index=i-1;
                        let status=0;
                        let np,pindex=0;
                        for(let j=0;j<seg.length;j++){
                            let c = seg.charAt(j);
                            if(status==0){
                                //初始化状态
                                if(c==' '||c=='L'||c=='Z'){
    
                                }else{
                                    np={};
                                    np.index=pindex++;
                                    plist.push(np);
                                    np.x=c;
                                    np.y='';
                                    status=1;
                                }
                            }else if(status == 1){
                                //开始写x
                                if(c==' '||c==','){
                                    //开始写y
                                    np.x=parseFloat(np.x);
                                    status=2;
                                }else if(c=='L'){
    
                                }else{
                                    np.x+=c;
                                }
                            }else if(status == 2){
                                if(c==' '||c=='Z'||c=='L'){
                                    np.y=parseFloat(np.y);
                                    status = 0;
                                }else{
                                    np.y+=c;
                                }
                            }
                        }
                    }
                    return result;
                }
            }
            window.οnlοad=function(){
                let panel=document.getElementById('panel');
                
                for(let i=0,len=panel.children.length;i<len;i++){
                    panel.children[i].οnclick=caculatePath;
                }
            }
        </script>
    </head>
    <body>
        <svg  width='100%' height='100%' style="border:1px solid">
            <defs>
                <marker id="arrow" markerWidth="5" markerHeight="5" refx="0" refy="3" orient="auto" markerUnits="strokeWidth">
                    </marker>
            </defs>
    
            <g id="panel">
            <path  d="M20 90 L30 0 180 20 140 170Z M100 40 L60 20 40 60 Z M140 110 L140 60 100 60 80 100Z" fill="red" stroke="black" stroke-width="1"/>
            <path  d="M 240 110 200 110 210 130 230 130 Z M 20 10 140 160 270 10 270 190 20 190 Z M 40 130 80 130 70 110 50 110 Z" fill="blue" stroke="black" stroke-width="1"/>
            <path  d="M 190 60 160 40 40 40 40 160 160 160 190 140 190 110 150 110 150 150 50 150 50 50 150 50 150 90 190 90 Z M 130 70 70 70 90 100 70 130 130 130 110 100 Z M 20 10 210 10 240 190 30 190 Z" fill="green" stroke="black" stroke-width="1"/>
            <path  fill="yellow" d="M 515.176 32.5645 L 324.258 181.059 L 246.477 231.564 L 197.99 157.824 L 421.232 67.9199 L 362.645 39.6367 L 50.5078 55.7988 L 27.2734 217.422 L 118.188 327.529 L 518.207 326.52 L 604.07 184.088 L 515.176 32.5645 z M 312.137 61.8594 L 244.457 128.529 L 187.889 116.408 L 218.193 65.9004 L 312.137 61.8594 z M 177.787 76.002 L 170.717 209.342 L 254.557 269.951 L 427.295 148.732 L 446.486 226.514 L 253.547 305.307 L 131.32 241.666 L 75.7617 89.1328 L 177.787 76.002 z M 492.953 85.0938 L 522.248 90.1445 L 551.543 191.158 L 439.416 302.275 L 366.684 280.051 L 484.871 222.473 L 480.832 172.977 L 492.953 85.0938 z M 84.8535 185.098 L 123.238 263.889 L 169.705 281.062 L 156.574 305.307 L 95.9648 282.072 L 57.5781 226.514 L 54.5488 193.18 L 84.8535 185.098 z"></path>
    
            <path fill="pink" stroke="blue" d="M 0 300 L0 400 L150 400 L150 380 L250 380 L250 400 L400 400 L400 300Z M100 350 L300 350 L200 340Z M50 360 L350 360 L350 370 L50 370Z" ></path>
    
            <path fill="darkblue" d="M 76.0547,21.5254 L 75.4512,37.3594 L 58.9297,466.727 L 634.598,477.336 L 660.068,34.0449 Z M 131.348,54.9551 L 192.967,56.2754 L 186.355,98.2832 Z M 222.354,56.9062 L 266.256,57.8477 L 269.129,74.3066 L 225.398,109.703 L 214.082,109.459 Z M 389.65,60.4922 L 434.258,61.4492 L 440.795,117.586 L 350.936,135.99 L 362.236,97.3965 L 371.996,84.7891 L 381.024,72.2914 Z M 463.652,62.0781 L 548.537,63.8984 L 530.947,125.684 L 469.365,111.127 Z M 578.639,64.5449 L 625.961,65.5586 L 618.539,194.756 L 590.986,200.816 L 556.83,141.156 Z M 106.363,72.3535 L 169.805,122.324 L 102.598,170.236 Z M 289.045,95.6621 L 330.428,102.387 L 319.621,139.268 L 260.107,119.078 Z M 194,102 L214 132 L 190,122 Z M 225.17,138.832 L 227.857,138.891 L 315.775,168.713 L 325.164,218.836 L 318.633,224.689 L 262.492,206.191 L 234.553,159.479 Z M 467.902,140.713 L 531.643,155.779 L 556.002,198.344 L 467.482,158.762 Z M 194.078,140.803 L 206.014,167.082 L 185.609,228.994 L 159.529,242.369 L 114.529,197.502 Z M 438.604,147.764 L 438.248,163 L 402.289,209.734 L 386.125,213.602 L 353.268,210.686 L 345.074,166.912 Z M 457.236,186.09 L 537.91,222.158 L 493.592,228.064 L 455.502,230.307 L 432.676,218.002 Z M 225.48,201.053 L 238.491,213.006 L 220.955,214.807 Z M 100.504,224.646 L 142.338,266.361 L 112.168,311.863 L 103.346,314.174 L 98.252,283.168 Z M 616.805,224.961 L 612.346,302.57 L 581.812,274.451 L 579.367,249.936 L 577.547,235.974 L 574.516,230.923 L 589.637,230.941 Z M 253.117,233.77 L 303.359,250.32 L 295.482,272.451 L 286.461,288.41 L 227.938,301.764 L 180.045,264.582 L 203.475,252.564 Z M 408.684,238.146 L 439.324,254.684 L 447.172,292.891 L 425.367,291.783 L 406.387,238.701 Z M 345.99,239.283 L 376.639,242 L 398.215,302.361 L 327.033,270.68 L 334.547,249.529 Z M 536.516,251.73 L 501.43,277.691 L 506.85,255.68 Z M 483.356,253.262 L 477.721,274.616 L 459.165,257.925 Z M 552.703,275.986 L 553.08,279.773 L 543.338,309.279 L 520.807,299.586 Z M 162.859,288.115 L 207.246,322.566 L 193.545,361.557 L 181.705,383.217 L 167.805,382.314 L 138.123,325.424 Z M 314.955,297.188 L 387.291,329.379 L 382.189,358.236 L 378.357,363.965 L 373.125,364.098 L 339.242,351.496 L 312.578,301.389 Z M 574.629,307.426 L 610.186,340.182 L 604.191,444.537 L 587.582,444.23 L 551.996,400.861 L 566.256,332.762 Z M 288.344,317.85 L 311.229,360.85 L 301.432,371.266 L 226.195,356.479 L 235.533,329.904 Z M 492.541,319.135 L 535.49,337.611 L 527.479,375.805 L 489.086,326.139 L 488.297,321.459 Z M 421.859,320.766 L 458.963,322.641 L 459.02,322.98 L 414.891,340.57 L 417.344,326.707 Z M 113.695,341.566 L 138.027,388.199 L 93.6055,403.955 L 95.8223,346.34 L 96.3555,346.107 Z M 470.521,349.746 L 497.805,385.031 L 414.773,382.92 L 405.818,375.547 Z M 332.975,380.24 L 352.375,387.463 L 336.939,433.309 L 329.328,427.639 L 321.666,392.266 Z M 214.547,383.863 L 272.266,395.211 L 228.389,428.172 L 207.121,397.447 Z M 381.23,393.033 L 395.184,404.512 L 397,440.719 L 365.373,440.135 Z M 160.74,411.039 L 182.059,412.426 L 199.117,437.07 L 92.8984,435.113 Z M 424.732,412.316 L 524.307,414.842 L 526.926,416.221 L 549.33,443.525 L 426.184,441.256 Z M 296.465,413.465 L 299.07,425.506 L 270.42,433.027 Z"></path>
    
            </g>
            <g id="lineGroup"></g>
        </svg>
    	
    	<div style="position:fixed;right:10%;height:100px;width:200px;top:50px;background-color:#ccc;text-align:center;line-height:1.95">
    	<div style="">点击左侧图形</div> <div>查看最小连通图</div></div>
    </body>
    </html>