草庐IT

javascript - 找到两个移动物体的最佳交点

coder 2024-05-09 原文

我想大幅优化我的一个算法，我会尽我所能来解释它。

主题

t = 0 时，我们处于二维欧几里得系统中。 在这个系统中有两个对象:O1 和O2。

O1和O2分别位于PA和PC点。

O1 以恒定且已知的速度向点 PB 移动。物体到达 PB 时停止。

O2 可以恒定且已知的速度在任何方向上不同或不 O1。在时间 0，O2 没有方向，我们需要为它找到一个方向。

已知参数:

  • O1 : 位置、方向、速度
  • O2:位置、速度

这是系统的小图。

我们想找到点 PI 和时间 ti 为: O1 在时间 ti 的位置 = O2 在时间 ti 的位置= 圆周率。然后让物体O2移动到PI点，得到O2方向。

选择O2的方向(Point Pi)并且两个对象O1和O2都在移动时，对象将永远不会停止或等待彼此。

在这种情况下，结果将是这样的(PI 在这张图片上标注为 D)。

算法

你可以在这个 jsfiddle 找到用 JS 编写的工作算法，这也是理解问题的好方法。

此时我使用了一个简单的算法，它可以工作，但是可以进行很多操作，我会得到最佳的交点时间，然后得到交点位置。

为了得到这个时间，我会检查一下O1的位置，并检查O2此时是否有可能去这个位置。如果O2不能及时到达目标，我们将增加150%的时间，但是如果O2当时可以越过O1-B线，我们将减少50%的时间。

最终，经过多次近似，我们将找到两个物体相遇的最佳时间。

伪代码

function getOptimalIntersectionTime time
   if distance between O1 and O2 at the time `time` < 1
       return time
   else if O2 could not reach the object O1 at the time `time`
       return getOptimalIntersectionTime time * 1.5
   else
       return getOptimalIntersectionTime time * 0.5

我为什么担心？

我的算法有效，但在某些情况下(例如 jsFiddle 中的“Reverse Case”)需要大量的微积分才能找到最佳点。

在这个 jsFiddle 中，我们对位置(-1000 到 1000)和速度(1-200)使用了很小的值，但是这个算法使用更大的数字会显着变慢。

我知道过早优化是个坏主意，但我正处于项目的末尾(包括数据库插入/选择和数据分析，包括多次调用该算法)并且该算法最多需要 80在某些情况下项目系统资源的百分比，因此改进可以真正提高系统的稳定性和响应能力。

最佳答案

不失一般性，令 O2 位于 (0,0)。

设 s 和 v 为 O1 的位置和速度矢量，v2 为 O2 的速度，t 为拦截时间。然后我们有:

|s + v * t| = t * v2

根据距离的定义:

(sx + vx * t) ^ 2 + (sy + vy * t) ^ 2 = (t * v2) ^ 2

将其相乘并重新排序得到:

  sx^ 2 + 2 * sx * vx * t + vx^2 * t^2
+ sy^ 2 + 2 * sy * vy * t + vy^2 * t^2
-                           v2^2 * t^2
= 0

即

  sx^2 + sy^2 + (2 * sx * vx + 2 * sy * vy) * t + (vx^2 + vy^2 - v2^2) * t^2 = 0
  \---   ---/   \------------   ----------/       \--------   ------/
      \ /                    \ /                           \ /
       c                      b                             a

如您所见，这是一个关于 t 的二次方程。我们可以简单地应用 quadratic formula找到 t 的两个可能值(如果方程无解，那是因为不可能截取)。您可能希望使用最早的 future 拦截，即 > 0 的较小 t。

一旦计算出 t，找到拦截点和拦截方向应该很容易。

总而言之，这个问题可以在常数时间内解决，不需要迭代。

关于javascript - 找到两个移动物体的最佳交点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10358022/

物体javascriptstrongcodesectionalgorithmmathoptimizationgeometry

有关javascript - 找到两个移动物体的最佳交点的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  4. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  5. ruby-on-rails - 如何重命名或移动 Rails 的 README_FOR_APP - 2

    当我在我的Rails应用程序根目录中运行rakedoc:app时，API文档是使用/doc/README_FOR_APP作为主页生成的。我想向该文件添加.rdoc扩展名，以便它在GitHub上正确呈现。更好的是，我想将它移动到应用程序根目录(/README.rdoc)。有没有办法通过修改包含的rake/rdoctask任务在我的Rakefile中执行此操作？是否有某个地方可以查找可以修改的主页文件的名称？还是我必须编写一个新的Rake任务？额外的问题:Rails应用程序的两个单独文件/README和/doc/README_FOR_APP背后的逻辑是什么？为什么不只有一个？

  6. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  7. ruby-on-rails - capybara ::ElementNotFound:无法找到 xpath "/html" - 2

    我正在学习http://ruby.railstutorial.org/chapters/static-pages上的RubyonRails教程并遇到以下错误StaticPagesHomepageshouldhavethecontent'SampleApp'Failure/Error:page.shouldhave_content('SampleApp')Capybara::ElementNotFound:Unabletofindxpath"/html"#(eval):2:in`text'#./spec/requests/static_pages_spec.rb:7:in`(root)'

  8. [Vuforia]二.3D物体识别 - 2

    之前说过10之后的版本没有3dScan了，所以还是9.8的版本或者之前更早的版本。 3d物体扫描需要先下载扫描的APK进行扫面。首先要在手机上装一个扫描程序，扫描现实中的三维物体，然后上传高通官网，在下载成UnityPackage类型让Unity能够使用这个扫描程序可以从高通官网上进行下载，是一个安卓程序。点到Tools往下滑，找到VuforiaObjectScanner下载后解压数据线连接手机，将apk文件拷入手机安装然后刚才解压文件中的Media文件夹打开，两个PDF图打印第一张A4-ObjectScanningTarget.pdf，主要是用来辅助扫描的。好了，接下来就是扫描三维物体。将瓶

  9. ruby-on-rails - rbenv:从 RVM 移动到 rbenv 后，在 Jenkins 执行 shell 中找不到命令 - 2

    我从Ubuntu服务器上的RVM转移到rbenv。当我使用RVM时，使用bundle没有问题。转移到rbenv后，我在Jenkins的执行shell中收到“找不到命令”错误。我内爆并删除了RVM，并从~/.bashrc'中删除了所有与RVM相关的行。使用后我仍然收到此错误:rvmimploderm~/.rvm-rfrm~/.rvmrcgeminstallbundlerecho'exportPATH="$HOME/.rbenv/bin:$PATH"'>>~/.bashrcecho'eval"$(rbenvinit-)"'>>~/.bashrc.~/.bashrcrbenvversions

  10. ruby - 如何找到调用当前方法的方法 - 2

    如何找到调用此方法的位置？defto_xml(options={})binding.pryoptions=options.to_hifoptions&&options.respond_to?(:to_h)serializable_hash(options).to_xml(options)end 最佳答案 键入caller。这将返回当前调用堆栈。文档:Kernel#caller.例子[0]%rspecspec10/16|===================================================62=====

随机推荐