求平面内满足条件的点(坐标点)?

问题描述

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

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

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

相关代码

/**
     * 个数:生成几个。
     * 距离:间距多少(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);

     });

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

怎么解决这种问题呢?

阅读 1.8k
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!

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题