s********g
发帖数: 8 | 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**a
发帖数: 416 | 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******e
发帖数: 2265 | 3 应该可以用binary search吧?
如果没有解析饰的话,用一个sweep line(plane)应该可以打倒目的
【在 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
: 逐点判断速度太慢了,各位有没有知道这方面的解析式的??
: 比如只需知道这两点和椭球的参数,就可以很快判断的?
| s********g
发帖数: 8 | 4 我也考虑过用binary search, 可是search到什么程度就可以确定不相交了?
什么是sweep line? 如果是一个点一个点的看的话,计算时间会很长...
【在 d******e 的大作中提到】
: 应该可以用binary search吧?
: 如果没有解析饰的话,用一个sweep line(plane)应该可以打倒目的
| s***s
发帖数: 38 | 5 That is not the right direction, I think.
You are all CS-mind. :-)
【在 s********g 的大作中提到】
: 我也考虑过用binary search, 可是search到什么程度就可以确定不相交了?
: 什么是sweep line? 如果是一个点一个点的看的话,计算时间会很长...
| s********g
发帖数: 8 | 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****e
发帖数: 468 | 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 的大作中提到】
: 【 以下文字转载自 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
: 逐点判断速度太慢了,各位有没有知道这方面的解析式的??
: 比如只需知道这两点和椭球的参数,就可以很快判断的?
| w**l
发帖数: 5 | 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. :-)
|
|
