热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

在坐标系中查找大多数未填充的点

如何解决《在坐标系中查找大多数未填充的点》经验,为你挑选了1个好方法。

我有一个基本代表一个屏幕的坐标系.
我有任意数量的职位.例如:

population = [
    {x: 100.44, 200.54},
    {x: 123.45, 678.9},
    {x: 1300.23, 435.81},
    {x: 462.23, 468.37},
    {x: 956.58, 385.38},
];

我正在寻找一种找到最无人居住点的算法.

白色迷你圆圈代表人口和红色Xs标记点,对我来说似乎非常无人居住:

截图

我的目标是运行一个动画,随机将所有这些白色迷你圆圈移动到随机方向,一旦圆圈离开屏幕,它就会被传送到最无人居住的地点,这样大空空间的数量就会减少.

我试图通过计算从每个整数坐标到每个圆的距离之和,然后选择具有最高距离和的坐标来实现这一点.仅此一点似乎已经非常耗费CPU,但我注意到这个算法会使圆圈传送到我的坐标系的边界.所以我还添加了从每个整数坐标到每个边界整数坐标的距离之和.那时,脚本基本上冻结了.所以这绝对不是正确的方法.

我的想法已经不多了.我想我不需要一个完美的算法,而是一个在精度和性能之间保持平衡的算法.最后,我希望能够在1920x1080画布上每秒多次运行该算法,其中大约有80个这样的小环.理想情况下,算法会有一个参数来调整精度,从而调整它使用的CPU时间.

这是我上面提到的方法.我注释掉导致脚本冻结的行:

let circles = [
    {x: 60.44, y: 190.54},
    {x: 103.45, y: 18.9},
    {x: 390.23, y: 135.81},
    {x: 302.23, y: 28.37},
    {x: 56.58, y: 85.38},
]

function getDistance(p1, p2) {
    return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2)
}
function drawCircle(ctx,x,y,r,c) {
    ctx.beginPath()
    ctx.arc(x, y, r, 0, 2 * Math.PI, false)
    ctx.fillStyle = c
    ctx.fill()
}


const canvas = document.getElementById('canvas')
const ctx = canvas.getContext("2d")

let highestDistanceSum = 0
let coordWithHighestDistanceSum
for (let x=0; x highestDistanceSum) {
            coordWithHighestDistanceSum = canvasCoord
            highestDistanceSum = distanceSum
        }
    }
}


for (let p of circles) {
    drawCircle(ctx, p.x, p.y, 3, 'black')
}

drawCircle(ctx, coordWithHighestDistanceSum.x, coordWithHighestDistanceSum.y, 5, 'red')



1> AVAVT..:

(因为它是黑色画布上的白点,我会称之为白点星,以便于区分)

首先,您的解决方案似乎不符合您的标准.你不需要与所有恒星的距离最大的点.你需要距离它最近的恒星最远的点.

详细说来,比如说这样的情况,中心有一颗恒星,距离中心有一定距离的大量恒星:

在此输入图像描述

"最大距离和"方法可能会在红色圆圈的某个位置给出一个点(它太靠近甚至与中心星重叠),而你想要的更像是绿色圆圈中的某些东西:

在此输入图像描述

考虑到这一点:

    首先,我们应该将屏幕划分为合理大小的正方形,我们将从这些正方形构建距离图,以找到与任何恒星距离最远的那个.

"合理大小"的部分在性能方面非常重要.您使用的是1920x1080分辨率,这在我看来太精细了.为了获得足够令人愉悦的结果,48x30甚至32x20的分辨率就足够了.

    要实际构建距离图,我们可以简单地使用广度优先搜索.我们将所有星星的位置转换为网格坐标,并将其用作BFS的起始位置.

结果将是这样的:

在此输入图像描述

这里还有一个很大的问题:最红的广场位于最底层!

边缘和角落方形比中心坐标具有"欺骗"优势,因为一侧没有星形(甚至是三角形,角形方块).因此角落和边缘正方形很可能与任何恒星的距离最大.

你的艺术作品在视觉上是不是很令人愉悦?所以我们可以通过过滤掉某个填充内的结果来作弊.幸运的是,BFS的结果默认排序,因此我们可以迭代结果,直到找到适合所需区域的结果.

以下是带注释的完整代码.即使可以看到距离图,整个过程也需要20ms,对于webgl片来说应该足够了(运行@ max 30fps~33ms /帧)

这个解决方案还将处理几个星星在同一帧移出界限的罕见情况.在这种情况下,只需从BFS的结果中获取几个不同的坐标.





  
  
  
  



  
  



推荐阅读
  • 本文讨论了在openwrt-17.01版本中,mt7628设备上初始化启动时eth0的mac地址总是随机生成的问题。每次随机生成的eth0的mac地址都会写到/sys/class/net/eth0/address目录下,而openwrt-17.01原版的SDK会根据随机生成的eth0的mac地址再生成eth0.1、eth0.2等,生成后的mac地址会保存在/etc/config/network下。 ... [详细]
  • 本文由编程笔记#小编为大家整理,主要介绍了logistic回归(线性和非线性)相关的知识,包括线性logistic回归的代码和数据集的分布情况。希望对你有一定的参考价值。 ... [详细]
  • 本文介绍了一个在线急等问题解决方法,即如何统计数据库中某个字段下的所有数据,并将结果显示在文本框里。作者提到了自己是一个菜鸟,希望能够得到帮助。作者使用的是ACCESS数据库,并且给出了一个例子,希望得到的结果是560。作者还提到自己已经尝试了使用"select sum(字段2) from 表名"的语句,得到的结果是650,但不知道如何得到560。希望能够得到解决方案。 ... [详细]
  • 本文介绍了一个适用于PHP应用快速接入TRX和TRC20数字资产的开发包,该开发包支持使用自有Tron区块链节点的应用场景,也支持基于Tron官方公共API服务的轻量级部署场景。提供的功能包括生成地址、验证地址、查询余额、交易转账、查询最新区块和查询交易信息等。详细信息可参考tron-php的Github地址:https://github.com/Fenguoz/tron-php。 ... [详细]
  • 嵌入式处理器的架构与内核发展历程
    本文主要介绍了嵌入式处理器的架构与内核发展历程,包括不同架构的指令集的变化,以及内核的流水线和结构。通过对ARM架构的分析,可以更好地理解嵌入式处理器的架构与内核的关系。 ... [详细]
  • 本文讨论了如何优化解决hdu 1003 java题目的动态规划方法,通过分析加法规则和最大和的性质,提出了一种优化的思路。具体方法是,当从1加到n为负时,即sum(1,n)sum(n,s),可以继续加法计算。同时,还考虑了两种特殊情况:都是负数的情况和有0的情况。最后,通过使用Scanner类来获取输入数据。 ... [详细]
  • 本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程,将每个考题分配给3个独立的专家,如果他们的评分不一致,则需要请一位裁判做出最终决定。文章详细描述了评分规则,并给出了解决该问题的程序。 ... [详细]
  • 本文介绍了Oracle数据库中tnsnames.ora文件的作用和配置方法。tnsnames.ora文件在数据库启动过程中会被读取,用于解析LOCAL_LISTENER,并且与侦听无关。文章还提供了配置LOCAL_LISTENER和1522端口的示例,并展示了listener.ora文件的内容。 ... [详细]
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • 本文介绍了为什么要使用多进程处理TCP服务端,多进程的好处包括可靠性高和处理大量数据时速度快。然而,多进程不能共享进程空间,因此有一些变量不能共享。文章还提供了使用多进程实现TCP服务端的代码,并对代码进行了详细注释。 ... [详细]
  • 拥抱Android Design Support Library新变化(导航视图、悬浮ActionBar)
    转载请注明明桑AndroidAndroid5.0Loollipop作为Android最重要的版本之一,为我们带来了全新的界面风格和设计语言。看起来很受欢迎࿰ ... [详细]
  • 3.223.28周学习总结中的贪心作业收获及困惑
    本文是对3.223.28周学习总结中的贪心作业进行总结,作者在解题过程中参考了他人的代码,但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获,同时提到了一道让他困惑的题目,即input details部分引发的疑惑。 ... [详细]
  • 本文讨论了Kotlin中扩展函数的一些惯用用法以及其合理性。作者认为在某些情况下,定义扩展函数没有意义,但官方的编码约定支持这种方式。文章还介绍了在类之外定义扩展函数的具体用法,并讨论了避免使用扩展函数的边缘情况。作者提出了对于扩展函数的合理性的质疑,并给出了自己的反驳。最后,文章强调了在编写Kotlin代码时可以自由地使用扩展函数的重要性。 ... [详细]
  • 本文详细介绍了如何使用MySQL来显示SQL语句的执行时间,并通过MySQL Query Profiler获取CPU和内存使用量以及系统锁和表锁的时间。同时介绍了效能分析的三种方法:瓶颈分析、工作负载分析和基于比率的分析。 ... [详细]
  • 为什么下一个5年,软件定义市场将暴涨32%
    Technavio公司的市场调研分析预测,到2020年全球软件定义一切(SDx)市场年复合增长率将超过32%,向虚拟化的转化是市场增长的主要驱动力。近来 ... [详细]
author-avatar
生命的无言
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有