math - 如何确定两个移动点何时彼此可见？

Question

假设我有两个点，Point1 和 Point2。在任何给定的时间，这些点可能处于不同的位置——它们不一定是静态的。

Point1 位于时间 t 的某个位置，其位置由给出时间 t 的 x 和 y 坐标的连续函数 x1(t) 和 y1(t) 定义。这些函数是不可微的，它们是由线段分段构造的。

Point2 是相同的，具有 x2(t) 和 y2(t)，每个函数具有相同的属性。

可能妨碍可见性的障碍物是简单(且不可移动)的多边形。

如何找到可见性的边界点？

即有两种边界:点变得可见和不可见。

对于变得可见的边界 i，存在一些 ϵ>0，使得对于任何实数 a，a ∈ (i-ϵ, i) ，Point1 和 Point2 不可见(即连接 (x1(a), y1(a)) 到(x2(a), y2(x)) 越过一些障碍)。

对于 b ∈ (i, i+ϵ) 它们是可见的。

而对于变得不可见，则相反。

但是我能否找到这样一个精确的边界，如果可以，如何找到？

Answer 1

好的，我现在对问题有了更清晰的了解，并受到@walkytalky 建议的启发，这里有一个更详细的答案。

你提到了p1和 p2沿直线段行驶。我不知道这些段是否以一种方式对齐，使得 p1和 p2总是同时开始新的段。但是，您始终可以将线段切割成两条线段(具有相同的斜率)，以便 p1和 p2总是同时开始新的线段。

假设 p1沿线行驶A-B , 和 p2 (同时)沿着 C-D 旅行作为参数 t从 0 到 1。(也就是说，在时间 t=0.5 ， p1 位于 A-B 的中间，而 p2 位于 C-D 的中间。)

通过出租 Ax和 Ay表示点 A 的 x 和 y 坐标(对于 B 、 C 和 D )我们可以表达 p1和 p2作为 t 的函数通过以下方式:

p1(t) = (Ax + t*(Bx - Ax), Ay + t(By - Ay))
p2(t) = (Cx + t*(Dx - Cx), Cy + t(Dy - Cy))

(例如，当 t=0 ， Ax + t*(Bx - Ax) 计算为 Ax ，而当 t=1 计算为 Bx 。)

要找到每个“a-vertex-is-passing-by-between-p1-and-p2”时间，我们执行以下操作:

对于每个障碍物顶点 v=(Vx, Vy)我们需要找到一个 t以便 p1(t) , p2(t)和 v彼此一致。

这可以通过求解以下方程(两个方程和两个未知数， t 和 k )来完成:

Vx=p1(t).x + k*(p2(t).x - p1(t).x)
Vy=p1(t).y + k*(p2(t).y - p1(t).y)`

如 k位于 0 和 1 之间，多边形顶点 v实际上是介于(扩展) A-B线和(扩展) C-D线。如 t也在 0 和 1 之间，顶点 v实际上是通过 p1-p2点沿这些线段移动的时间线(因为当 t 为 1.3 时，这些点将已经在新线段上)。

一旦计算了所有“a-vertex-is-passing-by-p1-and-p2”时间，找出其余部分是一项简单的任务。 (也就是说，弄清楚它是“在视线范围内”、“在视线范围之外”还是“两者都不是”类型的传递):

对于所有对 t0和 t1连续顶点通过次数，您检查线 p1((t1-t0)/2)-p2((t1-t0)/2)没有与多边形边的交点。如果它没有交点，则点将在整个时间段内( t0-t1 )在视线内，否则它们将在整个时间段内看不见(因为在此时间段内没有其他顶点通过)。