×

Loading...
Ad by
  • 技多不压身,工到自然成:安省技工证书特训班,点击咨询报名!
Ad by
  • 技多不压身,工到自然成:安省技工证书特训班,点击咨询报名!

问一个算法问题,有什么方法可以知道一条线穿过一个正方形?

本文发表在 rolia.net 枫下论坛Say if I have some squares on the screen and I want to do a free draw,
when the line drawing crosses a square, I need to do something.

In the application, there is a OnMouseMove event, which is triggered
when the cursor moves from A to B.

what I am currently doing is,

1. when OnMouseMove event is triggered first time, I scanned all the squares to
see if the current moving point is in the square area, if yes, I
assume there is a line is "entering" the square

2. when OnMouseMove event is triggered again, I have know there is a
line entering a specific square, so this time I will check if the new
moving point is outside of the known square, if yes, I assume the line
has crossed the square

This idea works for most cases.

The only problem is, when the mouse moves too fast, from A and B, and
both points are outside a square, but actually the line can cross a
square, which means I was not aware there is an "entering" point.

So I wonder if anyone else can come up a better solution, thanks更多精彩文章及讨论,请光临枫下论坛 rolia.net
Report

Replies, comments and Discussions:

  • 工作学习 / 学科技术讨论 / 问一个算法问题,有什么方法可以知道一条线穿过一个正方形?
    本文发表在 rolia.net 枫下论坛Say if I have some squares on the screen and I want to do a free draw,
    when the line drawing crosses a square, I need to do something.

    In the application, there is a OnMouseMove event, which is triggered
    when the cursor moves from A to B.

    what I am currently doing is,

    1. when OnMouseMove event is triggered first time, I scanned all the squares to
    see if the current moving point is in the square area, if yes, I
    assume there is a line is "entering" the square

    2. when OnMouseMove event is triggered again, I have know there is a
    line entering a specific square, so this time I will check if the new
    moving point is outside of the known square, if yes, I assume the line
    has crossed the square

    This idea works for most cases.

    The only problem is, when the mouse moves too fast, from A and B, and
    both points are outside a square, but actually the line can cross a
    square, which means I was not aware there is an "entering" point.

    So I wonder if anyone else can come up a better solution, thanks更多精彩文章及讨论,请光临枫下论坛 rolia.net
    • 为什么你不对所有的square做个定义,在OnMouseMove判断是否符合定义,做标志确认,这样你运动的再快,最后检索标志,确认轨迹。
      • 能解释一下什么叫做个定义?
        • 如果你可以对每个square定义类和属性,你可以放一个数组标记在square中,每次事件触发将一个全局序列添加进去,要读取得时候全部拿出来就可以了。
          • 不是太明白你在讲什么。现在每一个 sqaure 是一个 class,有 left, top and width,整个screen都是 paint出来的。我想你说的是,每次 onmousemove 就把 current mouse pt 放到 square 里面,然后另外一个属性是bool Crossed?
            这个好像不是在回答如何更好的判断 line crossing a square, 只是一种实现方式而已吧

            就算每个 square 保留所有的点,还是需要一个方法判断啊

            你有看我原来实现的办法吗?
            • 方程
            • 不要用bool Crossed来判断,增加一个cross_seq,一旦判断sqaure crossed 发生, 讲这个cross_seq保存在crossed后的的sqaure的序列数组中,用它来做判断。
              • sorry, totally lost, what is this sequential array used for? the key is I need an efficient way to determine if it's crossed by two points. please see my another post
                • 如果你只要解决2,那不是只要每个sqaure中增加一个boolean变量就可以了,只记录true,不记录false.
                  • 嗯,我的问题就是不知道如何解决2,那就不能set 那个 boolean true :D
                    • 你不是每个move都会检查是否落在方块中,只要一点在就置方块类中的变量为true,为什么会不行?
                      • 因为如果 mouse move 太快,会发生 A 和 B 都在 square 的外面,如果你 drawline (A, B) 其实是 cross 的情况。我本来也没有想到,写出来之后自己试了几次,发现明明线过去了,但是却没有 trigger crossing event,就是因为太快了
                        • 虽然不明白为什么会错过mouse move 事件,但是如果你完成后,得出没有穿过的结论,再用下面小桥流水的方法确认,是否可行?
                          • 因为 mousemove is triggered by from A to B, not every point between A and B,所以每次 mousemove 发生,都是只有一个点而已,但这个点跟上个点的关系并不是刚好 +- 1 的关系。如果我想一边 draw 一边 trigger crossing event,用算法来算每条线会变得很慢
                            因为每一个 frame (mousemove triggered) 都需要走一个 nested loop

                            或者我应该需要用一个新线程来算才行……

                            这个其实想起来很简单,操作起来却很多小麻烦
                            • 明白了,那最后用线性公式判断,我觉得是可行的
    • 想当年做master论文研究过computational geometry. Refresh了一下memory. 一条直线可以用aX+bY=c来表示. 所有满足aX+bY<c的点(X,Y)都在直线的一侧, 而>c的在另一侧. 你把你的直线用aX+bY=c表示出来, 然后测一下正方型的四个顶点是不是都在直线的一侧就可以了. 如果你是线段
      而不是直线, 那就麻烦一些. 你得测试你的线段和正方形的每条边是否交叉.

      测试AB和CD是否交叉的办法:
      1. 测试C和D是否在AB的两侧
      2. 测试A和B是否在CD的两侧
      both true, 那么有交叉.
      • 不必那么麻烦的,每次 mousemove 会触发得到一个 point,放到一个 list, 然后每两点组成一个 height =1 的 rectangle,看看是否 intersect with square 就可以了。我的问题的关键是:mousemove 是从 A 到 B,AB 可以看成是一条直线,总共3种情况
        1,AB 从 square 外面过,不 cross
        2,AB 两点分别在 square 外面,但是线穿过
        3,AB 任何一点在外面,其中一点在里面

        2,3需要看作 crossing succeed

        我之前用的方法是,当有一点发现在里面,就记录 square id;下一点如果不在那个 square 里面,我就看作这条线出去了。可是这样只能解决 3 ,不能解决 2

        我知道你说的,用直线方程算 4个点是否4个都做同一边,否则的话就是穿过。可这样效率太低了,我必须用一个 nested loop,外面是遍历所有记录的点,里面是所有的 square
        • 对于2, 除了用直线方程算, 我目前想不出更好的办法.
    • 觉得第一个点应该在mousedown之类的
      • 有放,从 mousedown 开始就记录每一个点,每次 mouseover trigger 就检查最后那个记录,如果不一样就放进去。关键是如果两个点都不在 square 里面,我那个方法是不行的