3

After Googling and looking on Stack for a long time, I've only managed to find methods for determining whether or not a point falls on the line that connects two points. This, unfortunately, isn't what I need.

Please see the image at the end of this question. I apologize in advance for the terrible picture, but it gets the point (get it?) across.

I need to create two perpendicular lines to the one that joins the points x and y. They need to intersect with the perpendicular line at points x and y. I then need to then tell if point z appears between those two lines or not.

Any help is appreciated. Thanks for your time!

Point graph.

Community
  • 1
  • 1
Stev
  • 129
  • 7
  • 2
    isn't this the point-in-polygon problem? - This is a maths problem better suited for http://math.stackexchange.com/ – nicholaswmin Apr 25 '15 at 02:58
  • Thing is, I'm not using a common language. But the language I'm using is most like Java. I think I've found the answer to my own question, however. Get the angle from x to y. Now get the angle from x to z. If the absolute difference is less then 90, wouldn't it be between those two points? – Stev Apr 25 '15 at 02:59
  • 1
    Yes but this is not a programming question – nicholaswmin Apr 25 '15 at 03:00
  • 6
    Why tag java and javascript? Two completely unrelated languages – Patrick Roberts Apr 25 '15 at 03:00
  • http://stackoverflow.com/questions/8721406/how-to-determine-if-a-point-is-inside-a-2d-convex-polygon – nicholaswmin Apr 25 '15 at 03:01
  • I'd calculate the rotation required to bring the xy line parallel to the x-axis, apply that to the z point and check that the transformed z-point's x-value is in the range defined by the transformed x-values of x and y. Some simple trigonometry should handle it. –  Apr 25 '15 at 03:04
  • I see everyone throwing the word "angles" around.. that's a lot more computationally expensive than checking the type of triangle (right, obtuse, acute) by comparing the distance squared between each of the points. See my answer. – Patrick Roberts Apr 25 '15 at 03:42

6 Answers6

3

Compute the angle xyz and yxz. If either is > 90 then it is outside.

mike.k
  • 3,277
  • 1
  • 12
  • 18
2

Since you tagged your question with java, here you go:

import javafx.geometry.Point2D;
....
// is z between parallel lines 
boolean betweenLines(Point2D x, Point2D y, Point2D z) { 
    return  x.angle(y,z) < 90 && y.angle(x,z) < 90;
}
Misha
  • 27,433
  • 6
  • 62
  • 78
1

To find if Z point falls in needed stripe, you can determine if projection of Z to X-Y line falls between these points. Define vectors v = Y - X and w = Z - X. Projection lies in XY segment if parameter b falls in range 0..1. Very simple formula:

b = DotProduct(w, v) / DotProduct(v, v)

enter image description here

Community
  • 1
  • 1
MBo
  • 77,366
  • 5
  • 53
  • 86
1

Example code in JavaScript:

// JavaScript function to determine if infinite strip generated
// by x and y contains the point z
// point structure is:
//  {
//      double x;
//      double y;
//  }
// returns true or false
function stripContainsPoint(x, y, z) {
    var distXZ = (x.x - z.x) * (x.x - z.x) + (x.y - z.y) * (x.y - z.y),
        distXY = (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y),
        distYZ = (y.x - z.x) * (y.x - z.x) + (y.y - z.y) * (y.y - z.y);

    // if triangle is right or acute, or obtuse with hypotenuse XY, returns true
    return (distXZ + distXY >= distYZ) && (distYZ + distXY >= distXZ);
}

The variables dist?? are misnomers, as they are actually the distance squared of each.

Patrick Roberts
  • 49,224
  • 10
  • 102
  • 153
0

So a line can be described by y = mx + b. Lets say your first line is represented by y = 2x-1. Then for any point (u,v), you can plug x=u so that y = 2u-1. That allows you to determine y for the x position on your line. Hence, if v>y, then your point is above the line. Otherwise, your point is below the line.

By doing this with two parallel lines, you'll end up with the three cases obvious from your picture:

  1. y is greater than the corresponding points on both lines
  2. y is greater than the corresponding point on one of your lines
  3. y is less than the corresponding point on both lines

EDIT:

Reading some of the comments on your post, it sounds like there may be better ways than this :)

user2027202827
  • 1,234
  • 11
  • 29
0

Basically, this is a maths problem not a programming problem. (Or to put it another way, once you understand the maths, the programming is trivial.)

I can think of two ways to do this:

  1. Work out the 2 perpendicular lines passing through x and y. If z is above the x perpendicular line and below the y perpendicular line.

  2. Work out the angle between y-x-z and the angle between x-y-z. If both angles are less than 90 degrees, then z is between the lines.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • 3. Determine the distance squared between each two points. If the distance squared between X and Y plus X and Z is less than between Y and Z, and distance squared between X and Y and Y and Z is less than between X and Z. (This is a lot less computationally expensive than calculating angles) – Patrick Roberts Apr 25 '15 at 03:33