Jump to content

  • Log In with Google      Sign In   
  • Create Account

Determine which side of a line a point is


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 GuyWithBeard   Members   -  Reputation: 890

Like
0Likes
Like

Posted 30 July 2009 - 12:47 AM

Hi! I need to check whether a point (given as x,y) is above or below a line (given as two points). I found a few solutions on the net, but they all seemed kind of overkill for this, or they wanted the data in another format. I am working in JavaME, and this is all purely 2D. How would you do this? Thanks!

Sponsor:

#2 ToohrVyk   Members   -  Reputation: 1591

Like
1Likes
Like

Posted 30 July 2009 - 12:55 AM

Assuming the points are (Ax,Ay) (Bx,By) and (Cx,Cy), you need to compute:

(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)

This will equal zero if the point C is on the line formed by points A and B, and will have a different sign depending on the side. Which side this is depends on the orientation of your (x,y) coordinates, but you can plug test values for A,B and C into this formula to determine whether negative values are to the left or to the right.



#3 scgames   Members   -  Reputation: 1977

Like
1Likes
Like

Posted 30 July 2009 - 12:57 AM

You can determine which side of a line a point is on by converting the line to hyperplane form (implicitly or explicitly) and then computing the perpendicular (pseudo)distance from the point to the hyperplane.

Here's an example implementation (pseudocode, not compiled or tested):
int side(vector2 p1, vector2 p2, vector2 p)
{
vector2 diff = p2 - p1;
vector2 perp(-diff.y, diff.x);
float d = dot(p - p1, perp);
return sign(d);
}


#4 GuyWithBeard   Members   -  Reputation: 890

Like
0Likes
Like

Posted 30 July 2009 - 06:46 AM

Thanks guys, it worked great! I used the first technique.

#5 scgames   Members   -  Reputation: 1977

Like
1Likes
Like

Posted 30 July 2009 - 11:46 AM

Quote:
I used the first technique.
Just for the record, the techniques are exactly the same, just written differently. Here's how to get from my version to ToohrVyk's version:
diff.x = Bx - Ax
diff.y = By - Ay
perp.x = Ay - By
perp.y = Bx - Ax

dot(p - p1, perp) =
(Cx - Ax) * (Ay - By) + (Cy - Ay) * (Bx - Ax) =
(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)


#6 TSIROS   Members   -  Reputation: 102

Like
1Likes
Like

Posted 18 August 2009 - 07:49 PM

this is a straight approach, with simple geometry

a rectangular R=(Bx-Ax)*(By-Ay)

two rectangulars

R1=(Bx-Ax)*(Cy-Ay)

R2=(Bx-Cx)*(By-Ay)

R-R1-R2 = (Bx - Ax) * (By - Cy) - (By - Ay) * (Bx - Cx) (1)

instead of previous (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)

if (1) = 0 "on"
if (1) < 0 "left"
if (1) > 0 "right"

no corrections needed

#7 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 19 August 2009 - 01:03 AM

Quote:
Original post by TSIROS
this is a straight approach, with simple geometry

a rectangular R=(Bx-Ax)*(By-Ay)

two rectangulars

R1=(Bx-Ax)*(Cy-Ay)

R2=(Bx-Cx)*(By-Ay)

R-R1-R2 = (Bx - Ax) * (By - Cy) - (By - Ay) * (Bx - Cx) (1)

instead of previous (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)

if (1) = 0 "on"
if (1) < 0 "left"
if (1) > 0 "right"

no corrections needed
Wait...how is that different than what ToohrVyk and I posted? (Aside from being arranged differently, that is.)

Also, what do you mean by 'no corrections needed'?

#8 TSIROS   Members   -  Reputation: 102

Like
0Likes
Like

Posted 19 August 2009 - 02:21 AM

i am sorry

no corrections needed

there is a previous post ....


differently arranged

you use dot product , i use simple geometry, there is a difference.

#9 Daerax   Members   -  Reputation: 1207

Like
0Likes
Like

Posted 19 August 2009 - 02:29 AM

Actually 'simple geometry' is much harder than algebra to do right.

as soon as any new geometric math is invented the first thing mathematicians do is try to find a way to talk about it in algebraic terms. cause its just much easier.

#10 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 19 August 2009 - 06:44 AM

Quote:
you use dot product , i use simple geometry, there is a difference.
Your method performs a dot product as well.

In any case, the only difference I can see between your method and the other proposed solutions is a conceptual one (in other words, it's just an alternate way of expressing the same solution). Or am I missing something?

#11 TSIROS   Members   -  Reputation: 102

Like
0Likes
Like

Posted 24 August 2009 - 09:21 PM

a simple problem.

let a line (L) defined by two points
(Ax,Ay) and (Bx,By)

and two vertical lines on A and B

and a point (Mx,My).

when the point M is between the vertical lines?

#12 Cousken   Members   -  Reputation: 122

Like
0Likes
Like

Posted 25 July 2011 - 03:34 AM

Hello!
Sorry for reviving and old thread. I used the method described here and it works prefectly, but i am trying to undestand the use of dot product here. I have defined my lines with a point and a direction, so half of the math is already done in before hand. My case is as is:

Vector2f myFirstPoint = new Vector2f(100,100);
Vector2f myDirection = new Vector2f(1,0);

public boolean inside(Vector2f aPosition) {
final Vector2f lineToPosition = new Vector2f(aPosition);
lineToPosition.sub(myFirstPoint);

float dotProduct = (myDirection.x) * (lineToPosition.y) - (myDirection.y) * (lineToPosition.x);
if (dotProduct > 0) {
return false;
}
return true;
}

As you can see the only differance here from the original post by ToohrVyk is that i have (Bx - Ax) and (By - Ay) caluclated before hand in the form of myDirection. (Cy - Ay) and (Cx - Ax)are calculated with the sub() method which stands for substact. But the mathematical definition of dot product isn't as the form used here. According to Wikipedia:

Posted Image

According to this what the formula here calculates is not a dot product. I would really appriciate if someone helped me to undestand how dot product is used here, perhaps how the forumla is derived from it?

Thanks everyone who already contributed here for making my life easier :)

#13 luca-deltodesco   Members   -  Reputation: 637

Like
1Likes
Like

Posted 25 July 2011 - 03:47 AM

It's called the perp-dot (perpendicular-dot) product; which is the exterior product in 2 dimensions. It has many properties which the cross product has in 3D; for instance | x perpdot y | = |x||y|sin theta for instance (like in 3D | x cross y | = |x||y|sin theta.

in 2D each vector (vx ; vy) has 2 perpendicular vectors (-vy ; vx), (vy ; -vx) for which we normally choose (-vy ; vx) to be the principal perpendicular, and then the perp-dot product between vectors u,v is perp(u) dot v = u.x * v.y - u.y * v.x

#14 apatriarca   Crossbones+   -  Reputation: 1775

Like
1Likes
Like

Posted 25 July 2011 - 04:00 AM

It is the dot product between the vector perpendicular to the direction and the difference between the points. If (x, y) is a vector, (-y, x) is perpendicular to it (it's the vector rotated by 90°). It works because the projection of one vector v along the direction of another vector d is defined to be (dot(d, v)/dot(d, d))d, but since we are only interested if the projection of the difference vector has the same direction of the perpendicular vector we have chosen, it is enough to determine the sign of the dot product between these two vectors.



#15 Cousken   Members   -  Reputation: 122

Like
0Likes
Like

Posted 25 July 2011 - 05:45 AM

Thank you both very much, that made things much clearer!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS