# Geometry puzzler

Robert Amesz rcameszREMOVETHIS at dds.removethistoo.nl
Tue Nov 7 06:56:40 CET 2000

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

```