Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!watmath!clyde!rutgers!gatech!udel!rochester!pt!andrew.cmu.edu!sohan+ From: sohan+@andrew.cmu.edu.UUCP Newsgroups: comp.graphics Subject: Re: Point inside of polygon revisited... Message-ID: Date: Tue, 16-Jun-87 21:38:46 EDT Article-I.D.: andrew.QUpTAay00UoIhwo0Xm Posted: Tue Jun 16 21:38:46 1987 Date-Received: Fri, 19-Jun-87 01:24:40 EDT Organization: Carnegie Mellon University Lines: 12 ID ; Wed, 17 Jun 87 01:29:52 edt ID ; Tue, 16 Jun 87 21:46:06 edt ID ; Tue, 16 Jun 87 21:38:48 edt Approved: l.2535.0.0>; Tue, 16 Jun 87 21:46:06 edt ID ; Tue, 16 Jun 87 21:38:48 edt In-Reply-To: <948@elrond.CalComp.COM> A very non-rigorous outline of a method I am using for a particular application is: Given Polygon p[1..n], point being checked P Take a known external point E; compute the cross-product of (P->pi) and (P->E) for i in [1..n]. Whenever cross-products change sign (crosses 0 - break ties consistently), check if pi-1->pi cuts P->E. If the number of such intersections is even, then external else internal. This is pretty painless and correct (I think :-)) for all kinds of polygons. Hope this helps Sohan