Determine which side of a line a point is
Author
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!
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.
(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.
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):
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);}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 - Axdiff.y = By - Ayperp.x = Ay - Byperp.y = Bx - Axdot(p - p1, perp) = (Cx - Ax) * (Ay - By) + (Cy - Ay) * (Bx - Ax) = (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
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
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
Quote:Original post by TSIROSWait...how is that different than what ToohrVyk and I posted? (Aside from being arranged differently, that is.)
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'?
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.
no corrections needed
there is a previous post ....
differently arranged
you use dot product , i use simple geometry, there is a difference.
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.
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.
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement