Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu!stanford.edu!neon.Stanford.EDU!flamingo.Stanford.EDU!espie
From: espie@flamingo.Stanford.EDU (Marc Espie)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Clicking on irregular shapes?
Message-ID: <1991Apr9.004012.26446@neon.Stanford.EDU>
Date: 9 Apr 91 00:40:12 GMT
References: <1991Apr05.104141.2118@cs.ruu.nl> <27867@neptune.inf.ethz.ch> <1079@cbmger.UUCP>
Sender: news@neon.Stanford.EDU (USENET News System)
Organization: LIENS, ENS, 45 rue d'Ulm, Paris (France)
Lines: 54

In article <1079@cbmger.UUCP> peterk@cbmger.UUCP (Peter Kittel GERMANY) writes:
>(Sorry, deleted the originator's name.)
>> [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
>>     /      \/ ___\
>>    /_______  /
>>            \/
>
>I always have moot feelings with such analytical algorithms. Often
>you have to compare for equality of real numbers, which is normally
>a NO-NO. You would have to convert coordinates to integers only to
>do this algorithm on them.
>
>Look for another example at this shape, would it be
>processed correctly?
>      /\
>     /  \       /\
>    / O  \_____/  \
>   /_______________\
>
>The O is thought to be on the same y coordinate as the horiz. line.
>
This is an old problem, well-known by people working on the subject.
It is solvable generally. There are actually two cases to consider.

1) You're really working with integer coordinates. In that case, don't
switch to float. Take an horizontal line passing through the end point,
and see which lines it crosses. Don't forget every equality cases,
and every subcase. That works, because these special cases are determined
by integer comparisons only.

2) You're working with floating-point coordinates. You can either reduce
everything to integer coordinates, in that case you will check the adjusted
point against the adjusted shape, and use the previous algorithm. As
Peter Kittel very rightly said, don't even think of mixing the two algorithms,
you will be fixing subtle bugs three months later.
Or... you can work with floating-point coordinates. Set up a margin of error,
and choose a line passing through your point. Check for special cases using
your margin: do you get within your margin of passing through a vertex ?
Are you near a line which has nearly the same orientation as the line you've
chosen ? If a problem arises, well, choose another line. It will eventually
work (pretty soon, usually), or your margin is too big for the kind of shape
you're drawing (ill-dimensionned problem). 

Both ideas are easy to implement if you're careful of what you're doing.
For further references, check any textbook in computational geometry
(Preparata, Edelsbrunner...).
--
	Marc Espie (espie@flamingo.stanford.edu)