Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!zephyr.ens.tek.com!tektronix!reed!busker!p8.f14.n105.z1.FIDONET.ORG!Howard.Spindel
From: Howard.Spindel@p8.f14.n105.z1.FIDONET.ORG (Howard Spindel)
Newsgroups: comp.lang.c
Subject: Re: Need help with finding perimeters of bounded areas
Message-ID: <1060.25382BFA@busker.FIDONET.ORG>
Date: 14 Oct 89 18:16:30 GMT
Sender: ufgate@busker.FIDONET.ORG (newsout1.26)
Organization: FidoNet node 1:105/14.8 - Busker's Boneyard, Portland OR
Lines: 57

> From: miller@unicom.UUCP (Gregory S Miller)
> Date: 12 Oct 89 02:37:36 GMT
> Organization: Science Computer Center, College of Marin,
> Kentfield CA
> Message-ID: <135@unicom.UUCP>
> Newsgroups: comp.lang.c,comp.lang.lisp,comp.ai
>
>
>
> 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).
>
You don't say whether the area has any concavities or not.  If not,
the following brute force idea may work - I didn't spend a whole lot
of time thinking it through.
Make 4 lists.  List 1 is the minimum X coordinate seen for a given Y,
List 2 is the maximum X coordinate for a given Y, List 3 is the
minimum Y coordinate seen for a given X, List 4 is the maximum Y
coordinate seen for a given X.  Your arrays will have to be large
enough to hold an entry for each possible X and Y intercept.
Scan convert each line.  For each point encountered while scan
converting compare against the minima/maxima saved in the tables
and replace if new minima/maxima are found.
When all lines have been scan converted the lists should contain
the coordinates of each point along the edge of the desired area.
 
Eschew Sesquipedalian Obfuscation!
Usenet:     Howard.Spindel@p8.f14.n105.z1.FIDONET.ORG
Fidonet:    1:105/14.8


--  
Howard Spindel - via FidoNet node 1:105/14
	    UUCP: ...!{uunet!oresoft, tektronix!reed}!busker!14.8!Howard.Spindel
	    ARPA: Howard.Spindel@p8.f14.n105.z1.FIDONET.ORG