-
Notifications
You must be signed in to change notification settings - Fork 49
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
lineIntersectsLine is not commutative #10
Comments
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. |
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 |
I agree with that.
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 |
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! |
@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:
lineIntersectsLine([[0, 0], [1, 0]], [[0.5, -1], [0.5, 0]]) // returns false Here is a PR fixing the issue #23 but reach out if you have another fix in mind |
Thanks @yannbriancon. I've merged your PR. |
Hi,
I noticed this:
Note that the start of
line1
and the end ofline2
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
The text was updated successfully, but these errors were encountered: