如何判断2个点连成的一条线与某矩形区域有相交？

小湖 · 发表于 2010-12-24 17:09:16

加入我们，或者，欢迎回来。

您需要登录才可以下载或查看，没有帐号？注册会员

x

已知画面中2个点P1和P2的X和Y 和某矩形区域（无倾斜角度）的长宽和位置，如何判断P1和P2的连接线与这个矩形范围有相交的部分？

enghao_lim · 发表于 2010-12-24 21:20:25

本帖最后由 enghao_lim 于 2010-12-24 21:31 编辑

我只想得出这个方法，就是算y=mx+c的说……然后逐条线判断，最后判断是否在里边……继续试看……

不想了……最后产物……没有效率……

class Numeric
def new_between?(a,b)
return between?(a,b) if b > a
return between?(b,a)
end
end
def intersect?(p1,p2,rect)
# gradient
m = (p2[1]-p1[1])/(p2[0]-p1[0]).to_f
# c constant
c = p2[1] - m * p2[0]
# 区域x，y取得
x1 = rect[0]
x2 = x1 + rect[2]
y1 = rect[1]
y2 = y1 + rect[3]
# 其中一点在框内就是有相交
if (p1[0].new_between?(x1,x2) and p1[1].new_between?(y1,y2)) or
(p1[0].new_between?(x1,x2) and p1[1].new_between?(y1,y2))
return true
# 不在框内就逐线判断，如有相交一定会经过边缘。
else
if p1[0] == p2[0]
return true if p1[0].new_between?(x1,x2) and (y1.new_between?(p1[1],p2[1]) or y2.new_between?(p1[1],p2[1]))
elsif p1[1] == p2[1]
return true if p1[1].new_between?(y1,y2) and (x1.new_between?(p1[0],p2[0]) or x2.new_between?(p1[0],p2[0]))
else
_x = (y1 - c)/m
return true if _x.between?(x1,x2)
_x = (y2 - c)/m
return true if _x.between?(x1,x2)
_y = m * x1 + c
return true if _y.between?(y1,y2)
_y = m * x2 + c
return true if _y.between?(y1,y2)
end
end
return false
end
rect = [20,20,10,10] #x,y,width,height
p1 = [21,24] #x,y
p2 = [23,27] #x,y
p intersect?(p1,p2,rect)

复制代码

六祈 · 发表于 2010-12-24 23:37:28

本帖最后由六祈于 2010-12-25 01:09 编辑

比如两个点P1（px1，py1），P2（px2，py2）
矩形的四个顶点为（x1，y1），（x2，y2）等

先求连线方程：y - py1 = (x - px1)*(py2-py1)/(px2-px1)
化简得到y=ax + b（a，b系数可从上式得出）

取矩形一边，譬如（x1，y1）到（x2，y2），同样计算连线方程
得到y=cx + d
相交得到x=（b-d）/（c-a），判断交点x.between?(px1,px2)，如果是则返回true
如果矩形四条边均返回false，则最终结果亦为false

最简单易懂的方法了

小湖 · 发表于 2010-12-25 00:44:41

确实是个纠结的问题，我暂时把线段做成平行于X轴的线段吧，判断起来简单多了……楼上几位辛苦了……

goahead · 发表于 2010-12-25 09:44:12

提示: 作者被禁止或删除内容自动屏蔽

六祈 · 发表于 2010-12-25 13:04:39

稍稍看了下那个剪裁算法，似乎判断两个点是否一个在矩形内一个在矩形外会更容易一些

IamI · 发表于 2010-12-25 13:31:44

本帖最后由 IamI 于 2010-12-25 13:34 编辑

大家好，II又来卖弄他的LP了

POINT = Struct.new("Point", :x, :y)
def POINT.initialize(x,y)
@x = x;@y = y
end
def go
p1 = POINT.new(2,3)
p2 = POINT.new(4,5)
r = Rect.new(1,3,6,7)
a = p2.y - p1.y
b = p1.x - p2.x
c = p1.y * (p2.x - p1.x) - p1.x * (p2.y - p1.y)
# 直线方程 ax + by + c = 0
# 以下线规(LP)
r1 = POINT.new(r.x,r.y)
r2 = POINT.new(r.x + r.width,r.y)
r3 = POINT.new(r.x,r.y + r.height)
r4 = POINT.new(r.x + r.width,r.y + r.height)
v1 = a * r1.x + b * r1.y + c
v2 = a * r2.x + b * r2.y + c
v3 = a * r3.x + b * r3.y + c
v4 = a * r4.x + b * r4.y + c
return true if v1 == 0 or v2 == 0 or v3 == 0 or v4 == 0
t = 0
t += 1 if v1 > 0
t += 1 if v2 > 0
t += 1 if v3 > 0
t += 1 if v4 > 0
return false if t == 0 or t == 4
return true
end
p go

复制代码

OTL这玩意儿判断的是直线不是线段，懒得改了……

苏小脉 · 发表于 2010-12-26 05:55:12

本帖最后由苏小脉于 2010-12-26 06:07 编辑

　　在 R2 中检测有两个端点的线段是否与一个矩形碰撞的问题可以被划分为检测线段是否和矩形的任意边相交，或线段的任意端点在矩形内部（包括刚好在边上）。

　　前者是四次线段相交检测。对于线段相交检测，最明显的途径自然就是求包含这两条线段的直线的交点，然后判断是否在线段范围内。然而，这个方法无法避免浮点运算。为了提高效率，就需要避免浮点运算，只进行整数定点运算。下面的算法，是判断两条线段各自的端点是否分别在包含另一条线段的直线的两端。只有在这种情况下（当且仅当），两条线段才相交。这就涉及到另一个问题——判断两个点是否分别在一条直线的两端。这里可以分别使用两个点按固定的顺序连接线段的两个端点（即直线上的两个点），形成两个凸包（三角形），然后检测凸包的形成是通过顺时针还是逆时针旋转。如果这两个点各自在直线的一端，那么必然有着相反的旋转方向，一个是顺时针，一个是逆时针。

def cw_test(ax, ay, bx, by, cx, cy)
lhs = (by - ay) * (cx - ax)
rhs = (cy - ay) * (bx - ax)
if lhs == rhs then 0
elsif lhs < rhs then 1
else 2
end
end
def bound?(x, a, b)
a <= x && x <= b || a >= x && x >= b
end
def bound_inside?(x, y, ax, ay, bx, by)
bound?(x, ax, bx) && bound?(y, ay, by)
end
def seg_intersect?(px1, py1, px2, py2, qx1, qy1, qx2, qy2)
t1 = cw_test(px1, py1, qx1, qy1, qx2, qy2)
t2 = cw_test(px2, py2, qx1, qy1, qx2, qy2)
t3 = cw_test(qx1, qy1, px1, py1, px2, py2)
t4 = cw_test(qx2, qy2, px1, py1, px2, py2)
3 == (t1 | t2) && 3 == (t3 | t4) ||
0 == t1 && bound_inside?(px1, py1, qx1, qy1, qx2, qy2) ||
0 == t2 && bound_inside?(px2, py2, qx1, qy1, qx2, qy2) ||
0 == t3 && bound_inside?(qx1, qy1, px1, py1, px2, py2) ||
0 == t4 && bound_inside?(qx2, qy2, px1, py1, px2, py2)
end
def point_lies_in?(x, y, ax, ay, bx, by, cx, cy, dx, dy)
(cw_test(x, y, ax, ay, bx, by) |
cw_test(x, y, bx, by, cx, cy) |
cw_test(x, y, cx, cy, dx, dy) |
cw_test(x, y, dx, dy, ax, ay)) != 3
end
def seg_rect_collide?(ax, ay, bx, by, tlx, tly, trx, try, brx, bry, blx, bly)
point_lies_in?(ax, ay, tlx, tly, trx, try, brx, bry, blx, bly) ||
point_lies_in?(bx, by, tlx, tly, trx, try, brx, bry, blx, bly) ||
seg_intersect?(ax, ay, bx, by, tlx, tly, trx, try) ||
seg_intersect?(ax, ay, bx, by, trx, try, brx, bry) ||
seg_intersect?(ax, ay, bx, by, brx, bry, blx, bly) ||
seg_intersect?(ax, ay, bx, by, blx, bly, tlx, tly)
end

复制代码

seg_rect_collide? 是检测线段 (ax, ay)-(bx, by) 与矩形碰撞的函数。矩形的四个顶点 (tlx, tly), (trx, try), (brx, bry), (blx, bly) 是按时钟顺序排列的，比如“左上、右上、右下、左下”这样的顺序。

详情可参考：
http://szsu.wordpress.com/2010/12/25/seg_rect_collision/

附一段在 RM 中的随机化、可视化测试脚本：

def init_sprite(sprite, color)
sprite.ox = sprite.oy = 5
sprite.bitmap = Bitmap.new(10, 10)
sprite.bitmap.fill_rect(0, 0, 10, 10, color)
end
yellow = Color.new(0xff, 0xff, 0)
blue = Color.new(0, 0, 0xff)
init_sprite(a = Sprite.new, yellow)
init_sprite(b = Sprite.new, yellow)
init_sprite(tl = Sprite.new, blue)
init_sprite(tr = Sprite.new, blue)
init_sprite(br = Sprite.new, blue)
init_sprite(bl = Sprite.new, blue)
loop do
ax = rand(640)
ay = rand(480)
bx = rand(640)
by = rand(480)
tlx = rand(320)
tly = rand(240)
brx = rand(320) + 320
bry = rand(240) + 240
a.x = ax
a.y = ay
b.x = bx
b.y = by
tl.x = tlx
tl.y = tly
tr.x = brx
tr.y = tly
br.x = brx
br.y = bry
bl.x = tlx
bl.y = bry
p "(#{ax},#{ay}), (#{bx},#{by})",
"(#{tlx}, #{tly}), (#{brx}, #{tly}), (#{brx}, #{bry}), (#{tlx}, #{bry})",
seg_rect_collide?(ax, ay, bx, by, tlx, tly, brx, tly, brx, bry, tlx, bry)
Graphics.update
end

复制代码

帐号		自动登录	找回密码
密码			注册会员

[已经解决] 如何判断2个点连成的一条线与某矩形区域有相交？

加入我们，或者，欢迎回来。

点评

点评

评分

点评

评分

点评

评分

贵宾

开拓者