How can you determine a point is between two other points on a line segment?

Question

I´m using notifications for the androidwear watch in my project. My intentention is that the background of the notificatión will be an image extract from a url, but i don´t know how to do it.

The doc of the NotificationCompat.WearableExtender()explain:

.setBackground(bBitmap);

but.. if i want to load the backgroud from a url?

i´ll be reading about this, but without success.

Thanks in advance.

Solution 1

Check if the cross product of (b-a) and (c-a) is 0, as tells Darius Bacon, tells you if the points a, b and c are aligned.

But, as you want to know if c is between a and b, you also have to check that the dot product of (b-a) and (c-a) is positive and is less than the square of the distance between a and b.

In non-optimized pseudocode:

def isBetween(a, b, c):
    crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)

    # compare versus epsilon for floating point values, or != 0 if using integers
    if abs(crossproduct) > epsilon:
        return False

    dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y)*(b.y - a.y)
    if dotproduct < 0:
        return False

    squaredlengthba = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
    if dotproduct > squaredlengthba:
        return False

    return True

Solution 2

Here's how I'd do it:

def distance(a,b):
    return sqrt((a.x - b.x)**2 + (a.y - b.y)**2)

def is_between(a,c,b):
    return distance(a,c) + distance(c,b) == distance(a,b)

Solution 3

Check if the cross product of b-a and c-a is0: that means all the points are collinear. If they are, check if c's coordinates are between a's and b's. Use either the x or the y coordinates, as long as a and b are separate on that axis (or they're the same on both).

def is_on(a, b, c):
    "Return true iff point c intersects the line segment from a to b."
    # (or the degenerate case that all 3 points are coincident)
    return (collinear(a, b, c)
            and (within(a.x, c.x, b.x) if a.x != b.x else 
                 within(a.y, c.y, b.y)))

def collinear(a, b, c):
    "Return true iff a, b, and c all lie on the same line."
    return (b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y)

def within(p, q, r):
    "Return true iff q is between p and r (inclusive)."
    return p <= q <= r or r <= q <= p

This answer used to be a mess of three updates. The worthwhile info from them: Brian Hayes's chapter in Beautiful Code covers the design space for a collinearity-test function -- useful background. Vincent's answer helped to improve this one. And it was Hayes who suggested testing only one of the x or the y coordinates; originally the code had and in place of if a.x != b.x else.

(This is coded for exact arithmetic with integers or rationals; if you pass in floating-point numbers instead, there will be problems with round-off errors. I'm not even sure what's a good way to define betweenness of 2-d points in float coordinates.)

Solution 4

Here's another approach:

• Lets assume the two points be A (x1,y1) and B (x2,y2)
• The equation of the line passing through those points is (x-x1)/(y-y1)=(x2-x1)/(y2-y1) .. (just making equating the slopes)

Point C (x3,y3) will lie between A & B if:

• x3,y3 satisfies the above equation.
• x3 lies between x1 & x2 and y3 lies between y1 & y2 (trivial check)

Solution 5

The length of the segment is not important, thus using a square root is not required and should be avoided since we could lose some precision.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Segment:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def is_between(self, c):
        # Check if slope of a to c is the same as a to b ;
        # that is, when moving from a.x to c.x, c.y must be proportionally
        # increased than it takes to get from a.x to b.x .

        # Then, c.x must be between a.x and b.x, and c.y must be between a.y and b.y.
        # => c is after a and before b, or the opposite
        # that is, the absolute value of cmp(a, b) + cmp(b, c) is either 0 ( 1 + -1 )
        #    or 1 ( c == a or c == b)

        a, b = self.a, self.b             

        return ((b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y) and 
                abs(cmp(a.x, c.x) + cmp(b.x, c.x)) <= 1 and
                abs(cmp(a.y, c.y) + cmp(b.y, c.y)) <= 1)

Some random example of usage :

a = Point(0,0)
b = Point(50,100)
c = Point(25,50)
d = Point(0,8)

print Segment(a,b).is_between(c)
print Segment(a,b).is_between(d)

View more solutions

Comments

[ojrac]

I see a LOT of length = sqrt(x) stuff going on in these answers; they might work, but they aren't fast. Consider using length-squared; if you're just comparing squared length values to each other, there's no loss of accuracy, and you save slow calls to sqrt().

[RobS]

Is the point c represented by 2 integers as well? If so then do you want to know if c is exactly along a real straight line between a and b or lies on the raster approximation of the straight line between a and b? This is an important clarification.

[Below the Radar]

A similar question was asked here: stackoverflow.com/q/31346862/1914034 with a solution when a buffer distance from the line is needed

[Georgy]

Related: Determine if Shapely point is within a LineString/MultiLineString

[Stefnotch]

Warning to future readers: A fair number of answers are incorrect or incomplete. A few edge cases that frequently don't work are horizontal and vertical lines.

[Jonathan Leffler]

The only problem with this is the numerical stability - taking differences of numbers and so on is apt to lose precision.

[Jonathan Leffler]

Shouldn't the last condition be more like: ABS(product - lengthca * lengthba) < epsilon?

[Darius Bacon]

Shouldn't you be comparing squared lengths instead? Square roots are to be avoided. Also, if this is unavoidable due to overflow, you can use math.hypot instead of math.sqrt (with the appropriate change of arguments).

[Darius Bacon]

I wonder about that epsilon, too. Can you explain it? Of course, if we must deal with floats, we must be careful about comparisons, but it's not clear to me why an epsilon makes this particular comparison more accurate.

[Cyrille Ka]

I concur. There is several good answer to this question, and this one is fine. But this code needs to be amended to not use sqrt, and the last comparison fixed.

[jfs]

-epsilon < (distance(a, c) + distance(c, b) - distance(a, b)) < epsilon

[jfs]

-epsilon < crossproduct < epsilon and min(a.x, b.x) <= c.x <= max(a.x, b.x) and min(a.y, b.y) <= c.y <= max(a.y, b.y) is sufficient, isn't it?

[Federico A. Ramponi]

@Jonathan: indeed the code is more familiar and elegant using abs. Thanks.

[Federico A. Ramponi]

As for the epsilon stuff: That is only a matter of not using == to compare floating point numbers. You should never use x==y with floats. You should use abs(x-y) <= epsilon (small) instead. In the revised code I use > epsilon to express !=.

[Federico A. Ramponi]

Note that I don't like any solution which involves cross products. The dot product and/or the distance work also in 4-dimensional or n-dimensional spaces, the cross product (as an operation on two vectors) does not.

[Federico A. Ramponi]

Now it doesn't use sqrt anymore.

[Cyrille Ka]

Yes, silly me. That's the answer of Sridhar Iyer, with a crossproduct instead of slopes. As I said, there is several possible answers. :)

[jfs]

If c.x or c.y are float then the first == in is_between() could fail (btw it is a crossproduct in disguise).

[bart]

The absolute value of the crossproduct is twice the area of the triangle formed by the three points (with the sign indicating the side the third point) so IMHO you should use an epsilon that is proportional to the distance between the two endpoints.

[bart]

That doesn't take rounding errors (inexactness of coordinates) into account.

[jfs]

add to is_between(): a, b = self.a, self.b

[Darius Bacon]

As Jonathan Leffler mentions in another comment, this has numerical issues that other approaches like the cross-product avoid. The chapter I link to in my answer explains.

[Darius Bacon]

This is the right idea, I think, but short on detail (how do we check that equation in practice?) and a bit buggy: the last y3 ought to be y2.

[Darius Bacon]

It looks like that will return true if all three points are the same (which is all right, imho) but false if exactly two of the points are the same -- a pretty inconsistent way to define betweenness. I posted an alternative in my answer.

[Ognjen]

fixed that by another cmp trick, but this code starts to smell ;-)

[Lordn__n]

It solves how to draw a line through a two-dimensional integer space between two arbitrary points and its mathematically correct. If the third point is one of the points on that line then it is, by definition, between those two points.

[Lordn__n]

This works in real space, not integer space as the poster asked.

[Cyrille Ka]

Can you tell us why wouldn't it work with integers ? I don't see the problem, provided that the epsilon check is replaced by "!= 0".

[Cyrille Ka]

No, Bresenham's Line Algorithm solves how to create an approximation of a line segment in a two-dimensional integer space. I don't see from the original poster's message that it was a question about rasterization.

[Lordn__n]

"Let's say you have a two dimensional plane with 2 points (called a and b) on it represented by an x INTEGER and a y INTEGER for each point." (emphasis added by me).

[Lordn__n]

Because either a) the approximated line between the two points is important and those vectors don't match in real terms or b) you are only interested in an exact match in which case I'm sure you could reduce it to a greatest common factor type calculation.

[Sumudu Fernando]

After checking the cross product condition, it is simpler to check that (c-a).(b-c) > 0 (with equality when c = a or c = b); this just says that the parallel vectors c-a and b-c have to point in the same direction.

[Darius Bacon]

I think this misrepresents my answer, which also checks the betweenness condition.

[causa prima]

I liked the idea of doing it without the expensive square root operation but I just found out the hard way that this doesn't work. We have three points, ab is 4, bc is 4, ac is 6. a+b>c (4+4>6)--they're not a line. Yet a^2+b^2<c^2 (16+16<36).

[serverpunk]

Is it just me or is there something missing in the expression for squaredlengthba? Why the extra parenthesis?

[Cyrille Ka]

Yes, the extra parenthesis is just a typo. 4 years have passed before someone said something. :)

[Grant M]

I think Bresenham's Line Algorithm gives closet integer points to a line, that can then be used to draw the line. They may not be on the line. For example if for (0,0) to (11,13) the algorithm will give a number pixels to draw but there are no integer points except the end points, because 11 and 13 are coprime.

[Grant M]

Since range checking faster would it be better to range check first then check for collinear if in bounding box.

[frankgut]

You should rename a,b,c to make it clearer which are the segment end points and which is the query point.

[Mikko Virkkilä]

The function is_on(a,b,c) is wrong for the case where a == b != c. In such a case it will return true, even though c does not intersect a line segment from a to b.

[Darius Bacon]

@SuperFlux, I just tried running that, and got False.

[Rick]

I think this answer is pretty clearly superior to the current accepted answer.

[Robin Davies]

How about crazy floating point precision problems when some of the coordinates are close or identical?

[Robin Davies]

The correct way to avoid precision problems in most other approaches. Also significantly more efficient that most other approraches.

[Charles Bretana]

Computers don't do floating points well. In a computer there's no such thing as infinitely continuously adjustable values. So if you are using Floating points, you have to establish define and use some small epsilon value as a determinant, and any two points closer than that epsilon should be considered the same point. Determine the point that IS on the same line and the same distance from the end points. If your candidate point is within your epsilon of that calculated point, then call it identical.

[Robin Davies]

My point was that this answer is unusable because of precision problems when you actually implement it in code. So nobody should use it. A lovely answer on a math test. But a compete failure in a comp-sci course. I came here looking for the dot-product method (which is correct); so I thought I'd take a few moments to flag the many answers in this thread that are incorrect so others that are familiar with the correct solution won't be tempted to use them.

[Charles Bretana]

You are correct about the issues that arise due to computers inability to represent every possible real number on a line. You are incorrect that any solution (including dot product method) can be immune to these issues. Any solution can suffer from these problems. Unless you make some allowances for acceptable epsilon, a point that is exactly on the line (but whose coordinates are not representable in ieee floating point binary representation), will fail the dot product test as well, since the computer will represent the point's coordinates inaccurately by some amount.

[John Demetriou]

so basically if (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y) == 0 then they are collinear. But, what do the negative and positive values mean?

[Darius Bacon]

@JohnDemetriou, it's an oriented area of the triangle through a, b, and c. The 'area' is positive or negative depending on whether tracing through them in that order goes clockwise or counterclockwise (but I'm too lazy at the moment to tell you which direction would yield positive vs. negative).

[Paulo Neves]

@MikkoVirkkilä: return (p <= q <= r or r <= q <= p) and (p != r or p == q == r)

[Neon Warge]

@jfs what do you mean by that? Whats the check with the epsilon for?

[jfs]

@NeonWarge: sqrt() returns a float. == is a wrong thing for floats in most cases. math.isclose() could be used instead. There was no math.isclose() in 2008 and therefore I've provided the explicit inequality with epsilon (abs_tol in math.isclose() speak).

[Jules]

That is absolutely correct, however, this method is not very good even with math.isclose(). When the coordinates are integers you would like to have an exact test. My other answer gives a formula for that: stackoverflow.com/a/29301940/40078

[vac]

It looks like this code would just works with vertical and horizontal line segments. What if ptLineStart is (0,0), ptLineEnd is (2,2) and ptPoint is (1, 1)?

[user43968]

dotProduct can only tell about alignement. Your code is incomplete !!! With a(0,0), b(4,0), c(1,1) you have dotproduct = (1-0)*(1-4) +(1-0)*(1-0) = -3+1=-3

[Climax]

Shouldn't it be if abs(crossproduct) < epsilon: For the simple fact that it could lead to 0-division if the cross product is 0

[nivs1978]

What is the value of epsilon? A very small number to take into account for floating point errors?

[Ideogram]

How can a solution that is correct for real space ( ℝ×ℝ) not be correct for integer space (ℕ×ℕ), as ℕ∈ℝ. Or do you mean: "is not optimal for…" instead of 'is not correct ?

[Amar C]

I am not getting cross product as zero while using the points (.5,0), (2,1), (1.6,.6). The cross product in -0.2. What could be wrong? I am using the following code to test: python ax,ay = (.5,0) bx,by = (2,1) cx,cy = (1.6,.6) crossproduct = (cy - ay) * (bx - ax) - (cx - ax) * (by - ay)

[Cyrille Ka]

@AmarC: these 3 points are not aligned, that's why. If C was (1.4,.6) for example it would be 0.

[jwezorek]

collinear(a, b, c) is testing floating point numbers by equality. Shouldnt it use an epsilon/tolerance?

[Schlumpf]

if a dotproduct is 0 then it means that the angle is 90° => the two vectors are orthogonal and therefore the points are not on the same line. Should'nt we check dotproduct <= 0 instead of < 0? Well through the crossproduct check as first step we already checked, that they lie on the same line, but wouln't <= be a little bit more logical? Or do I have a wrong assumption?

[Schlumpf]

The squaredlengthba check I haven't understood yet. Why is this assumption true? The dotproduct only gives an indication of the angle of the two vectors, which should be ~ 0° when we divide the result through its length and use the arccos as the two vectors are parallel. So why does it work if I compare the squaredlengthba (AB²) with the dotproduct of the two vectors (AC and AB)?

[golwig]

@user43968 you're right. Forgot that i was working with vectors back then. The answer from Cyrille Ka is the right (full) one!

[alan23273850]

To check whether c is between a and b, it's simpler to check the dot product of (c-a) and (c-b) is nonpositive. This avoids computing Euclidean distances.

[Marcel]

@jfs why not abs(distance(a, c) + distance(c, b) - distance(a, b)) < epsilon

[jfs]

@Marcel: Perhaps, to avoid thinking about edge cases: none, -inf, subnormals. I'm not sure, now.

[Darius Bacon]

@jwezorek floating point numbers do raise such issues, but this code doesn't introduce floats.

[jwezorek]

Well, yeah, and in a statically typed language that would be clear but in a dynamically typed language, well, 90% of time if someone sees a point type they are going to assume floating point values will work. I mean this is why dynamic types are not great for this sort of thing.