lineIntersectsLine is not commutative

[yeldiRium]

Hi,

I noticed this:

const line1 = [
  [50.054358, 8.693184],
  [50.055604, 8.685873]
];
const line2 = [
  [50.054228, 8.69338],
  [50.054358, 8.693184]
];
lineIntersectsLine(line1, line2);
// false
lineIntersectsLine(line2, line1);
// true

Note that the start of line1 and the end of line2 are identical.

What do you think is the expected result? Since the lines share a point, they arguably do intersect. However my use case is around multiple lines fanning out from a single point and I don't want to count those as intersecting.

I'd suggest adding a parameter excludeEndpoints that determines wether sharing a start/end-point should count as intersecting. What do you think?

I can probably open a PR if we decide on something.

Kind regards, yeldiRium

[yeldiRium]

Update:

I debugged the intermediate values in the algorithm and got this:

lineIntersectsLine(line1, line2);
// { det: 7.062139999908574e-7 }
// { lambda: -0, gamma: 0 }

lineIntersectsLine(line2, line1)
// { det: -7.062139999908574e-7 }
// { lambda: 0.9999999999999997, gamma: 0.9999999999999999 

So this might be a rounding error on JavaScript's part? Unfortunately i don't know much about the details of mathematics and how numbers/floats work in JavaScript.

[HarryStevens]

Strictly speaking, an intersection is defined as a point common to two or more objects (here is a Wikipedia article on that), which means that two line segments that share an endpoint do, in fact, intersect. To solve for this, I think it would make sense to add a test to this function that first checks to see if the two lines share a common point before continuing with the rest of the algorithm. Something like:

if (sharePoint(lineA, lineB)){ return true; }

function sharePoint(lineA, lineB){
  let share = false;
  for (let i = 0; i < 2; i++){
    for (let j = 0; j < 2; j++){
      if (equal(lineA[i], lineB[j])){
        share = true;
        break;
      }
    }
  }
  return share;
}

function equal(pointA, pointB){
  return pointA[0] === pointB[0] && pointA[1] === pointB[1];
}

On the other hand, it sounds like that's not your desired outcome. Can you explain in a little more detail your use case for the excludeEndpoints parameter?

[yeldiRium]

two line segments that share an endpoint do, in fact, intersect

I agree with that.

Can you explain in a little more detail your use case for the excludeEndpoints parameter?

In my use case I have multiple lines coming from the same point and those lines should not count as intersecting each other. Maybe you know the game Ingress. I'm building a simulation for it.

However I've solved my use case with my own implementation in the mean time, so I wouldn't want to burden your implementation with a feature just for my sake.

The actual problem I was reporting in this issue, however, is not that the function isn't applicable to my use case, but rather that it does not always produce the intended result. As outlined in my first code example, the function lineIntersectsLine is not commutative, which it should be - regardless of whether endpoints should be included or not.

[HarryStevens]

I agree that the function should be commutative. Floating-point arithmetic is always tricky in JavaScript, but the test that I mentioned in my previous comment will at least ensure that the function will always return true if the lines share an endpoint. Thank you for bringing this to my attention!

[yannbriancon]

@HarryStevens Thanks for this great library!

I am though having issues with the fact that if the end point of one line is on the other line but is not its beginning or end, the lines are not detected as intersecting.

Here is an example: line1 = [a, b] = [[0, 0], [1, 0]] line2 = [c, d] = [[0.5, -1], [0.5, 0]]

a---d---b
    |
    |
    c

lineIntersectsLine([[0, 0], [1, 0]], [[0.5, -1], [0.5, 0]]) // returns false

Here is a PR fixing the issue https://github.com/HarryStevens/geometric/pull/23 but reach out if you have another fix in mind

[HarryStevens]

Thanks @yannbriancon. I've merged your PR.