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. |
|
