Berkeley CSUA MOTD:Entry 25569
Berkeley CSUA MOTD
 
WIKI | FAQ | Tech FAQ
http://csua.com/feed/
2025/04/17 [General] UID:1000 Activity:popular
4/17    

2002/8/15-16 [Uncategorized] UID:25569 Activity:high
8/15    Given a line with xy coordinates, how can you tell if that line
        will overlap a rectangle if both xy points fall outside the
        rectangle?
        \_ google "method of separating axes" -pld
        \_ Easy anwer: check if the line interests any of the rectangle's lines
           \_is that the only solution? seems like an inefficient method.
             \_ Maybe compute dot product of line and two perdendicular sides
                of the rectangle and depending on that call some particular
                case of the solver? Or maybe just go with the assumption
                if the line intersects any *two* edges then it goes inside,
                so basically solving the line simultanously against each side.
                there clerely is some optimization that can be done.
                \_ What is the underlying problem?
        \_ Turn each edge of the rectangle into an infinite line,
           and you cut the plane into pieces numbered 1-9.  You can figure
           out the easy case where the target line is exclusively on one
           side of an edge.  The choose an edge and figure out if the
           target line is inside or outside the edge... parametrically it
           amounts to about 4 multiplications and 8 additions, and you can
           improve on that.  Ok, motd god just told me my lock time was up,
           so take 184.
           \_ Try me -t 1200
        \_ Draw on graph paper and see.
        \_ Is it a rectangle or square?  Is it aligned with the coordinate axes
           or not?