miller@unicom.UUCP (Gregory S Miller) (10/22/89)
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@unicom.UUCP ??-> Use "R"eply - right! -------------------------------------------------------------------------