Geometry puzzler

[Paul Winkler]

I have a problem that's more geometry than python per se, but I need a
solution in python so I thought I'd ask here. This is for a
proprietary web application I'm developing, but I'd be happy to donate
this part of my code to the python community - probably in the form of
some example code for sping (formerly known as PIDDLE... see
sping.sourceforge.net) since that's what I'm using. I just don't know
enough geometry to work this one out on my own...

I need to draw text on a page without it overlapping with various
other graphic elements on the page. Problem is that those elements
could be anywhere, so I need a general solution. This would be useful
for vector-drawing and page layout applications in general.

One way I thought of is to keep track of one or more allowed drawing
zones on my canvas. These zones could be represented as polygons
defined by a sequence of (x,y) coordinate tuples. We can find the
perimeter of such a polygon by drawing line segments between each
coordinate pair in the sequence, and then one line from the last
coordinate pair to the first to close the polygon. So far so good.
So:

( (0,0), (100,0), (100,100), (0, 100) )

...would be a square.


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?

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.)


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.


Examples in ugly ASCII art - two simple intersecting polygons.


1 represents poly1, 2 represents poly2.


 1111111111111111111111111
 1    	       	       	 1
  1 		   22222+222222
  1		   2   	1      2
   1 		   2   1        2
   1 		   2   1         2
    1 		   222+222222222222
    1 	       	      1
     1	       	     1
     11111111111111111


union(1,2) would look like:



 1111111111111111111111111
 1		       	 1
  1 		        +222222
  1		       	       2
   1 		                2
   1		                 2
    1 		      +222222222222
    1 	       	      1
     1	       	     1
     11111111111111111


bite(1,2) would look like:

 1111111111111111111111111
 1		       	 1
  1 		   22222+
  1		   2
   1 		   2
   1		   2
    1 		   222+
    1 	       	      1
     1	       	     1
     11111111111111111



 
 Now that I've got this 
  shape defined I can 
  draw my text inside
   it nicely just
   by inserting
    line breaks anytime
    I'm about to go  
     out of bounds  
     for this line.

 
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!)

-- 
.................    paul winkler    ..................
slinkP arts:   music, sound, illustration, design, etc.
           web page:  http://www.slinkp.com
      A member of ARMS:   http://www.reacharms.com