Very Computer

This question has nothing to do with linux other than that
is the OS I use.  The question is:

        Given a regular quadrilateral defined by the 4 vertices,
and
        Given a random point
question
        Is the point inside the quadrilateral?

What is the fastest way to answer this question?

Thanks
--
Steve

*wink*

Aaron

Quote:>         Given a regular quadrilateral defined by the 4 vertices,
> and
>         Given a random point
> question Is the point inside the quadrilateral?
> What is the fastest way to answer this question?

Each line can be characterized as a linear equation.
ax + by = c
if you plug in the x and y for the test point,
ax + by will be either >c, =c, or <c, where =c means the
point is on the line, >c is one side of it <c the other.

Now, the real problem is deciding what the "right side" is
and how to deal with problems like: the line might be horizontal
or vertical (probably turns into a or b being zero in the above) etc.

But it seems to me this might be as easy as about 8 multiplies...

--
Charles B. (Ben) Cranston

http://www.wam.umd.edu/~zben

: This question has nothing to do with linux other than that
: is the OS I use.  The question is:

:       Given a regular quadrilateral defined by the 4 vertices,
: and
:       Given a random point
: question
:       Is the point inside the quadrilateral?

: What is the fastest way to answer this question?

Let the vertices be A, B, C, D and the random point P.  Compute the
four vector cross products AP x BP, BP x CP, CP x DP, and DP x AP,
where AP is the vector difference between A and P, etc., and the cross
product in two dimensions is u x v = u1*v2 - u2*v1.  If all four
products have the same sign, P is inside the quadrilateral.  If you
can guarantee that the vertices are always listed in clockwise, or
counter-clockwise order, and the quadrilateral is convex, the sign
will always be postive or negative and you can test for that instead.
This is probably not the fastest possible method, but it should be
fast and simple enough for almost any reasonable application.

Paul Hughett

1. The quadrilateral is non-self-intersecting

2. The quadrilateral is convex (i.e. non-concave)

I think 1 is reasonable but 2 makes it a lot weaker.
You could always split the quad into two triangles,
which are GUARANTEED to be convex, then use the same
algorithm.  Be careful where you split it though.
For a quad there can be only one trio of vertices
where it is concave, you want the middle vertex to
be one of the endpoints of the splitting line segment.

WLOG you can walk around the polygon in either direction
starting from any point, looking for monotonicity in
the deflection angle.  If it is monotonic the figure is
convex, if it changes sign there is an adjacent concavity
but I cannot see any better way than walking the entire
polygon and summing the deflection angles to find out
which sense the polygon is -- if the total is a multiple
of +360 degrees it is one sense, -360 degrees the other.
If the sense turns out to be backwards you can walk the
other way or invert all your tests.

To find a point to characterize inside/outside for
each segment you should be able to use an average
point, that is, a point whose x coordinate is the
average of the x coordinates of the vertices and
whose y coordinate is the average of the y coordinates
of the vertices.

Testing for self intersection is probably a n^2
problem which means you'd have to make 4*3 = 12
tests.

My old computer graphics teacher (to whom I spoke about this)
suggests a heirarchical triangulation using the same kind of
sidedness tests that could test in log(n) time for large
numbers of vertices.  He also mentions an algorithm based
on the total angle swept by a line from the test point to
each of the vertices in turn.  This algorithm is attributed
to Randloph Franklin.

--
Charles B. (Ben) Cranston

http://www.wam.umd.edu/~zben

Quote:>1. The quadrilateral is non-self-intersecting

>2. The quadrilateral is convex (i.e. non-concave)

Quote:>    Given a regular quadrilateral defined by the 4 vertices,

Sorry for the confusion.

--
Steve

Quote:> This question has nothing to do with linux other than that
> is the OS I use.  The question is:

>    Given a regular quadrilateral defined by the 4 vertices,
> and
>    Given a random point
> question
>    Is the point inside the quadrilateral?

> What is the fastest way to answer this question?

--

Quote:>> This question has nothing to do with linux other than that
>> is the OS I use.  The question is:

>>         Given a regular quadrilateral defined by the 4 vertices,
>> and
>>         Given a random point
>> question
>>         Is the point inside the quadrilateral?

>> What is the fastest way to answer this question?

>The quickest way to answer the question is to just guess. Yes or no.
>Takes no time at all.

miguel

gary