jjzjj

javascript - JS - 基于密度的稀疏点数

coder 2024-07-25 原文

假设我有一个数组如下(每个小数组是[x, y]):

var myPoints = [[25, 28], [26, 26], [70, 40], [50, 50], [300, 300], [285, 350], [1000, 1000]];

假设我需要将数组精简到 4 个点。 (这是一个小例子，我的实际数组有数千个点)我如何根据密度来细化数组，以便从点更近的区域中删除更多的点，而从密度较低的区域中删除更少的点？

在这种情况下(将上面的数组从 8 项减少到 4 项)我希望返回的数组看起来像下面这样:

var thinnedPoints = [[25, 28], [70, 40], [300, 300], [1000, 1000]];

我关于如何处理这个问题的想法是生成一个字典，将点映射到它到另一个点的最小距离(例如，靠近另一个点的点将有一个小的最小距离)然后根据升序最小值对字典进行排序distance，然后删除字典中的每 n'tn 项。

这种方法的问题是我不知道如何有效地为每个点生成到最近的其他点的距离值。

是否有一种有效的方法来生成这些值，或者是否有另一种方法来解决这种基于密度的细化问题？

谢谢!

最佳答案

您似乎想解决 P 中心问题或 P 中值问题。

来自 Approximability Results for the p-Center Problem作者:Stefan Buettcher，

The p-Center problem, also known as the Min-Max Multicenter problem or the Facility Location problem, is a famous problem from operations research. Informally, it is the problem of placing fire stations in a city so that the maximum time to reach any point in the city is minimized.

来自 Methods for Solving the p-Median Problem: An Annotated Bibliography作者:J. Reese，

The p-median problem is simply stated as: Given a graph or a network G = (V, E), find Vp ⊆ V such that |Vp| = p, where p may either be variable or fixed [...], and that the sum of the shortest distances from the vertices in {V\Vp} to their nearest vertex in Vp is minimized.

这两个问题通常都是 NP 完全问题，因此没有(已知的)方法可以在多项式时间内解决它们。但是您可以尝试各种启发式方法。

关于javascript - JS - 基于密度的稀疏点数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39322143/

稀疏点数codesectionproblemjavascriptarrays

有关javascript - JS - 基于密度的稀疏点数的更多相关文章

  1. 叮咚买菜基于 Apache Doris 统一 OLAP 引擎的应用实践 - 2

    导读：随着叮咚买菜业务的发展，不同的业务场景对数据分析提出了不同的需求，他们希望引入一款实时OLAP数据库，构建一个灵活的多维实时查询和分析的平台，统一数据的接入和查询方案，解决各业务线对数据高效实时查询和精细化运营的需求。经过调研选型，最终引入ApacheDoris作为最终的OLAP分析引擎，Doris作为核心的OLAP引擎支持复杂地分析操作、提供多维的数据视图，在叮咚买菜数十个业务场景中广泛应用。作者｜叮咚买菜资深数据工程师韩青叮咚买菜创立于2017年5月，是一家专注美好食物的创业公司。叮咚买菜专注吃的事业，为满足更多人“想吃什么”而努力，通过美好食材的供应、美好滋味的开发以及美食品牌的孵

  2. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  3. kvm虚拟机安装centos7基于ubuntu20.04系统 - 2

    需求：要创建虚拟机，就需要给他提供一个虚拟的磁盘，我们就在/opt目录下创建一个10G大小的raw格式的虚拟磁盘CentOS-7-x86_64.raw命令格式：qemu-imgcreate-f磁盘格式磁盘名称磁盘大小qemu-imgcreate-f磁盘格式-o?1.创建磁盘qemu-imgcreate-fraw/opt/CentOS-7-x86_64.raw10G执行效果#ls/opt/CentOS-7-x86_64.raw2.安装虚拟机使用virt-install命令，基于我们提供的系统镜像和虚拟磁盘来创建一个虚拟机，另外在创建虚拟机之前，提前打开vnc客户端，在创建虚拟机的时候，通过vnc

  4. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  5. ruby-on-rails - (Ruby,Rails) 基于角色的身份验证和用户管理...？ - 2

    我正在寻找用于Rails的优质管理插件。似乎大多数现有的插件/gem(例如“restful_authentication”、“acts_as_authenticated”)都围绕着self注册等展开。但是，我正在寻找一种功能齐全的基于管理/管理角色的解决方案——但不是简单地附加到另一个非基于角色的解决方案。如果我找不到，我想我会自己动手......只是不想重新发明轮子。 最佳答案 RyanBates最近做了两个关于授权的railscast(注意身份验证和授权之间的区别；身份验证检查用户是否如她所说的那样，授权检查用户是否有权访问资源

  6. ruby-on-rails - Assets 管道损坏 : Not compiling on the fly css and js files - 2

    我开始了一个新的Rails3.2.5项目，Assets管道不再工作了。CSS和Javascript文件不再编译。这是尝试生成Assets时日志的输出:StartedGET"/assets/application.css?body=1"for127.0.0.1at2012-06-1623:59:11-0700Servedasset/application.css-200OK(0ms)[2012-06-1623:59:11]ERRORNoMethodError:undefinedmethod`each'fornil:NilClass/Users/greg/.rbenv/versions/1

  7. ruby-on-rails - Rails - 理解 application.js 和 application.css - 2

    rails新手。只是想了解\assests目录中的这两个文件。例如，application.js文件有如下行://=requirejquery//=requirejquery_ujs//=require_tree.我理解require_tree。只是将所有JS文件添加到当前目录中。根据上下文，我可以看出requirejquery添加了jQuery库。但是它从哪里得到这些jQuery库呢？我没有在我的Assets文件夹中看到任何jquery.js文件——或者直接在我的整个应用程序中没有看到任何jquery.js文件？同样，我正在按照一些说明安装TwitterBootstrap(http:

  8. ruby - 在 Rakefile 中动态生成 Rake 测试任务(基于现有的测试文件) - 2

    我正在根据Rakefile中的现有测试文件动态生成测试任务。假设您有各种以模式命名的单元测试文件test_.rb.所以我正在做的是创建一个以“测试”命名空间内的文件名命名的任务。使用下面的代码，我可以用raketest:调用所有测试require'rake/testtask'task:default=>'test:all'namespace:testdodesc"Runalltests"Rake::TestTask.new(:all)do|t|t.test_files=FileList['test_*.rb']endFileList['test_*.rb'].eachdo|task|n

  9. ruby - 在 Mechanize 中使用 JavaScript 单击链接 - 2

    我有这个:AccountSummary我想单击该链接，但在使用link_to时出现错误。我试过:bot.click(page.link_with(:href=>/menu_home/))bot.click(page.link_with(:class=>'top_level_active'))bot.click(page.link_with(:href=>/AccountSummary/))我得到的错误是:NoMethodError:nil:NilClass的未定义方法“[]” 最佳答案 那是一个javascript链接。Mechan

  10. ruby - 如何使用 Ruby 基于字母数字字符串生成颜色？ - 2

    我想要像“嘿那里”这样的东西变成，例如，#316583。我希望将任意长度的字符串“归结”为十六进制颜色。我不知道从哪里开始。我在想，每个字符串的MD5散列都是不同的-但如何将该散列转换为十六进制颜色数字？ 最佳答案 你可以只取几位前几位:require'digest/md5'color=Digest::MD5.hexdigest('Mytext')[0..5] 关于ruby-如何使用Ruby基于字母数字字符串生成颜色？，我们在StackOverflow上找到一个类似的问题：

随机推荐