Technically, the position of a point, relative to an arbitrary straight line, is computed with a vector cross-product. This concept should be familiar to those who have studied vector algebra. The formula is not intuitively easy to understand, but can be illustrated with the following example:
(xs, ys) point on the line;
used as the vector starting point
(xe, ye) point on the line;
used as the vector end point
(xt, yt) test point
Rotate the vector 90 degrees counter-clockwise, the new vector end point (xr, yr) is given by:
xr = xs - (ye - ys)
yr = ys + (xe - xs)
Project the test point onto the new vector, using the vector inner product (which many people are familiar with):
dxt = xt - xs
dyt = yt - ys
dxv = xr - xs = ys - ye
dyv = yr - ys = xe - xs
D = dxt*dxv + dyt*dyv
If D is positive, the test point is on the positive side of the vector's starting point (xs, ys), which implies that it is also to the left of the original line (assuming that a right-handed coordinate system is used). Figure 6
illustrates the algorithm with the two test points (x1, y1) and (x2, y2).