Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!usc!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: <27867@neptune.inf.ethz.ch>
Date: 5 Apr 91 15:31:24 GMT
References: <1991Apr05.104141.2118@cs.ruu.nl>
Sender: news@neptune.inf.ethz.ch
Reply-To: umueller@iiic.ethz.ch (Urban Dominik Mueller)
Organization: Departement Informatik, ETH, Zurich
Lines: 44

ptavoly@cs.ruu.nl (Peter Tavoly) writes:

>umueller@iiic.ethz.ch (Urban Dominik Mueller) writes:
>> [an algorithm for determining whether a point's inside a polygon]

>I am currently writing a game that needs this (and probably will never be
>finished :^). Now what about this:
>        /\
>       /  \    /\
>      / O  \  /  \                                                   X
>     /      \/ ___\
>    /_______  /
>            \/
>where you draw the horizontal line from the 'O' to the 'X', now, it intersects
>an odd number of boundaries, yet it is OUTside the shape. Or am I mistaking
>something here?

Am *I* mistaking *you*? The way I see it, the 'O' is clearly inside, as the
algorithm states. Or are you talking about the 'X'? 'X' must be a point that's
sure to be outside, but 'O' is the point in question. The polygon can be as
complex as you want.

>       /\
>      /  \    /
>     / O  \  /                                                       X
>    /      \/
>   /_______/
>Here, an even number of boundaries is crossed. (The second intersection is a
>single line)

The polygon must be closed for this algorithm to work. To make it closed,
you have to draw a second line over that single line already drawn, there-
fore you get a double interection at that line, so the total number of inter-
sections is odd again -> inside.

BTW I just discovered that I explained the problem with the imaginary line
going through a vertex exactly the wrong way round. Count the intersection
only if it's *no* local maximum or minimun, otherwise don't (or do it twice).
My apologies if that caused problems to anyone.
                                          __
 |          Urban Mueller         |      / / |    Urban Mueller    |
 | INTERNET:umueller@iiic.ethz.ch | __  / /  |    Schulhausstr. 83 |
 | FIDONET: 2:302/906 (AUGL)      | \ \/ /   | CH-6312 Steinhausen |
 | "Don't tell my employer"       |  \__/    |    SWITZERLAND      |