Path: news.mathworks.com!newsfeed-00.mathworks.com!nlpi057.nbdc.sbc.com!prodigy.net!news.glorb.com!postnews.google.com!b38g2000prf.googlegroups.com!not-for-mail
From: Rune Allnor <allnor@tele.ntnu.no>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Deciding which side a numerically generated line you are on
Date: Sat, 17 Jan 2009 02:54:28 -0800 (PST)
Organization: http://groups.google.com
Lines: 31
Message-ID: <6a95faa5-b673-4fa8-804d-dd9ae4da773d@b38g2000prf.googlegroups.com>
References: <gkr5ue$8b5$1@fred.mathworks.com>
NNTP-Posting-Host: 77.17.94.229
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1232189668 19778 127.0.0.1 (17 Jan 2009 10:54:28 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sat, 17 Jan 2009 10:54:28 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: b38g2000prf.googlegroups.com; posting-host=77.17.94.229; 
	posting-account=VAp5gAkAAAAmkCze5hvZtMeedpZWNthI
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET 
	CLR 2.0.50727; .NET CLR 3.0.04506.648; .NET CLR 3.5.21022),gzip(gfe),gzip(gfe)
Xref: news.mathworks.com comp.soft-sys.matlab:512198


On 17 Jan, 00:41, "Dale" <hazelREMOVETHISnu...@gmail.com> wrote:
> I am looking at a number of functions of two variables (say x and y), and=
 I am restricting my attention to x \in [-pi/2, pi/2] and y \in [-pi, pi]. =
=A0Call this set S \subset R^2. =A0The problem is such that I really only w=
ant to look at some of the data in this subset of the plane. =A0I numerical=
ly generate some boundary curves that separate feasible (x,y) coordinates f=
rom infeasible ones (by solving a system of two equations in two unknowns),=
 and I need to be able to decide if an arbitrary point in S is on one side =
or the other side of the numerically generated curve. =A0I have the points =
on the curve as a 2xn array, each column of which is a point (x,y) on the c=
urve. =A0

The terminology you use would suggest that this is a constrained
linear programming problem. There are well-known methods to solve
such problems, but they are a bit complicated to learn and
implement. Linear programming tecniques work in any dimension.

The 2D nature of your curves allows a different approach. You
could view this as a geometric problem. In this case you check
the signs of the vector cross products

c_n =3D a_n x b_n

where a_n is the vector from a point P1 on the line to the
point under test P, and b_n is a vector from the point P1
to another point P2 on the line. If all the lines are
directed, the signs of all the cross products c_n will
be the same if P lies inside a convex region bounded
by the lines.

Rune