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

Text File | 1992-08-27 | 1.9 KB | 54 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]>
Date: Thu, 27 Aug 1992 19:39:02 GMT
Lines: 41

In article <[e-mail]>, [e-mail] (Mark Schnitzius) writes:
|> [e-mail] (Mark Stockley) writes:
|>
|> >I am in need of an algorithm to compute whether or not a given
|> >point exists within or without a polygon. Any help or pointers to
|> >where to look would be much appreciated.
|>
|> If I remember right the trick is to extend a line from the point
|> infinitely in any direction (say, up).  Count how many of the
|> polygon's edges this line passes through.  If it passes through
|> an even number of polygon edges (including zero) the point is
|> outside of the polygon.  An odd number indicates the point is
|> inside the polygon.

Correct, but a word of caution should be said.
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.

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