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