Hi all, I am trying to find out a simple algorithm to find out if a point, specified by a 2D vector is to the left or right of a line segment. A line segment is defined by + u * ( - ), where points to the tail of the line segment and points to the head. In graphics: v2 / / w / v1 should return ''right'', because the segment points from v1 to v2 and w lies at the right-hand side. I know there probably is a way using special cases, but I would like to know if there are any elegant solutions to the problem. I hope I made myself clear, anybody has an idea?

A line segment has a direction, but no orientation. Therefore, it has neither left nor right.

With two 2D vectors (AB, AC), you''d get that from the sign of the determinant.

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

If we apply some sort of metric to the situation, i.e angle of rotation from +X axis, then we have something to work with.

Can''t you just find the dot product??

if ur line is made up of a direction vector v1 and a position vector v2, and ur point is at point p.

Then you get vector v3 = (p - v2)

If you find the dot product of v1 and v3, if it is greater than zero the point is one side of the line, if the point is less than zero then its on the other side of the line.

quote:

---

Original post by Yau
Can''t you just find the dot product??

---

That won''t work. The sign of the dot product handles "forward" and "backward" ( a.b = 0 if orthogonal), not "left" and "right". You need the cross-product for "left" and "right", and thus, the determinant of the two vectors (''z'' coordinate of the cross product).

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

Since you are in two dimensions you can find a "right" vector easily enough. If your line''s direction is (x,y) then the right vector is (y,-x) assuming x is positive, i.e. right is below the line. The sign of the dot product will then tell you which "side" of the line the point is on. The dot product does tell you front and back, but front doesn''t have to be forward, i.e. it can be left or right.

quote:

---

Original post by LilBudyWizer
If your line''s direction is (x,y) then the right vector is (y,-x) assuming x is positive, i.e. right is below the line. The sign of the dot product will then tell you which "side" of the line the point is on.

---

And the result (x1.y2-x2.y1) is the determinant of [[x1 y1][x2 y2]], as I was saying all along

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

The determinant method worked and was the elegant solution I was looking for. Thanks!

Just out of curiosity; what is the exact meaning of a determinant anyway (except of the definition)? In all linear algebra texts I have encountered only the definition is given, not the conceptual meaning.

Could anyone enlight me in this?

quote:

---

Original post by leroy
Just out of curiosity; what is the exact meaning of a determinant anyway (except of the definition)? In all linear algebra texts I have encountered only the definition is given, not the conceptual meaning.

---

A zero determinant means that your system of vectors contains two or more linearly dependent vectors. It is also used for matrix inversions, and has (as far as ''meaning'' is concerned) some relation I can''t quite remember with the mixed product

Sorry I can''t help more, it''s been 6 years since my last linear algebra class.

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

Area of the triangle v1-v2-w. If the area is positive then w is to the left, if the area is negative then w is to the right (it could be the other way round, I cant remember)

Area = 0.5*((xb-xa)*(yc-ya)-(xc-xa)*(yb-ya))

Where xa,ya xb,yb xc,yc are the points on the triangle

The area is 0 if the points are colinear