连通不规则多边形算法

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

下面算法由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.onload=function(){
            let panel=document.getElementById('panel');
            
            for(let i=0,len=panel.children.length;i<len;i++){
                panel.children[i].onclick=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>

  

上一篇:前端开发之走进Vue.js


下一篇:className用法