4 hours ago, Alberth said:
In that case you know the x position, so you can use that in the 2nd line to find n2 (unless the 2nd line is vertical as well, then you end up in the parallel case, see below). Use the 'x position' equation of the 2nd line where you use the x of the first line as resulting x position. This gives n2, and y of the shared point. Next you can use the 'y position' equation of the 1st line to get n1.
Yep; that's a relatively easy one, I was just calling it out explicitly to remind me to add it in my code ?
4 hours ago, Alberth said:
Technically, both lines can also be on top of each other, which means you will need to check if the segments overlap. I think it's sufficient if one of the end-points is part of the other line segment. I wonder if a simple AABB (axis aligned bounding box) check would suffice.
Yep, so what I do is work out whether the start of line 1 is within line 2's range, and then, if it's not, calculate n1 for the start and end of line 2 and use the lowest valid value of n1 - i.e. which end would have been hit first.
This has now all been implemented (see attached) and the explosions are now visually in the right place!
Thanks again for all your help - much appreciated!
template<class T = float>
static bool DoLinesIntersect(
T line1StartX,
T line1StartY,
T line1EndX,
T line1EndY,
T line2StartX,
T line2StartY,
T line2EndX,
T line2EndY,
T& line1Proportion,
T& line2Proportion) {
bool line1IsPoint = line1StartX == line1EndX && line1StartY == line1EndY;
bool line2IsPoint = line2StartX == line2EndX && line2StartY == line2EndY;
auto dx2 = line2EndX - line2StartX;
auto dy2 = line2EndY - line2StartY;
if (line1IsPoint && line2IsPoint) {
// both points, just check if they're the same
if (line1StartX == line2StartX &&
line1StartY == line2StartY) {
line1Proportion = 0.0;
line2Proportion = 0.0;
return true;
}
return false;
}
if (line1IsPoint) {
// line 2 must be a line...
if (dx2 == 0 && line1StartX != line2StartX)
return false;
if (dy2 == 0 && line1StartY != line2StartY)
return false;
auto line2ProportionX = (line1StartX - line2StartX) / (line2EndX - line2StartX);
auto line2ProportionY = (line1StartY - line2StartY) / (line2EndY - line2StartY);
if (dx2 == 0) {
line2Proportion = line2ProportionY;
}
else if (dy2 == 0) {
line2Proportion = line2ProportionX;
}
else {
if (line2ProportionX != line2ProportionY)
return false;
line2Proportion = line2ProportionX;
}
if (line2Proportion < 0 || line2Proportion>1)
return false;
line1Proportion = 0;
return true;
}
if (line2IsPoint) {
// Line 1 is a line though...
return DoLinesIntersect(line2StartX,
line2StartY,
line2EndX,
line2EndY,
line1StartX,
line1StartY,
line1EndX,
line1EndY,
line2Proportion,
line1Proportion);
}
// At this stage, we have 2 general lines and need to see if they intersect with each other...
//
// There are 3 possibilities:
// 1. The lines are parallel to each other
// 2. Line 1 is a vertical line (has to be separated out to enable the equations to be solved)
// 3. they're general lines and there's a general solution
auto dx1 = line1EndX - line1StartX;
auto dy1 = line1EndY - line1StartY;
auto a1 = line1StartX;
auto b1 = line1StartY;
auto a2 = line2StartX;
auto b2 = line2StartY;
bool line1IsVertical = dx1 == 0;
if (line1IsVertical) {
if (dx2 == 0) {
// We have the even more special case that both lines are vertical hence this is similar to the parallel case
if (a1 != a2)
return false;
// There are 4 options if we're in the same linear space:
// 1. No overlap
// 2. Initial overlap
// 3. line 2 starts in line 1
// 4. line 2 ends in line 1
//
// Note that #3 and #4 are both possible, at which point the lowest n1 should be selected
auto n2Initial = (b1 - b2) / dy2;
if (n2Initial >= 0 && n2Initial <= 1) {
line1Proportion = 0;
line2Proportion = n2Initial;
return true;
}
auto n1Line2Start = (b2 - b1) / dy1;
auto n1Line2End = (line2EndY - b1) / dy1;
bool line2StartIntersects = n1Line2Start >= 0 && n1Line2Start <= 1;
bool line2EndIntersects = n1Line2End >= 0 && n1Line2End <= 1;
if (line2StartIntersects && line2EndIntersects) {
line2StartIntersects = n1Line2Start <= n1Line2End;
line2EndIntersects = !line2StartIntersects;
}
if (line2StartIntersects) {
line1Proportion = n1Line2Start;
line2Proportion = 0;
return true;
}
if (line2EndIntersects) {
line1Proportion = n1Line2End;
line2Proportion = 1;
return true;
}
return false;
}
// Check to see where we hit line 2
auto n2 = (a1 - a2) / dx2;
if (n2 < 0 || n2 > 1)
return false;
// Check to see whether this would give a reasonable value for line 1
auto n1 = (b2 - (n2*dy2) - b1) / dy1;
if (n1 < 0 || n1 > 1)
return false;
line1Proportion = n1;
line2Proportion = n2;
return true;
}
bool linesAreParallel = (dy2 - (dx2*dy1 / dx1)) == 0;
if (linesAreParallel) {
auto n2InitialX = (a1 - a2) / dx2;
auto n2InitialY = (b1 - b2) / dy2;
if (dx2 != 0 &&
dy2 != 0 &&
n2InitialX != n2InitialY)
return false;
auto n2Initial = dx2 == 0 ? n2InitialY : n2InitialX;
if (n2Initial >= 0 && n2Initial <= 1) {
line1Proportion = 0;
line2Proportion = n2Initial;
return true;
}
// Now, it's time to do the check for the line2Start and line2End and calculate accordingly
T n1Line2Start, n1Line2End;
{
auto n1Line2StartX = (a2 - a1) / dx1;
auto n1Line2StartY = (b2 - b1) / dy1;
n1Line2Start = dx1 == 0 ? n1Line2StartY : n1Line2StartX;
}
{
auto n1Line2EndX = (line2EndX - a1) / dx1;
auto n1Line2EndY = (line2EndY - b1) / dy1;
n1Line2End = dx1 == 0 ? n1Line2EndY : n1Line2EndX;
}
bool line2StartIntersects = n1Line2Start >= 0 && n1Line2Start <= 1;
bool line2EndIntersects = n1Line2End >= 0 && n1Line2End <= 1;
if (line2StartIntersects && line2EndIntersects) {
line2StartIntersects = n1Line2Start <= n1Line2End;
line2EndIntersects = !line2StartIntersects;
}
if (line2StartIntersects) {
line1Proportion = n1Line2Start;
line2Proportion = 0;
return true;
}
if (line2EndIntersects) {
line1Proportion = n1Line2End;
line2Proportion = 1;
return true;
}
return false;
}
// General solution time
{
// Calculate n2
line2Proportion = (b1 + (a2 * dy1 / dx1) - (a1*dy1 / dx1) - b2) / (dy2 - (dx2*dy1 / dx1));
if (line2Proportion < 0 || line2Proportion > 1)
return false;
// We hit within a reasonable region of line 2, now let's check for line 1
line1Proportion = (a2 + (line2Proportion*dx2) - a1) / dx1;
if (line1Proportion < 0 || line1Proportion>1)
return false;
return true;
}
}
)
