一、问题产出的背景
我现在有一个多边形区域,因为某些原因,该区域的形状在某年可能发生了改变,我现在需要在前端写一个动画,让他慢慢变化。效果大致如下(不要在意线,那是点的运动轨迹,我为了方便观察和美观调成了贝塞尔曲线,默认是直线):
几何变形动画1
二、问题核心
最难的部分就是第一个多边形怎么过渡到第二个多边形,我的动画规则是这样的,分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种数组情况,我试了一下暴力解法,浏览器直接卡崩了,这还只是30,已经无法想象40边形甚至50边形的情况个数了,
这个问题可以抽象成这样一个问题,现在有2个一维数组长度为m的数组M[m1,m2,m3...mm],长度为n的数组N[n1,n2,n3...nn],m>n,求一个扩展数组Nm他长度等于M并且与数组M或者M的相似数组每个对应数组的差之和最小,相似数组的规则同上的相同多边形,有大佬能解决这个问题吗,我已经被这个问题困扰了一周了,现在实现了一种优化后暴力枚举但C(30,15)没法降下去的方法和一种很快但不能再数学上证明点移动距离最小,该方法几百边形转换没看出卡顿,我下期更新该方法。
对应多边形数组早到了动画就好做了,再对应点之间进行插值就可以了
我现在有一个多边形区域,因为某些原因,该区域的形状在某年可能发生了改变,我现在需要在前端写一个动画,让他慢慢变化。效果大致如下(不要在意线,那是点的运动轨迹,我为了方便观察和美观调成了贝塞尔曲线,默认是直线):
几何变形动画1
二、问题核心
最难的部分就是第一个多边形怎么过渡到第二个多边形,我的动画规则是这样的,分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种数组情况,我试了一下暴力解法,浏览器直接卡崩了,这还只是30,已经无法想象40边形甚至50边形的情况个数了,
这个问题可以抽象成这样一个问题,现在有2个一维数组长度为m的数组M[m1,m2,m3...mm],长度为n的数组N[n1,n2,n3...nn],m>n,求一个扩展数组Nm他长度等于M并且与数组M或者M的相似数组每个对应数组的差之和最小,相似数组的规则同上的相同多边形,有大佬能解决这个问题吗,我已经被这个问题困扰了一周了,现在实现了一种优化后暴力枚举但C(30,15)没法降下去的方法和一种很快但不能再数学上证明点移动距离最小,该方法几百边形转换没看出卡顿,我下期更新该方法。
对应多边形数组早到了动画就好做了,再对应点之间进行插值就可以了