一、问题产出的背景我现在有一个多边形区域,因为某些原因,该区域的形状在某年可能发生了改变,我现在需要在前端写一个动画,让他慢慢变化。效果大致如下:(发gif给我删了3次,只能图片了,线为点的轨迹)
开始的多边形
结束的多边形
过渡动画
二、问题核心最难的部分就是第一个多边形怎么过渡到第二个多边形,我的动画规则是这样的,分2种情况
1、如果多边形的点数一样,那么找出第一个多边形数组的每一个点到第二个多边形数组的相同位置点的距离和最小,一个n边形是可以由2n种数组组成,
如下什么样的数组是同一个多边形我们定义一个多边形是一个二维数组,有一维数组点[x,y]组成,如[[x1,y1],[x2,y2]...[xn,yn]]点的坐标相同,并且点的顺序是从多边形任意一点顺时针或逆时针出发遍历一遍即可,
用代码来说。我们将[[x1,y1],[x2,y2]...[xn,yn]]数组点复制一遍[[x1,y1],[x2,y2]...[xn,yn],[x1,y1],[x2,y2]...[xn,yn]],然后顺序取n个,逆序取n个,总共2n个数组,这些数组就是同一个多边形
2、如果多边形的点数不一致,假设M>N,第一个为N边形,第二个为M边形,我们需要扩展N边形为M边形,比如[[x1,y1],[x2,y2]...[xn,yn]]可以扩展为[[x1,y1],[x1,y1],[x1,y1],[x2,y2],[x2,y2]...[xn,yn]],这样的数组表示的还是同一个多边形,后续处理同情况一,这一种情况看上去也不复杂,但是我们没有一个合适的方法通过暴力的枚举会发现不现实,因为扩展的情况的组合数量为C(M,N)意思是M!/N!/(M-N)!,这个数字增长的速度是比指数增长还爆炸的阶乘增长,C(30,15)就已经等于155,117,520,然后还需要乘30对点的距离再乘2*30种数组情况,我试了一下暴力解法,浏览器直接卡崩了,
这个问题可以抽象成这样一个问题,现在有2个一维数组长度为m的数组M[m1,m2,m3...mm],长度为n的数组N[n1,n2,n3...nn],m>n,求一个扩展数组Nm他长度等于M并且与数组M或者M的相似数组每个对应数组的差之和最小,相似数组的规则同上的相同多边形,有大佬能解决这个问题吗,我已经被这个问题困扰了一周了,现在只是实现了一种优化暴力枚举但C(30,15)没法降下去的方法和一种效率很快但我不能在数学上证明所有点移动距离之和最小
开始的多边形
结束的多边形
过渡动画
二、问题核心最难的部分就是第一个多边形怎么过渡到第二个多边形,我的动画规则是这样的,分2种情况
1、如果多边形的点数一样,那么找出第一个多边形数组的每一个点到第二个多边形数组的相同位置点的距离和最小,一个n边形是可以由2n种数组组成,
如下什么样的数组是同一个多边形我们定义一个多边形是一个二维数组,有一维数组点[x,y]组成,如[[x1,y1],[x2,y2]...[xn,yn]]点的坐标相同,并且点的顺序是从多边形任意一点顺时针或逆时针出发遍历一遍即可,
用代码来说。我们将[[x1,y1],[x2,y2]...[xn,yn]]数组点复制一遍[[x1,y1],[x2,y2]...[xn,yn],[x1,y1],[x2,y2]...[xn,yn]],然后顺序取n个,逆序取n个,总共2n个数组,这些数组就是同一个多边形
2、如果多边形的点数不一致,假设M>N,第一个为N边形,第二个为M边形,我们需要扩展N边形为M边形,比如[[x1,y1],[x2,y2]...[xn,yn]]可以扩展为[[x1,y1],[x1,y1],[x1,y1],[x2,y2],[x2,y2]...[xn,yn]],这样的数组表示的还是同一个多边形,后续处理同情况一,这一种情况看上去也不复杂,但是我们没有一个合适的方法通过暴力的枚举会发现不现实,因为扩展的情况的组合数量为C(M,N)意思是M!/N!/(M-N)!,这个数字增长的速度是比指数增长还爆炸的阶乘增长,C(30,15)就已经等于155,117,520,然后还需要乘30对点的距离再乘2*30种数组情况,我试了一下暴力解法,浏览器直接卡崩了,
这个问题可以抽象成这样一个问题,现在有2个一维数组长度为m的数组M[m1,m2,m3...mm],长度为n的数组N[n1,n2,n3...nn],m>n,求一个扩展数组Nm他长度等于M并且与数组M或者M的相似数组每个对应数组的差之和最小,相似数组的规则同上的相同多边形,有大佬能解决这个问题吗,我已经被这个问题困扰了一周了,现在只是实现了一种优化暴力枚举但C(30,15)没法降下去的方法和一种效率很快但我不能在数学上证明所有点移动距离之和最小