Geometry puzzler
Gareth McCaughan
Gareth.McCaughan at pobox.com
Mon Nov 6 22:18:24 CET 2000
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
More information about the Python-list
mailing list