Правильно ли и последовательно проверять две вершинные точки на равенство?
Я пишу игру Typescript, в которой на холсте нарисованы вершины, а из них исходят некоторые ребра. Я хочу определить, пересекаются ли некоторые ребра из разных вершин. Для этого я использую общую функцию doLinesIntersect, чтобы определить, пересекаются ли два ребра.
Однако проблема в том, что он показывает все линии как пересекающиеся, потому что, если два ребра имеют общую вершину, они вычисляются как всегда пересекающиеся, но мне этого не нужно. Мне удалось заставить его «работать», проверив вручную, имеют ли они общую вершину следующим образом:
function doLinesTrulyIntersect(aX1: number, aY1: number, aX2: number, aY2: number, bX1: number, bY1: number, bX2: number, bY2: number): boolean {
const sharesVertexes = (aX1 === bX1 && aY1 === bY1) ||
(aX1 === bX2 && aY1 === bY2) ||
(aX2 === bX1 && aY2 === bY1) ||
(aX2 === bX2 && aY2 === bY2);
return !sharesVertexes && doLinesIntersect(
aX1, aY1, aX2, aY2,
bX1, bY1, bX2, bY2
);
}
По сути, если два ребра имеют общую вершину, они не пересекаются.
Но всегда ли это будет работать? Логика заключается в том, что, поскольку если два ребра имеют одну и ту же вершину, то (поскольку это одна и та же точка) проверка на равенство с плавающей запятой должна работать, верно? В конце концов, под капотом те же самые детали.
Однако я знаю, что в целом проверка равенства двух плавающих запятых неверна и непоследовательна, но применимо ли это в данном случае?
Как вы реализовали doLinesIntersect? Вы вообще хотите, чтобы линии не пересекались, если они только соприкасаются, например (0,0, 2,0, 1,0, 1,1)? Откуда берутся координаты вершин? (ввод пользователя вручную? Они на самом деле находятся в дискретной сетке?) Насколько вероятно, что у вас есть вершины, которые вы сочтете равными?
Ответы 1
Если конечная точка X на одном ребре и конечная точка Y на другом ребре равны одной и той же точке P, то X равно Y. Объекты с плавающей запятой не являются мистическими объектами, которые изменяются спонтанно, и проверка на равенство сообщает, что две вещи равны, если и только если они равны.
Когда вы видите предостережения относительно сравнения чисел с плавающей запятой на предмет равенства, реальная проблема заключается в сравнении любых приближений, а не в чем-то конкретном, связанном с арифметикой с плавающей запятой. Предположим, существует некоторое идеальное число N и у нас есть два приближения A и B к N. Будут ли A и B равны? Вполне возможно, что нет, поскольку подготовка двух приближений разными способами часто приводит к разным результатам. Чтобы оценить процент населения США с голубыми глазами, вы можете взять 1000 человек и получить некоторый процент А, а другой человек может взять и взять 1000 других людей и получить некоторый процент Б. Даже если оба они являются приближениями N, они, вполне вероятно, не равны.
Причина, по которой это возникает как проблема в арифметике с плавающей запятой, заключается в том, что числа с плавающей запятой в первую очередь были разработаны для аппроксимации арифметики действительных чисел и в основном используются для этого. Обратите внимание, что именно арифметика с плавающей запятой приближается к арифметике с действительными числами. Числа с плавающей запятой — это настоящие действительные числа (их подмножество). В числах нет ничего приблизительного или шаткого: каждое число с плавающей запятой представляет собой ровно одно действительное число. Когда вы присваиваете переменной с плавающей запятой число с плавающей запятой, оно сохраняет это число. Оно не меняется и не становится приблизительным.
Это процесс вычислений с числами с плавающей запятой, который приводит к приближениям и ошибкам округления: Большинство операций с плавающей запятой, включая сложение и другие арифметические, научные функции и преобразование десятичных чисел в формат с плавающей запятой (включая десятичные числа в исходном коде). или программный ввод) — это операции, которые могут округлять свои результаты, чтобы они соответствовали формату с плавающей запятой.
Обратите внимание, что вышесказанное на самом деле справедливо для любого числового формата. Вычисления с числами с фиксированной точкой также дают округленные результаты, когда точный математический результат не умещается в формате. А вычисления с целыми числами также корректируются для соответствия целочисленному формату. 7/3 в целочисленной арифметике дает 2, ошибку, превышающую 1 часть из 10, тогда как 7./3. в «двойной точности» с плавающей запятой имеет ошибку менее 1 части в квадриллионе. Таким образом, целочисленная арифметика может быть намного хуже с точки зрения ошибок округления, чем арифметика с плавающей запятой. Причина, по которой люди с осторожностью относятся к округлению с плавающей запятой, а не к целочисленному округлению, связана с преобладающими способами использования этих форматов, а не с их внутренней подверженностью ошибкам.
Более того, если вы работаете с приближениями, все ваши результаты будут приблизительными. Вы можете получить очень большие относительные ошибки, вычитая два почти равных числа. Люди предупреждают о сравнении, потому что это одна из операций, которой новички могут злоупотреблять. Но каждый раз, когда вы работаете с приближениями в любом формате, вы должны осознавать, какие ошибки могут произойти и насколько велики они могут быть.
Все вышеперечисленное предназначено для того, чтобы дать вам контекст для определения того, на какие операции вы можете положиться. Если вы установите две конечные точки в одну и ту же точку, а затем сравните их, они будут сравниваться как равные.
Некоторые вещи, которые могут пойти не так в описанной вами проблеме:
- Во-первых, вы не устанавливаете две конечные точки в одну и ту же точку.
- Что-то меняет значение(я) одной или обеих конечных точек.
- Происходит сравнение между чем-то вычисленным и конечной точкой, а не между двумя конечными точками напрямую. Например, если у нас есть ребро XY и ребро YZ с общей конечной точкой Y, и какое-то программное обеспечение вычисляет место их пересечения, эти вычисления могут дать точку Y', которая немного отличается от Y.
@Райан, с
doLinesTrulyIntersect(0,0, 1,1, 0,0, 2,2)(оба края начинаются с 0,0 и по диагонали идут к N, N), вы действительно хотите быть непересекающимся?