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