Xref: utzoo comp.graphics:1793 comp.sys.ibm.pc:12400
Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!hao!husc6!ut-sally!im4u!milano!geza!begeman
From: begeman@geza.SW.MCC.COM (Michael Begeman)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <210@geza.SW.MCC.COM>
Date: 25 Feb 88 15:22:38 GMT
References: <971@ut-emx.UUCP>
Organization: MCC, Austin, TX
Lines: 39
Keywords: READ THIS ONLY IF YOUR IQ >>125
Summary: That's an easy one.

In article <971@ut-emx.UUCP>, jezebel@ut-emx.UUCP (Jim @ MAC@/) writes:
> 
> Have a boundary defined on the screen. Boundary is composed of points
> joined by lines... Now some random points are generated and I want to check
> if a given point is within or outside the existing boundary..

This is a simple variation of the "convex hull" problem.  The C-H problem
involves finding, for a set of points, that subset which when connected
by line segments encloses the remaining points (you can think of this as
playing connect-the-dot around the outer edge).

In the convex-hull problem, the question takes the form: Given a new point,
does it change the convex hull?  The result if FALSE if it lies within the
existing convex hull (what you described as the boundary), TRUE if outside.

I'll refer you to the following reference:

	Kant, Elaine and Newell, Allen.  Problem Solving Techniques for
	the Design of Algorithms.  Information Processing & Management,
	Vol 20, No. 1-2, pp. 97-118, 1984.

This was reprinted in the second edition of an IEEE tutorial entitled
Human Factors in Software Development edited by Bill Curtis.  IEEE
Computer Society Order Number 577.

The article describes the ways different designers approached this
problem, and contains several tenable solutions.

P.S.  Sorry, but I can't claim the IQ >> 125 prize.  I'd only have
      earned that had I worked on the problem for weeks before discovering
      that it was already solved!

-------
	Of all the things I've lost, I miss my mind the most.

  +----------------------------------------------------------------+
  | Michael L. Begeman, MCC, 9390 Research Blvd., Austin TX 78759  | 
  |                 (512)338-3308     begeman@mcc.com              | 
  |  {gatech,harvard,pyramid,seismo}!ut-sally!im4u!milano!begeman  |
  +----------------------------------------------------------------+