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

Text File | 1992-08-31 | 1.6 KB | 48 lines

Newsgroups: comp.programming
Path: sparky!uunet!s5!is1.is.morgan.com!is.morgan.com!berlin
From: [e-mail] (Alexander Berlin)
Subject: Re: Deciding point-in-polygon: A new idea
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: chico
Organization: Morgan Stanley - IS
References: <[e-mail]> <[e-mail]>
Date: Mon, 31 Aug 1992 19:33:24 GMT
Lines: 35

In article <[e-mail]>, [e-mail] (Mark Schnitzius) writes:
|> Confession:  I knew it wouldn't work when I posted it, but I wanted to
|> see if anyone could come up with a way to make it work.  Since then, I
|> came to the realization that this idea WILL work if you add the stipulation
|> that the point must be added in such a way that it will not make any new
|> line crossings, and I believe it is always possible to do so.  Like you
|> said, the only change in sum will depend on (x1,y1), (x2,y2), and (x,y),
|> so after you find the place to add the point (which is where the complex-
|> ity comes in), you only need to check to see if
|>
|>   (x1*y2-x2*y1) > (x1*y-x*y1)+(x*y2-x2*y)
|>
|> If this inequality is true, the point is inside the polygon.

Wrong again. There are some cases when it is impossible to avoid new
line crossings. Example? Here goes:

    A ______ D
      \    /
       \  /
        \/ * X
        /\
       /  \
      /    \
   C /------\ B

And this is not the worst case at all.

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