Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!spool.mu.edu!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!cernvax!chx400!chx400!bernina!neptune!iiic.ethz.ch!umueller
From: umueller@iiic.ethz.ch (Urban Dominik Mueller)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Clicking on irregular shapes?
Message-ID: <27832@neptune.inf.ethz.ch>
Date: 4 Apr 91 00:05:12 GMT
Article-I.D.: neptune.27832
References: <1991Mar27.212214.6204@orfeo.radig.de> <2710@sirius.ucs.adelaide.edu.au> <20181@cbmvax.commodore.com> <1991Mar29.022042.14110@leland.Stanford.EDU> <1757.tnews@templar.actrix.gen.nz> <2151@pdxgate.UUCP> <NJ.91Mar30173951@truffula.Berkeley.EDU> <1991Ap <NJ.
Sender: news@neptune.inf.ethz.ch
Reply-To: umueller@iiic.ethz.ch (Urban Dominik Mueller)
Organization: Departement Informatik, ETH, Zurich
Lines: 15

There have already been many answers to this question, but none of them
complete.

The basic solution has been mentioned: Draw an imaginary line from the point
the user clicked on to a point in nowhereland, far away in any case. A hori-
zontal line would be best. Now count the number of times this line would
intersect with edges of the polygon. If that number is even, you're outside,
otherwise you're inside.
But that's not all of it. Assume your imaginary line passes exactly through
a vertex, which can easily happen. I that case, count it only as an inter-
section if that vertex is a local maximum or minimum.
The only problem left is the line intersection. I have no formula handy, but
it should not be too hard to intersect with a horizontal line.

  Urban Mueller,    umueller@iiic.ethz.ch