Я работаю над маленькой игрой, которая нуждалась в функции для вычисления точки пересечения двух линий. Итак, я получил эту формулу из Википедии (http://en.wikipedia.org/wiki/Line-line_intersection) и превратил это в функцию.
bool lineline(int L1X1, int L1Y1, int L1X2, int L1Y2, int L2X1, int L2Y1, int L2X2, int L2Y2, int* X, int* Y) { // Returns the point of intersection of two lines
int D = (L1X1 - L1X2) * (L2Y1 - L2Y2) - (L1Y1 - L1Y2) * (L2X1 - L2X2); // Denominator. If zero then no intersection
if (D == 0) { // Parallel and possibly overlapping
return false;
} else {
*X = ( (L1X1 * L1Y2 - L1Y1 * L1X2) * (L2X1 - L2X2) - (L1X1 - L1X2) * (L2X1 * L2Y2 - L2Y1 * L2X2) ) / D; // Calculate x
*Y = ( (L1X1 * L1Y2 - L1Y1 * L1X2) * (L2Y1 - L2Y2) - (L1Y1 - L1Y2) * (L2X1 * L2Y2 - L2Y1 * L2X2) ) / D; // Calculate y
std::cout << D << " | " << *X << " | " << *Y << "\n";
if (*X >= Bmin(L1X1, L1X2) && *X <= Bmax(L1X1, L1X2) && *Y >= Bmin(L1Y1, L1Y2) && *Y <= Bmax(L1Y1, L1Y2)) {
// Intersection is on first line
if (*X >= Bmin(L2X1, L2X2) && *X <= Bmax(L2X1, L2X2) && *Y >= Bmin(L2Y1, L2Y2) && *Y <= Bmax(L2Y1, L2Y2)) {
// Intersection is on second line
return true;
} else {
// Intersection is on first, but not on second line
return false;
}
} else {
// Intersection is not on first line.
return false;
}
return true;
}
}
Он работает довольно хорошо, например, когда я вызываю его с этими аргументами, он возвращает true
lineline(400, 0, 400, 2000, 0, 400, 2000, 400, &x, &y);
Однако, когда я перемещаю вторую линию на 1300 единиц …
lineline(400, 0, 400, 2000, 0, 1700, 2000, 1700, &x, &y) == false;
Возвращает ложь. Хотя две строки из второго вызова функции должны пересекаться, верно? Значения, которые он вычисляет с этими параметрами:
D = -4000000
*X = 400;
*Y = -447;
Кто-нибудь может мне помочь с этим? Я застрял на этом целый день и, возможно, мне просто не хватает чего-то простого, как в прошлый раз, но я не вижу этого. Заранее спасибо!
Формула поднимает различия между входными числами до третьей степени, поэтому, если различия имеют примерно три цифры, вы должны быть осторожны с переполнением int
, который имеет девять цифр, плюс первая цифра может доходить до 2. после того, как вы переполните int
, вы начинаете видеть отрицательные числа в результате умножения положительных, поэтому остальные ваши вычисления становятся неверными.
Чтобы улучшить диапазон, используйте 64-битные целые числа (т.е. long long
) для ваших промежуточных результатов.
Не уверен на 100%, но вы не можете изменить масштаб значений? Например. разделите все с наибольшим и используйте результаты с плавающей запятой, у вас будут одинаковые размеры просто в другом соотношении. Поскольку вам не нужна точная точка пересечения, это должно работать, только помните, что вы не получите 0 для параллельных линий, поэтому вы должны использовать действительно маленькое значение альфа, чтобы определить диапазон 0 +/- альфа, который будет определять значения D для параллельные линии.