[转载] 怎样判断两点连线是否与一椭球相交? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Computation - 科学计算

[转载] 怎样判断两点连线是否与一椭球相交?

[转载] 怎样判断两点连线是否与一椭球相交?# Computation - 科学计算

s*g2002-03-14 08:03

1 楼

【以下文字转载自 Programming 讨论区,原文如下】
发信人: swingswing (雪天**Mocha Java), 信区: Programming
标题: [转载] 怎样判断两点连线是否与一椭球相交?
发信站: The unknown SPACE (Thu Mar 14 20:19:18 2002), WWW转贴
【以下文字转载自 Java 讨论区,原文如下】
发信人: swingswing (雪天**Mocha Java), 信区: Java
标题: 怎样判断两点连线是否与一椭球相交?
发信站: The unknown SPACE (Thu Mar 14 20:17:55 2002) WWW-POST
逐点判断速度太慢了,各位有没有知道这方面的解析式的??
比如只需知道这两点和椭球的参数,就可以很快判断的?
多谢了!

a*a2002-03-14 08:03

2 楼

你的椭球经过座标变换可以变球吧？那么变球了以后，一条直线到球心的距离如果
比半径小，是不是就相交了？从球心到直线的垂足是不是就在球的内部？
如果这个垂足在两点间，是不是就可以说两点连线和球相交了？

【在 s********g 的大作中提到】

: 【以下文字转载自 Programming 讨论区,原文如下】
: 发信人: swingswing (雪天**Mocha Java), 信区: Programming
: 标题: [转载] 怎样判断两点连线是否与一椭球相交?
: 发信站: The unknown SPACE (Thu Mar 14 20:19:18 2002), WWW转贴
: 【以下文字转载自 Java 讨论区,原文如下】
: 发信人: swingswing (雪天**Mocha Java), 信区: Java
: 标题: 怎样判断两点连线是否与一椭球相交?
: 发信站: The unknown SPACE (Thu Mar 14 20:17:55 2002) WWW-POST
: 逐点判断速度太慢了,各位有没有知道这方面的解析式的??
: 比如只需知道这两点和椭球的参数,就可以很快判断的?

d*e2002-03-14 08:03

3 楼

应该可以用binary search吧?
如果没有解析饰的话,用一个sweep line(plane)应该可以打倒目的

【在 s********g 的大作中提到】

s*g2002-03-14 08:03

4 楼

我也考虑过用binary search, 可是search到什么程度就可以确定不相交了?
什么是sweep line? 如果是一个点一个点的看的话,计算时间会很长...

【在 d******e 的大作中提到】

: 应该可以用binary search吧?
: 如果没有解析饰的话,用一个sweep line(plane)应该可以打倒目的

s*s2002-03-14 08:03

5 楼

That is not the right direction, I think.
You are all CS-mind. :-)

【在 s********g 的大作中提到】

: 我也考虑过用binary search, 可是search到什么程度就可以确定不相交了?
: 什么是sweep line? 如果是一个点一个点的看的话,计算时间会很长...

s*g2002-03-14 08:03

6 楼

hehe, lets work on the right direction.....
give a direction first...:P

【在 s***s 的大作中提到】

: That is not the right direction, I think.
: You are all CS-mind. :-)

p*e2002-03-14 08:03

7 楼

You can find the slopes of the two tangent lines starting from
any point on the line. If the slopes of the line is b/w these two
slopes, then the line intersect the ellipse.

【在 s********g 的大作中提到】

w*l2002-03-14 08:03

8 楼

I am surprised that these CS guys are so ignorant of Math. If my understanding
is correct, this is almost a high shool level problem. If his ellipse means
the quadratic surface, then just solve the joint equations:
1. (x-x0)'A(x-x0)=1
2. x=x1+t*(x2-x1)
where A is a square matrix, x0 is the center of the ellipse, x1 and x2 are two
points on the line. Plug 2 into 1, it remain to check whether the following
eqaution about t has solution:
[x1+t*(x2-x1)]'A[x1+t*(x2-x1)]=1
which is a quadratic functio

【在 s***s 的大作中提到】

: That is not the right direction, I think.
: You are all CS-mind. :-)