Geometry puzzler

[Robert Amesz]

Paul Winkler wrote:

> [snip]
>
>There are two basic but important things I can't figure out how to do:
>
>1) Given any polygon, how can I test whether an arbitrary point lies
>   inside that polygon?

I can see why you have trouble with this one: topologically there is no 
inside or outside, just two different sides. If you have a point on one 
side you can check if another point is on the same side by counting the 
number of vertices the line segment connecting both points crosses. If 
it's even or zero, the points are on the same side, if it's odd they're 
on different sides. Of course, this means you'll have to know how to 
solve problem (2) first. Note that you'll get unexpected results if any 
of the vertices of the polygon intersect.

It's not that hard to find a point which is guaranteed to be outside 
the polygon in the usual sense of the word: first make a bounding box 
for the polygon (i.e. the smallest possible rectangle in which all the 
polygon's points lie) and choose a point outside that box. For general 
work with polygonal regions you might want to precalculate a bounding 
box.


>2) Given two line segments, how can I find the coordinates of their
>   intersection, if there is one? (easy for right angles, but I will
>   often NOT have right angles.)

That's not hard. First, make the equations (i.e. a x + b x = c) for the 
lines on which the line segments lie, and find the intersection point, 
if any. I assume you know how to do simultaneous linear equations, 
otherwise both steps will be rather difficult.

Once you find a point of intersection, you'll just have to see if the 
point lies in the two line segments bounding boxes. If it does, the 
point must be on both line segments. (Note however that there's a 
special case when the intersection of two line segments is a line 
segment rather than a point!)

If you expect the intersection point doesn't exist most of the time, 
it's probably more efficient to construct the intersection of the two 
bounding boxes first, and only proceed if that intersection is 
nonempty. (You can re-use that intersection in the final step later, so 
the extra effort isn't a total loss.)

Even more optimalisations are possible if you recognize certain 
pathological special cases early on, e.g. if one of the lines runs 
parallel to the y-axis. 


>I think if I knew how to do those two things, I could work out how to
>effectively manage and use an allowable drawing zone. For any line of
>text I could find the edges where it runs out of the allowed zone.
>Then whenever I added one of my graphic elements to the page, I could
>draw a polygon around it and subtract that space from the allowed
>zone.
>
>So my real problem, which I think I could solve given 1 and 2 above,
>is to combine such polygons in various ways.
>
>I need two functions or methods so that:
>
>bite(poly1, poly2) returns a new polygon which looks like poly1 with
>   the area encompassed by poly2 removed from it.
>
>union(poly1, poly2) returns a new polygon which looks like poly1 with
>   the area encompassed by poly2 added to it.

Oddly enough, those two functions are in fact identical. It once again 
depends on what you define as being inside the polygon or outside it.


>Examples in ugly ASCII art - two simple intersecting polygons.

Ugly is the word, I'm afraid. Did you use a fixed-pitched font for 
those?

[snip]

>Of course there are many different ways polygons can intersect,
>and I can't think of a solution for all cases. I don't even know 
>what to do when one polygon is entirely inside the other.
>(obvious for union, non-obvious for bite!)

Regions with holes in them are topologically different from continous 
ones, so you can't really represent those regions by single polygons. 
You could cheat a little by connecting the hole to the rest of the 
region by two overlapping vertices, but that would probably be more 
trouble than it's worth and might interfere with other algorithms later 
on.

Polygons which intersect can be merged, of course, but because a vertex 
of one polygon can intersect multiple vertices of the other this is not 
as eausy as one might think. Also, some vertices may in fact overlap 
partly or fully, making the calculation a bit more, hmmm, interesting.

BTW, Win32 already has an API to work with regions (polygonal and 
otherwise), you might wish to study that.


HTH (if only just a little),
Robert Amesz