Omnimaga

General Discussion => Other Discussions => Math and Science => Topic started by: Deep Toaster on June 21, 2011, 12:41:46 am

Title: Finding out which side of a line a point is on
Post by: Deep Toaster on June 21, 2011, 12:41:46 am
Here's a question that'll help me tremendously in my next project (hopefully contest entry):

Given a line (http://www.texify.com/img/%5Cnormalsize%5C%21%5Cvec%7BRS%7D.gif), what's the simplest (fastest, least intensive) way to tell if a point (http://www.texify.com/img/%5Cnormalsize%5C%21P.gif) is "above" or "below" it?

Thanks in advance for any help.

EDIT: What I actually want to do is test if a point starts above a line and goes below, in case anyone has a simpler way to test that. Any solution has to be specific in that the point must start on one side and end in the other, not the other way around.
Title: Re: Finding out which side of a line a point is on
Post by: Quigibo on June 21, 2011, 12:48:06 am
Its very simple.  If you have a point R with vector RS, you can determine if point P is above or below by taking the dot product of the vectors RS and RP.  If its positive, its above, negative, its below, and zero its on the line.  It requires just 2 multiplications and an addition.

EDIT: Actually wait, that doesn't work.  Let me revise that.

EDIT2: The correct formula was this:
(X2 - X1)*(Py - Y1) - (Y2 - Y1)*(Px - X1)

You can improve it slightly to this:
(X2 - X1)*(Py - Y1) + (Y1 - Y2)*(Px - X1)

That replaces a subtraction with an addition to speed it up.
Title: Re: Finding out which side of a line a point is on
Post by: Deep Toaster on June 21, 2011, 12:49:13 am
Quote from: Quigibo on June 21, 2011, 12:48:06 am
Its very simple.  If you have a point R with vector RS, you can determine if point P is above or below by taking the dot product of RS with RP.  If its positive, its above, negative, its below, and zero its on the line.  It requires just 2 multiplications and an addition.

I think I learned that stuff in math class this year... Never have I wished more that I had paid attention x.x

Thanks Quigibo.

EDIT: Wait, how does that work? The dot product's sign is determined by a cosine, which should be positive on both ends, right?

I'm probably just missing the point entirely.

EDIT2: Oh. What's that called?
Title: Re: Finding out which side of a line a point is on
Post by: calc84maniac on June 21, 2011, 12:51:08 am
Alternatively, if you have a line of equation A*x+B*y=C, and a point (x0,y0), you can compare A*x0+B*y0 to C. If it's greater, it's on one side, if it's less than, it's on the other side, and if it's equal, it's on the line.
Title: Re: Finding out which side of a line a point is on
Post by: Deep Toaster on June 21, 2011, 12:52:29 am
Quote from: calc84maniac on June 21, 2011, 12:51:08 am
Alternatively, if you have a line of equation A*x+B*y=C, and a point (x0,y0), you can compare A*x0+B*y0 to C. If it's greater, it's on one side, if it's less than, it's on the other side, and if it's equal, it's on the line.

And that makes sense now, thanks :)
Title: Re: Finding out which side of a line a point is on
Post by: calc84maniac on June 21, 2011, 12:58:31 am
Also, if you ever want the exact distance from a point to a line, you'd do abs(A*x0+B*y0-C)/sqrt(A^2+B^2). This works especially well if sqrt(A^2+B^2) is a known constant (typically 1, but when working with integers something like 256 might be better)