Am I inside?

Am I inside?

Post by Steven M. Harringt » Wed, 18 Nov 1998 04:00:00



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

 
 
 

Am I inside?

Post by Aaron and Hifum » Wed, 18 Nov 1998 04:00:00



> 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


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

*wink*

Aaron

 
 
 

Am I inside?

Post by Charles B. Cransto » Wed, 18 Nov 1998 04:00:00


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?

Dunno about fastest.  Each of the four lines that is a boundary
of the quadrilateral splits the plane into two half planes.
There is a "right side" and a "wrong side" of each one.
If the point is inside the quadrilateral it must be on
the "right side" of each of the four lines.

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

 
 
 

Am I inside?

Post by Paul Hughe » Thu, 19 Nov 1998 04:00:00



: 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

 
 
 

Am I inside?

Post by Charles B. Cransto » Fri, 20 Nov 1998 04:00:00


Yow!  The algorithm I gave for insidedness testing only works if:

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

 
 
 

Am I inside?

Post by msis.. » Sat, 21 Nov 1998 04:00:00


On Thu, 19 Nov 1998 11:40:21 -0500, "Charles B. Cranston"


>Yow!  The algorithm I gave for insidedness testing only works if:

Relax...

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

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

From his original post:

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

A "regular quadrilateral" excludes #1 and requires #2.
 
 
 

Am I inside?

Post by Steven M. Harringt » Sat, 21 Nov 1998 04:00:00



>On Thu, 19 Nov 1998 11:40:21 -0500, "Charles B. Cranston"

>>Yow!  The algorithm I gave for insidedness testing only works if:
>Relax...
>>1. The quadrilateral is non-self-intersecting

>>2. The quadrilateral is convex (i.e. non-concave)
>From his original post:
>>        Given a regular quadrilateral defined by the 4 vertices,
>A "regular quadrilateral" excludes #1 and requires #2.

Very true.  Unfortunatly, as I continued to examine the problem it
became clear that I could not ensure #2 only #1.

Sorry for the confusion.

--
Steve

 
 
 

Am I inside?

Post by James Youngm » Sat, 21 Nov 1998 04:00:00



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?

Look up "pick correlation" in a computer graphics textbook.

--

 
 
 

Am I inside?

Post by Miguel Cr » Sun, 22 Nov 1998 04:00:00



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.

I think it would be a little faster to just answer "no" as soon as you hear someone
start to ask the question. Surely there must be some overhead in guessing.

miguel

 
 
 

Am I inside?

Post by Gary Huckaba » Tue, 24 Nov 1998 04:00:00



> WLOG you can walk around the polygon in either direction
> starting from any point, looking for monotonicity in

Compute the winding number.  It doesn't matter if the figure is
convex or not and it's extremely efficient.

gary

 
 
 

Am I inside?

Post by Steven M. Harringt » Tue, 24 Nov 1998 04:00:00




>> WLOG you can walk around the polygon in either direction
>> starting from any point, looking for monotonicity in
>Compute the winding number.  It doesn't matter if the figure is
>convex or not and it's extremely efficient.

And how is that done?
--
Steve

 
 
 

1. HELP! I am trapped inside of XDM!!!

Hi,

    I am inside of xdm right now. I can't get out. Every time I try to
kill the processes, XDM locks up which forces me to hard re-boot....you
can imagine my dismay when I have to do that. So while I am trpped here
I have searched through the XDM MAN pages. I noticed under "controlling
the server" that I can kill the XDM process. Maybe I am misunderstanding
something here but if someone can come to my rescue I'd owe them my
freedom...thanks.

--
  ------------------------------------------------------------------
  Robert A. Maiale

  Key fingerprint =  9E F2 80 36 B5 60 AE DC  83 B2 5A FD 38 8F 4B 04
  -------------------------------------------------------------------

2. DSL/router/firewalls

3. Am I inside - an answer.c

4. Heeeellllpp meeeee!! I can't get X 3.2 to work no matter what I do!!!

5. How can I tell whether I am logging in on console inside .login?

6. Redhat or Mandrake? Which is better?

7. "Linux Inside": Spoof of Intel Inside

8. Q: How to make a boot disk for installation

9. Formattet output inside variable / line brak inside variable

10. FTP client inside linux firewall communicating with FTP server inside another linux firewall

11. This clone thing...am I stupid, or am I right?

12. I am with the following error, when i am running lilo...