[comp.lang.lisp] Need help with finding perimeters of bounded areas

miller@unicom.UUCP (Gregory S Miller) (10/12/89)

Consider an area A on an euclidean plane surface.  Inside A 
are an arbitrary number of lines that "fill out" A.  That is,
A is defined not by a perimeter, but rather as a filled object (
negative versus positive images...).

Now each line has a diameter D(i) where i is an subscript telling 
which line we`re referring.  It is perfectly reasonable that the lines
may overlap.  Since they overlap, one could use a lot of lines with
small diameters or a smaller number with larger diameters and still
produce the same area A.

Problem: Given the area A, find the perimeter - eliminate all lines
	 inside A and leave just the outline.  A is "given" by a
	 list of vectors with a diameter (ie. start/end point with
	 diameter). 

	 Just in case it was not already clear, the number, location
	 and diameter (D(i)) of each line is arbitrary so long as
	 the area A is filled out.

I do not know quite where to start on this problem.  I`ve never
run across "standard algorithms" which would be suited to this problem.

Ideas, text references, or the like would be helpful.
Thanks.

dhw@itivax.iti.org (David H. West) (10/13/89)

In article <135@unicom.UUCP> miller@unicom.UUCP (Gregory S Miller) writes:
>Consider an area A on an euclidean plane surface.  Inside A 
>are an arbitrary number of lines that "fill out" A.  That is,
>A is defined not by a perimeter, but rather as a filled object (
>negative versus positive images...).

>Problem: Given the area A, find the perimeter - eliminate all lines
>	 inside A and leave just the outline.  A is "given" by a
>	 list of vectors with a diameter (ie. start/end point with
>	 diameter). 

I imagine one could simplify one of the perimeter-marching convex hull
algorithms fairly straightforwardly to do this. See e.g.
Preparata and Shamos, Computational Geometry, Springer, 1985.

-David West        dhw@itivax.iti.org