Tag Archives: 算法

多点在矩形中均匀随机排列算法的实现

不规则图形在一个固定矩形中的排列很容易让人联想到背包问题。OMG这太复杂了,所以我们不研究这个。我的问题很简单,将多个不规则图片随机的放在一个给定矩形中并且使他们排列相对均匀不要太难看即可。Google一番后,找到这么一个算法基本可以满足我的需求:https://home.comcast.net/~davejanelle/packing.html

算法描述:

  1. 将N个点随机的放到矩形中
  2. 定义一个步长STEP。可先设置为矩形某边长的1/5。(我实际使用的是Max(边长))
  3. 对每一个点P:
    1. 向上下左右四个方向分别移动STEP的距离。
    2. 判断新的位置是否加大了点P与其最近邻点的距离?如果是则保留新位置。
  4. 重复步骤3直到N个点中没有可以再移动的点。
  5. 缩短STEP(比如除以1.5),再次重复步骤3直到STEP小于某个最小值。

算法实现(objective-c + cocos2d):

写的比较烂,将就看吧…