logo标签列表

检测一条直线是否与一个球体相交

algorithmhaskell3dgeometry
5
尝试创建一个非常简单的布尔函数，以确定一条直线是否与一个球相交。
尽管问题类似，但这似乎不是我想要的：Intersection of a line and a Sphere? 我还尝试了以下列出的算法： http://www.docstoc.com/docs/7747820/Intersection-of-a-Line-and-a-Sphere 和 http://www.ccs.neu.edu/home/fell/CSU540/programs/RayTracingFormulas.htm，但都没有真正成功。
我最近的代码（用Haskell编写）如下：
data Point = Point { x :: Float, y :: Float, z :: Float} deriving (Eq, Show, Read)
data Sphere = Sphere { center :: Point, radius :: Float } deriving (Eq, Show, Read)

inView :: Point -> Point -> Sphere -> Bool
inView (Point x1 y1 z1) (Point x2 y2 z2) (Sphere (Point x3 y3 z3) r)
  | result > 0 && result < r = False
  | otherwise                = True
  where result = top/bot
        top = (x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1) + (z3 - z1) * (z2 - z1)
        bot = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1)

如果两个点之间有直接的视线，它将返回true。这对于一些简单的情况有效，但对于应该有效的其他情况则失败，例如：

inView (Point {x = 43.64, y = -183.20, z = 187.37}) (Point {x = 42.04, y = -183.58, z = 187.37}) (Sphere (Point 0 0 0) 5)

非常感谢您的帮助。

1
你使用的算法可能是错误的。通过量纲分析很容易看出来——top和bot具有面积的量纲，而result是无量纲的；r具有长度的量纲，因此result < r没有意义。 - kennytm
@KennyTM：观察得很好。可惜维度不是我们类型系统的默认部分。如果是的话，它将捕获许多错误。 - sigfpe
4个回答
2
您使用了错误的等式。如果您的线条表示为：
p1 + u (p2 - p1)

(其中u是一个标量)，然后top/bot找到使该表达式尽可能靠近球体中心的u。

所以我会修改您的代码：

where u = top/bot
      nearestPoint = {- p1 + u (p2 - p1) -}
      result = {- distance between nearestPoint and p3 -}

请填写伪代码，你就会明白了。你刚才误解了result的意思。

顺便说一下，你可以使用Data.VectorSpace来大大简化你的代码。我可以很容易地使用它来完整地编写我的修正：

import Data.VectorSpace

type Point = (Double, Double, Double)
inView :: Point -> Point -> Sphere -> Bool
inView p1 p2 (Sphere p3 r) = result < r
    where u = top/bot
          top = ...
          bot = ...
          nearestPoint = p1 ^+^ u *^ (p2 ^-^ p1)
          result = magnitude (p3 ^-^ nearestPoint)
1

我不知道这是否是最有效的方法，但需要考虑一件事：

如果从线到球心的垂直距离小于或等于球的半径，则该线与球相交。

那么你的问题就变成了：如何计算点到线的距离？

0

我觉得你想要使用的是

inView :: Point -> Point -> Sphere -> Bool
inView (Point x1 y1 z1) (Point x2 y2 z2) (Sphere (Point x3 y3 z3) r)
  | result > 0 && result < r^2 = False // is this correct? I know nothing about Haskell, but seems like this should be True
  | otherwise                  = True
  where result = -t1^2/t2 + t3
        t1 = (x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1) + (z3 - z1) * (z2 - z1)
        t2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1)
        t3 = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1) + (z3 - z1) * (z3 - z1)

注意：我不知道 Haskell 中表示平方的符号是什么，所以我在上面使用了 ^2。

e: 在这里和这里工作

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接