Make sure the point projected onto the line segment is not outside

Question

See image above; basically, I want a simple test to check if a point is in the range of a linear segment. Information (or input, if you prefer), I have the coordinates of the point, and the coordinates of the points of the end of the line segment. The result I want is a simple logical. How can I check this in a simple way?

Answer 1

You may have a simple and uniform check if you are using an internal product. The inner product between two vectors can be geometrically visualized as the product of the lengths of two time vectors, the cosine of the angle between them, or the product of the length of one of the vectors and the length of the (orthogonal) projector of the other by the line defined by this vector.

In your situation, if you project a vector v from one of the endpoints of the segment to the point in question, the point lies inside the allowed area if and only if the projection falls on the segment s connecting the two endpoints. And it is equivalent

 0 <= v·s <= s·s 

(strict inequalities if you want to exclude lines perpendicular to the segment through the endpoints)

 public static boolean inRange(double start_x, double start_y, double end_x, double end_y, double point_x, double point_y) { double dx = end_x - start_x; double dy = end_y - start_y; double innerProduct = (point_x - start_x)*dx + (point_y - start_y)*dy; return 0 <= innerProduct && innerProduct <= dx*dx + dy*dy; } 

Answer 2

It’s not difficult to determine the equations of these perpendicular dashed lines passing through the endpoints of your bold line.

Let the bold line be defined by points (x 1 , y 1 ) and (x 2 , y 2 ) . Then it has a slope

  m = (y 2 - y 1 ) / (x 2 - x 1 )

Thus, all perpendicular lines will have the form

  y (x) = ( -1 / m ) x + c

We can use this to determine the equations of perpendicular lines passing through (x 1 , y 1 ) and (x 2 , y 2 ) (respectively), which essentially represent the boundary of the area in which all real points should be:

  y a (x) = (-1 / m) x + y 1 + x 1 / m
 y b (x) = (-1 / m) x + y 2 + x 2 / m

So, for an arbitrary point (x*, y*) , to determine if it is in a valid area, you can check

  y a (x *) <= y * <= y b (x *)

(or vice versa if y a (x*) greater)

---

The following should do the trick:

 public static boolean check(double x1, double y1, double x2, double y2, double x, double y) { if (x1 == x2) { // special case return y1 < y2 ? (y1 <= y && y <= y2) : (y2 <= y && y <= y1); } double m = (y2 - y1) / (x2 - x1); double r1 = x1 + m * y1; double r2 = x2 + m * y2; double r = x + m * y; return r1 < r2 ? (r1 <= r && r <= r2) : (r2 <= r && r <= r1); } 

Answer 3

You can do this by calculating the angles.

Suppose your endpoints are (x1, y1) and (x2, y2), and your endpoint is (x, y).

Then you create two vectors: from one endpoint to another and one endpoint to your point:

 vec1 = (x - x1, y - y1); vec2 = (x2 - x1, y2 - y1); 

Calculate point product:

 double dotp = (x-x1) * (x2-x1) + (y-y1) * (y2 - y1); 

Now the point product divided by the value gives you the cosine of the angle:

 double theta = Math.acos((dtop) / (Math.sqrt((x-x1) * (x-x1) + (y-y1) * (y-y1)) * Math.sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)))); 

Now the trick is that if your angle is greater than PI / 2 , you are 'out'

 public static boolean check(double x, double y, double x1, double y1, double x2, double y2) { // vectors are (dx1, dy1) and (dx2, dy2) double dx1 = x - x1, dx2 = x2 - x1, dy1 = y - y1, dy2 = y2 - y1; double dotp = dx1 * dx2 + dy1 * dy2; double theta = Math.acos(dotp / (Math.sqrt(dx1 * dx1 + dy1 * dy1) * Math.sqrt(dx2 * dx2 + dy2 * dy2))); theta = Math.abs(theta); if (theta > (Math.PI / 2)) return false; dx1 = x - x2; dx2 = x1 - x2; dy1 = y - y2; dy2 = y1 - y2; dotp = dx1 * dx2 + dy1 * dy2; theta = Math.acos(dotp / (Math.sqrt(dx1 * dx1 + dy1 * dy1) * Math.sqrt(dx2 * dx2 + dy2 * dy2))); theta = Math.abs(theta); if (theta > (Math.PI / 2)) return false; return true; } 

Answer 4

I took Daniel Fisher's answer, which is great, and adjusted it for 3D and Unity:

 public bool InSegmentRange(Vector3 start, Vector3 end, Vector3 point) { Vector3 delta = end - start; float innerProduct = (point.x - start.x) * delta.x + (point.y - start.y) * delta.y + (point.z - start.z) * delta.z; return innerProduct >= 0 && innerProduct <= delta.x * delta.x + delta.y * delta.y + delta.z * delta.z; }