Project1

标题: 如何判断2个点连成的一条线与某矩形区域有相交？ [打印本页]
作者: 小湖    时间: 2010-12-24 17:09
标题: 如何判断2个点连成的一条线与某矩形区域有相交？
已知画面中2个点P1和P2的X和Y 和某矩形区域（无倾斜角度）的长宽和位置，如何判断P1和P2的连接线与这个矩形范围有相交的部分？
作者: enghao_lim    时间: 2010-12-24 21:20
本帖最后由 enghao_lim 于 2010-12-24 21:31 编辑

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

不想了……最后产物……没有效率……
  1. class Numeric
  2.   def new_between?(a,b)
  3.     return between?(a,b) if b > a
  4.     return between?(b,a)
  5.   end
  6. end

  8. def intersect?(p1,p2,rect)
  9.   # gradient
  10.   m = (p2[1]-p1[1])/(p2[0]-p1[0]).to_f
  11.   # c constant
  12.   c = p2[1] - m * p2[0]
  13.   # 区域x，y取得
  14.   x1 = rect[0]
  15.   x2 = x1 + rect[2]
  16.   y1 = rect[1]
  17.   y2 = y1 + rect[3]
  18.   # 其中一点在框内就是有相交
  19.   if (p1[0].new_between?(x1,x2) and p1[1].new_between?(y1,y2)) or
  20.      (p1[0].new_between?(x1,x2) and p1[1].new_between?(y1,y2))
  21.     return true
  22.   # 不在框内就逐线判断，如有相交一定会经过边缘。
  23.   else
  24.     if p1[0] == p2[0]
  25.       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]))
  26.     elsif p1[1] == p2[1]
  27.       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]))
  28.     else
  29.       _x = (y1 - c)/m
  30.       return true if _x.between?(x1,x2)
  31.       _x = (y2 - c)/m
  32.       return true if _x.between?(x1,x2)
  33.       _y = m * x1 + c
  34.       return true if _y.between?(y1,y2)
  35.       _y = m * x2 + c
  36.       return true if _y.between?(y1,y2)
  37.     end
  38.   end
  39.   return false
  40. end

  42. rect = [20,20,10,10] #x,y,width,height
  43. p1 = [21,24] #x,y
  44. p2 = [23,27] #x,y
  45. p intersect?(p1,p2,rect)
复制代码
作者: 六祈    时间: 2010-12-24 23:37
本帖最后由 六祈 于 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
确实是个纠结的问题，我暂时把线段做成平行于X轴的线段吧，判断起来简单多了……楼上几位辛苦了……
作者: goahead    时间: 2010-12-25 09:44
提示: 作者被禁止或删除 内容自动屏蔽
作者: 六祈    时间: 2010-12-25 13:04
稍稍看了下那个剪裁算法，似乎判断两个点是否一个在矩形内一个在矩形外会更容易一些
作者: IamI    时间: 2010-12-25 13:31
本帖最后由 IamI 于 2010-12-25 13:34 编辑

大家好，II又来卖弄他的LP了
  1. POINT = Struct.new("Point", :x, :y)
  2. def POINT.initialize(x,y)
  3.   @x = x;@y = y
  4. end



  8. def go
  9.   p1 = POINT.new(2,3)
  10.   p2 = POINT.new(4,5)
  11.   r = Rect.new(1,3,6,7)
  12.   a = p2.y - p1.y
  13.   b = p1.x - p2.x
  14.   c = p1.y * (p2.x - p1.x) - p1.x * (p2.y - p1.y)
  15.   
  16.   # 直线方程 ax + by + c = 0
  17.   # 以下线规(LP)
  18.   r1 = POINT.new(r.x,r.y)
  19.   r2 = POINT.new(r.x + r.width,r.y)
  20.   r3 = POINT.new(r.x,r.y + r.height)
  21.   r4 = POINT.new(r.x + r.width,r.y + r.height)
  22.   
  23.   v1 = a * r1.x + b * r1.y + c
  24.   v2 = a * r2.x + b * r2.y + c
  25.   v3 = a * r3.x + b * r3.y + c
  26.   v4 = a * r4.x + b * r4.y + c
  27.   
  28.   return true if v1 == 0 or v2 == 0 or v3 == 0 or v4 == 0
  29.   
  30.   t = 0
  31.   t += 1 if v1 > 0
  32.   t += 1 if v2 > 0
  33.   t += 1 if v3 > 0
  34.   t += 1 if v4 > 0
  35.   
  36.   return false if t == 0 or t == 4
  37.   return true
  38. end
  39. p go
复制代码
OTL这玩意儿判断的是直线不是线段，懒得改了……
作者: 苏小脉    时间: 2010-12-26 05:55
本帖最后由 苏小脉 于 2010-12-26 06:07 编辑

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

　　前者是四次线段相交检测。对于线段相交检测，最明显的途径自然就是求包含这两条线段的直线的交点，然后判断是否在线段范围内。然而，这个方法无法避免浮点运算。为了提高效率，就需要避免浮点运算，只进行整数定点运算。下面的算法，是判断两条线段各自的端点是否分别在包含另一条线段的直线的两端。只有在这种情况下（当且仅当），两条线段才相交。这就涉及到另一个问题——判断两个点是否分别在一条直线的两端。这里可以分别使用两个点按固定的顺序连接线段的两个端点（即直线上的两个点），形成两个凸包（三角形），然后检测凸包的形成是通过顺时针还是逆时针旋转。如果这两个点各自在直线的一端，那么必然有着相反的旋转方向，一个是顺时针，一个是逆时针。
  1. def cw_test(ax, ay, bx, by, cx, cy)
  2.   lhs = (by - ay) * (cx - ax)
  3.   rhs = (cy - ay) * (bx - ax)
  4.   if lhs == rhs then 0
  5.   elsif lhs < rhs then 1
  6.   else 2
  7.   end
  8. end

  10. def bound?(x, a, b)
  11.   a <= x && x <= b || a >= x && x >= b
  12. end

  14. def bound_inside?(x, y, ax, ay, bx, by)
  15.   bound?(x, ax, bx) && bound?(y, ay, by)
  16. end

  18. def seg_intersect?(px1, py1, px2, py2, qx1, qy1, qx2, qy2)
  19.   t1 = cw_test(px1, py1, qx1, qy1, qx2, qy2)
  20.   t2 = cw_test(px2, py2, qx1, qy1, qx2, qy2)
  21.   t3 = cw_test(qx1, qy1, px1, py1, px2, py2)
  22.   t4 = cw_test(qx2, qy2, px1, py1, px2, py2)
  23.   3 == (t1 | t2) && 3 == (t3 | t4) ||
  24.   0 == t1 && bound_inside?(px1, py1, qx1, qy1, qx2, qy2) ||
  25.   0 == t2 && bound_inside?(px2, py2, qx1, qy1, qx2, qy2) ||
  26.   0 == t3 && bound_inside?(qx1, qy1, px1, py1, px2, py2) ||
  27.   0 == t4 && bound_inside?(qx2, qy2, px1, py1, px2, py2)
  28. end

  30. def point_lies_in?(x, y, ax, ay, bx, by, cx, cy, dx, dy)
  31.   (cw_test(x, y, ax, ay, bx, by) |
  32.    cw_test(x, y, bx, by, cx, cy) |
  33.    cw_test(x, y, cx, cy, dx, dy) |
  34.    cw_test(x, y, dx, dy, ax, ay)) != 3
  35. end

  37. def seg_rect_collide?(ax, ay, bx, by, tlx, tly, trx, try, brx, bry, blx, bly)
  38.   point_lies_in?(ax, ay, tlx, tly, trx, try, brx, bry, blx, bly) ||
  39.   point_lies_in?(bx, by, tlx, tly, trx, try, brx, bry, blx, bly) ||
  40.   seg_intersect?(ax, ay, bx, by, tlx, tly, trx, try) ||
  41.   seg_intersect?(ax, ay, bx, by, trx, try, brx, bry) ||
  42.   seg_intersect?(ax, ay, bx, by, brx, bry, blx, bly) ||
  43.   seg_intersect?(ax, ay, bx, by, blx, bly, tlx, tly)
  44. 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 中的随机化、可视化测试脚本：

  2. def init_sprite(sprite, color)
  3.   sprite.ox = sprite.oy = 5
  4.   sprite.bitmap = Bitmap.new(10, 10)
  5.   sprite.bitmap.fill_rect(0, 0, 10, 10, color)
  6. end

  8. yellow = Color.new(0xff, 0xff, 0)
  9. blue = Color.new(0, 0, 0xff)
  10. init_sprite(a = Sprite.new, yellow)
  11. init_sprite(b = Sprite.new, yellow)
  12. init_sprite(tl = Sprite.new, blue)
  13. init_sprite(tr = Sprite.new, blue)
  14. init_sprite(br = Sprite.new, blue)
  15. init_sprite(bl = Sprite.new, blue)

  17. loop do
  18.   ax = rand(640)
  19.   ay = rand(480)
  20.   bx = rand(640)
  21.   by = rand(480)
  22.   tlx = rand(320)
  23.   tly = rand(240)
  24.   brx = rand(320) + 320
  25.   bry = rand(240) + 240

  27.   a.x = ax
  28.   a.y = ay
  29.   b.x = bx
  30.   b.y = by
  31.   tl.x = tlx
  32.   tl.y = tly
  33.   tr.x = brx
  34.   tr.y = tly
  35.   br.x = brx
  36.   br.y = bry
  37.   bl.x = tlx
  38.   bl.y = bry

  40.   p  "(#{ax},#{ay}), (#{bx},#{by})",
  41.   "(#{tlx}, #{tly}), (#{brx}, #{tly}), (#{brx}, #{bry}), (#{tlx}, #{bry})",
  42.   seg_rect_collide?(ax, ay, bx, by, tlx, tly, brx, tly, brx, bry, tlx, bry)
  43.   
  44.   Graphics.update
  45. end
复制代码




欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1