1

对于我的研究，我需要编写一个有效的并行程序来找到一个在给定时刻在矩阵中对于最大数量的其他对象不可见的对象。

主要特征：

  • 带 3 台计算机的 MPI
  • OpenMP 在每台 PC 上使用 4 个内核
  • 可选 CUDA

数据：

  • 对象被放置在大小为 AxB 的矩阵中。
  • 我有一个包含对象坐标及其时间戳的大文件。
  • 物体是飞行，但速度是恒定的。

问题：

如果我从一个对象 (C1) 的单元格中心到另一个对象 (C3) 的单元格中心画一条线，并且这条线与另一个对象 (C2) 交叉的单元格，这意味着：

  • C1 看不到 C3
  • C3 看不到 C1

问题

我的问题：

是否有任何已知的类似问题的算法（可能是图形中的一些问题），我可以查看解决方案？

感谢您的任何帮助。

更新：最终解决方案 https://github.com/anod/CriticalLevelCalculation

4

1 回答 1

0

我认为解决方案是简单的数学。

  1. 取 2 个点 p1 和 p2。
  2. 找到他们的线性方程。
  3. 与所有点进行比较，如果它们中的任何一个属于该方程并且在 p1 和 2 之间。
  4. 如果某些点挡住了路，那么 p1 和 p2 将再投一票是不可见的。

希望这可以帮助你。

于 2012-10-07T13:29:06.720 回答