Geometry puzzler

[Gareth McCaughan]

Paul Winkler wrote:

[in summary: he wants to be able to test for "point inside
arbitrary polygon" and for "line segment intersects line segment",
in order to draw text that doesn't overlap other stuff on a page.]

1. AB and CD don't intersect if their bounding boxes don't.
   This obviously doesn't solve the problem completely, but
   you'll probably find that including this test is a win
   because it's quick and often lets you avoid the more
   complicated calculations.

2. AB and CD intersect iff AB intersects CD* and CD intersects AB*,
   where "*" means "continue past both endpoints, to infinity".
   AB intersects CD* iff A and B are on opposite sides of CD*,
   of course. And *that*'s true iff the signed areas of triangles
   CDA and CDB are opposite. ("Signed area" means that it matters
   whether you list the vertices clockwise or anticlockwise; the
   two answers have opposite sign.)

3. Twice the signed area of the triangle 0..(p,q)..(r,s) is
   ps-qr.

For point-inside-polygon, what others have said is correct:
you can do it by looking at the intersections of a ray going
out from the point to infinity with the polygon. Finding these
intersections may be painful if your polygon is very complicated
("painful" meaning "expensive" rather than "conceptually
difficult"). You'll probably find that bounding-box tests
can eliminate some of the pain.

If it's only text layout that you want to do, you may well
find it's better to do something a little different: divide
the screen/canvas/page/whatever into horizontal stripes and
work out which regions of each stripe are available. This will
require more computation when the polygons are being placed,
but less when the text is being laid out; my guess is that
this is a good tradeoff.

-- 
Gareth McCaughan  Gareth.McCaughan at pobox.com
sig under construc