**1**

# Determine which side of a line a point is

###
#1
Members - Reputation: **1615**

Posted 30 July 2009 - 12:47 AM

###
#2
Members - Reputation: **1591**

Posted 30 July 2009 - 12:55 AM

*(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
Members - Reputation: **2078**

Posted 30 July 2009 - 12:57 AM

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);

}

###
#5
Members - Reputation: **2078**

Posted 30 July 2009 - 11:46 AM

Quote: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:

I used the first technique.

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
Members - Reputation: **102**

Posted 18 August 2009 - 07:49 PM

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
Members - Reputation: **2078**

Posted 19 August 2009 - 01:03 AM

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

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

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

###
#10
Members - Reputation: **2078**

Posted 19 August 2009 - 06:44 AM

Quote:Your method performs a dot product as well.

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

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?

###
#12
Members - Reputation: **122**

Posted 25 July 2011 - 03:34 AM

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:

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
Members - Reputation: **637**

Posted 25 July 2011 - 03:47 AM

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
Crossbones+ - Reputation: **2275**

Posted 25 July 2011 - 04:00 AM