Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!alchemy!ptavoly
From: ptavoly@cs.ruu.nl (Peter Tavoly)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Clicking on irregular shapes?
Message-ID: <1991Apr05.104141.2118@cs.ruu.nl>
Date: 5 Apr 91 10:41:41 GMT
Organization: Utrecht University, Dept. of Computer Science
Lines: 53


umueller@iiic.ethz.ch (Urban Dominik Mueller) writes:

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

I am currently writing a game that needs this (and probably will never be
finished :^). Now what about this:

        /\
       /  \    /\
      / O  \  /  \                                                   X
     /      \/ ___\
    /_______  /
            \/

(this is a totally random shape, created by a misty mind :)

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? In other words this even/odd thing does not work since you
can always make a shape that has a 'too irregular' shape. Or imagine a
shape like this:

       /\
      /  \    /
     / O  \  /                                                       X
    /      \/
   /_______/

Here, an even number of boundaries is crossed. (The second intersection is a
single line)

 -Thomas Tavoly.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  "Help, I've been attacked by a Prime terminal at 1200 baud!!!"  -Thomas T.
  
  Did you know that IBM have a secret factory with an infinite number of
  monkeys? That's how they invented MS-DOS...      -ptavoly@praxis.cs.ruu.nl
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~