连通不规则多边形算法
程序员文章站
2022-03-13 14:50:53
...
多边形连通和最小生成树本质上是一样的，问题在于确定权值。
下面算法由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>
上一篇： MD5加密技术的Java代码实现
下一篇： mfc 多边形裁剪算法
推荐阅读
-
图片感兴趣区域ROI获取——鼠标选择矩阵区域+不规则多边形区域（anoconda3.4+spyder+python3.5+opencv3.4）
-
图论算法----Tarjan求无向图双连通分量及拓展
-
tarjan算法求解强连通分量
-
tarjan算法求强连通分量详解(避免误区)
-
C4D怎么使用多边形画笔工具建模不规则模型?
-
算法竞赛——进阶指南——acwing 367. 学校网络 SCC - tarjan求强连通+思维
-
二值图像连通域标记算法优化
-
多边形扫描转换算法的改进
-
程序设计思维 C - 班长竞选 （强连通分量、kosaraju算法）
-
Kasaraju算法--强连通图遍历及其python实现