求平面内满足条件的点（坐标点）？

Question

问题描述

参数是【个数，距离】求出在浏览器这个二位平面内满足的点位坐标。

个数：在浏览器这个二位平面内 坐标点的数量。

距离：每一个坐标点位之间的间距必须小于这个距离。

相关代码

/**
     * 个数：生成几个。
     * 距离：间距多少(px)
     */
    function starList() {
        var list = [], //生成之后的list
            arg = [].slice.call(arguments), //参数
            number = arg[0] || 10, //个数
            distance = arg[1] || 100, //距离
            domBody = document && document.body || {
                clientWidth: 1920,
                clientHeight: 1080
            },
            maxW = domBody.clientWidth,
            maxH = domBody.clientHeight;
            if(typeof number!=="number"){
                 throw("第一个参数出错，应该是number类型");
                
            }
            if(typeof distance!=="number"){
                throw("第二个参数出错，应该是number类型");
            
           }
           if(number*distance>Math.min(maxW,maxH)){
                throw("参数一与参数二的积必须小于视图的宽与度的最小值");
            }
        return {
            init: function (callback) {
                callback = callback || function () {};
                if(typeof callback!=="function"){
                    throw("参数出错，应该是function类型");
                    
                }
                this.pushList(); //存入数据
                callback(list);
            },
            /**
             * 存入数组
             */
            pushList: function () {
                //判断生成的点位数个数是否足够
                if (list.length === number) {
                    return;
                }
                var point = this._random(maxW, maxH, 0);
                if (this.judgeDistances(point)) {
                    list.push(point);
                    this.pushList();
                } else {
                    //如果不满足条件再次执行
                    this.pushList();
                }
            },
            /**
             * 随机方法
             */
            _random: function (maxw, maxh, min) {
                return {
                    x: parseInt(Math.random() * (maxw - min + 1) + min, 10),
                    y: parseInt(Math.random() * (maxh - min + 1) + min, 10)
                };
            },
            /**
             * 判断距离
             */
            judgeDistances: function (point) {
                var l = list.length;
                while (l--) {
                    //如果新生成的坐标距离不满足distance 则返回false 
                    if (Math.abs(list[l].x - point.x) < distance || Math.abs(list[l].y - point.y) < distance) {
                        return false;
                    }
                }
                return true;
            }
        }
    };
    var creatStar = starList(20,26);//如果26改为50或者45，则会爆栈。
     creatStar.init(function(list){
       console.log(list);

     });

//结果出现爆栈了，请问大佬有没有好的解决方案。

怎么解决这种问题呢？

Answer 1

1. 浏览器的堆栈调用是有上限的，看这个：https://zhuanlan.zhihu.com/p/...，Chrome大概是10000
2. 程序为什么调用栈大于10000呢？

假设：题主的显示屏和我一样是 1980 * 1080,
即 clientWidth = 1980; clientHeight = 1080; distance = 50;(题主传进去的)
要求：生成20个点（题主传进去的），使满足每个点之间的距离（无论x或y）都大于50；

要知道 50 * 20 = 1000 约等于1080；

那么这个问题可以化简为：

在一条155cm的带上随机点三个点，使满足每三个点间距离必须大于或等于50cm；

50 * 3 = 150 约等于 155

假设已存在两个点，其距离大于55cm且小于100cm，且两点距离左右边界都少于50cm（比如距离左侧40cm有一个点，距离右侧40cm有一个点，中间仅剩下75cm），则不存在第三点满足两两距离大于50;

所以说：三个点，仅考虑一条轴，就有很大概率，获取不到三个点，
那么，20个点要同时满足x轴和y轴，则存在非常大的概率，得不到最后的几个点而陷入无限循环中，于是，BOOM！