Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!elroy!cit-vax!cit-vlsi!flaig
From: flaig@cit-vlsi.Caltech.Edu (Charles M. Flaig)
Newsgroups: comp.graphics
Subject: Re: polygon enclosing point
Message-ID: <6196@cit-vax.Caltech.Edu>
Date: 19 Apr 88 22:33:28 GMT
References: <615@ubu.warwick.UUCP>
Sender: news@cit-vax.Caltech.Edu
Reply-To: flaig@cit-vlsi.UUCP (Charles M. Flaig)
Distribution: comp.graphics
Organization: California Institute of Technology
Lines: 32

In article <615@ubu.warwick.UUCP> pssw@diamond.UUCP (P S Swanson) writes:
>I am writing an asteroids game, and need an algorithm to say whether a single
>point is enclosed by, or lies on the perimeter of a closed polygon, defined by
>an unspecified number of line segments.  Any offers ?

Whimper....  I assume you don't follow this group regularly if you are asking
this question.  It has been covered *repeatedly* and is well past the satura-
tion point.  Does your site really flush old articles that quickly?

Some very good references and suggestions were repeatedly posted.  If you
no longer have them at your site, you can try asking if anyone in your area
saved them or knows of any references.  I wouldn't touch this question with
a 10-foot pole (and hope no one else does, either...).

>In addition, is there a very simple routine I have overlooked for finding
>whether two line segments intersect.  Mine is not too bad, but I feel sure
>there must be a blatantly obvious solution I have missed.

This is probably in any elementary computer graphics text (page 4 in mine).
Using the the slope-intercept line equation (b=y-mx) we get an intercept at
y=(b2-b1)/(m1-m2) and x=(b2m1-b1m2)/(m1-m2) if one exists.  Then check if
this point is within the boundaries of the line segments.  Using the general
line equation (rx+sy+t=0) we get an intercept at x=(s1t2-s2t1)/(s2r1-s1r2)
and y=(t1r2-t2r1)/(s2r1-s1r2).

I take no responsibility for typos, and disclaim any knowledge of this response.

______________________________________________________________________________
  ___   ,               ,                                           ,;,;;;,
 /   Y /|              /|              Charles Flaig                ;/@-@\;
|      |/     __, ,__  |/              flaig@csvax.caltech.edu       | ^ |
|      /^\   /  | | |  /  /\  /\                                      \=/ 
 \____/|  \_/|_/\_/ \_/ \_\/_/_/_/     "What, you think they PAY me for this?"