Solution to Perimeter Problem

[Gregory S Miller]

Sci. Comp. Ctr., College of Marin, Kentfield CA
Science Computer Center, COM, Kentfield CA
College of Marin; SCC, Kentfield CA
Keywords: 

You may recall I posted a problem of this form:

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

Thanks for all the emails. I thought of this solution shortly after I
posted the original question.  It is somewhat simular to those emailed
to me.  Thanks for the book recomendations - I will get them in any
case!
    
For each vector, produce the corresponding rectangle (ie. use the end/
start points and width).  Put the resulting lines which consist of the
new calculated start and end points into a list (or file or whatever).

Now read in the list and sort all lines by the y coordinate (keep duplicates).
Take the y sorted list and sub sort each y coordinate by x keeping
any duplicates. 

Now for each y coordinate, choose the first and last entry.  I mean,
since the y coordinate is sorted on x, the first entry will be that y 
coordinate whose x coordinate was less that all others with the same y;
the last will contain the largest x coordinate for that y.   

It then is the x with the largest and least magnitude for each y that we
want to keep.  Call these points the output points.  Now it is a matter of 
connecting the output by lines (details).

The resulting lines should give the desired perimeter.  I have been out of
the state on business for the week and therefore have not had time to
actually code the solution.  I suspect there will be some special cases that 
I have not considered :). 

Anyways - that`s what I think.

BTW - this type of problem arises when one wishes to find the correct
negative image of a PCB when given the positive image in the form of
a gerber (photo plot) file.  Anyone familiar with these files will under-
stand that it is more difficult to FIND those fill areas (ie to seperate
the fill areas from just regular draws and flashes) than to find the
actual perimeter.  That brings me to my last question:

	Can anyone reccomend a book of image matching/shaping finding?

Once again, thanks a lot.

-------------------------------------------------------------------------
 Instant Board Circuits   | This space available for lease.
                          | Discount/Commerical rates.  Apply now.
 G. Shane Miller          |----------------------------------------------
 415-883-1717 (voice)     | miller at unicom.UUCP ??-> Use "R"eply - right!
-------------------------------------------------------------------------