z**********g 发帖数: 209 | 1 What is the best efficient algorithm to find intersection point of two lines.
You are given four points A, B , C , d.
Find the intersection point between AB and CD.
Optimize the algorithm as much as you can. | o**********t 发帖数: 406 | | B******5 发帖数: 4676 | | l*********y 发帖数: 142 | 4 解方程有边界条件的吧。
lines.
【在 z**********g 的大作中提到】 : What is the best efficient algorithm to find intersection point of two lines. : You are given four points A, B , C , d. : Find the intersection point between AB and CD. : Optimize the algorithm as much as you can.
| b******v 发帖数: 1493 | 5 我先抛砖引玉,给个最基本的解法吧
假设题目说的是二维平面
(1-s)A+sB = (1-t)C+tD
s(B-A)+t(C-D)=C-A
[B-A, C-D](s,t)' = C-A
(s,t)' = [B-A,C-D]^{-1}*(C-A)
而[B-A,C-D]是2x2矩阵,求逆比较简单
最后结果是交点K=A+{det[C-A,C-D]/det[B-A,C-D]}*(B-A)
lines.
【在 z**********g 的大作中提到】 : What is the best efficient algorithm to find intersection point of two lines. : You are given four points A, B , C , d. : Find the intersection point between AB and CD. : Optimize the algorithm as much as you can.
| x******3 发帖数: 245 | 6 这个是line intersection吧
貌似lz要的是segments intersection
【在 b******v 的大作中提到】 : 我先抛砖引玉,给个最基本的解法吧 : 假设题目说的是二维平面 : (1-s)A+sB = (1-t)C+tD : s(B-A)+t(C-D)=C-A : [B-A, C-D](s,t)' = C-A : (s,t)' = [B-A,C-D]^{-1}*(C-A) : 而[B-A,C-D]是2x2矩阵,求逆比较简单 : 最后结果是交点K=A+{det[C-A,C-D]/det[B-A,C-D]}*(B-A) : : lines.
| h**6 发帖数: 4160 | 7 如果求线段交点的话,首先判断有没有交点。
如果AB*BC和AB*BD符号相反,则有交点,否则没有交点。此处*是叉乘。
其余跟直线交点解法相似,并且不必判断平行的情况。 | b******v 发帖数: 1493 | 8 只要先算出s = det[C-A,C-D]/det[B-A,C-D]
然后判断它是否在[0,1]内,如果不是,则两线段没有交点
如果是,则K=A+s*(B-A)
【在 x******3 的大作中提到】 : 这个是line intersection吧 : 貌似lz要的是segments intersection
| B*****t 发帖数: 335 | 9 the best efficient algorithm here means that division is not
allowed.
【在 b******v 的大作中提到】 : 只要先算出s = det[C-A,C-D]/det[B-A,C-D] : 然后判断它是否在[0,1]内,如果不是,则两线段没有交点 : 如果是,则K=A+s*(B-A)
| b******v 发帖数: 1493 | 10 那你说说不用除法该怎么找交点
【在 B*****t 的大作中提到】 : the best efficient algorithm here means that division is not : allowed.
| B*****t 发帖数: 335 | 11 我原以为是图形学里面的算法问题,找整数交点的坐标,可以不用除法。
不过好像题目是不是这个意思。
可以这样做吧。先判断是否有交点,如果有的话,解个方程,不过还是得用到除法。
【在 b******v 的大作中提到】 : 那你说说不用除法该怎么找交点
| y*c 发帖数: 904 | 12 1. Use y-y_1/x-x_1 == - (y-y_2/x-x_2) to see if a point is on the line and
between the segment.
2. Binary search the point in AB, use median of two end points. |
|