NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/programm/2524

Text File | 1992-08-29 | 2.8 KB | 67 lines

Newsgroups: comp.programming
Path: sparky!uunet!s5!is1.is.morgan.com!is.morgan.com!berlin
From: [e-mail] (Alexander Berlin)
Subject: Re: How to decide if a point is inside a polygon?
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: chico
Organization: Morgan Stanley - IS
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
Date: Fri, 28 Aug 1992 17:42:03 GMT
Lines: 54

In article <[e-mail]>, [e-mail] (Mark Schnitzius) writes:
|> [e-mail] (Alexander Berlin) writes:
|>
|> >When drawind the line in any direction, you want to avoid
|> >crossing corners of the polygon. So, make sure no one of the given points
|> >(that make polygon) belongs to the line.
|>
|> >        A           B
|> >        .___________.
|> >         \         /
|> >          \  Y.   /
|> >           \  |  /
|> >    X       \ | /
|> >    .________\|/___________________
|> >              |
|> >              | C
|> >              |
|>
|> >In the above example X is outside triangle ABC, Y is inside it. Their lines
|> >exactly the same crossings whith the edge. So instead of coming up with
|> >additional complicated rules just make sure you don't hit the corners.
|>
|> Well, one solution to this problem is this: consider each vertice of the
|> polygon as belonging to only _one_ of the line segments it is connected to.
|> So in the above example,  only consider point C to be on the line segment
|> BC and not on AC.  Then if the line you're drawing goes through point C,
|> it is only considered to have gone through line segment BC and not AC.
|> This simple fix should clear up any problems.

No, it doesn't. I didn't say that the line drawn from point X has one or two
crossings. My point is that X-line and Y-line have the same number of crossings
(be it 1 or 2) while X is outside and Y is inside. The fix you suggest doesn't
distinguish X- and Y- cases in my example.
The rule that would work is to check if AC and CB segments are on the same
side of the line (2 or 0 crossings, case X) or on the different sides
(1 crossing, case Y). But I think it is much better to just avoid these
confusing cases. It can be even more complex if a direction you select for
the line makes it co-linear with one of the segments. Something like this:

             B                 C
      X ._______________________________________________________
            /                  \
           /                    \
          /                      \
         /________________________\
        A                          D

|>
|> Mark Schnitzius
|> [e-mail]
|> University of Central Florida
---
Alex Berlin
[e-mail]