Рассчитать пересечение двух линий, используя только целые числа
Я могу довольно легко вычислить точку пересечения, учитывая две линии. Если я начну с двух вершин:
(x1,y1)
(x2,y2)
Я могу рассчитать наклон, выполнив (y1-y2)/(x1-x2)и затем вычисление перехвата
y1 - slope * x1
Затем сделайте это снова, поэтому я должен установить наклон и перехват, а затем просто сделать:
x = (intercept2 - intercept1) / (slope1 - slope2)
y = slope1 * x + intercept1
(отказ от ответственности: это может даже не работать, но я получил кое-что очень близкое к этому, и это иллюстрирует мою общую технику)
НО это работает только с типами данных с десятичными или нецелыми. Скажем, вершины:
(0,1)
(10,2)
Чтобы вычислить наклон, нужно (1-2)/(0-10), который -1/-10 который не 1/10, это 0,
Как я могу получить код, который дает правильный результат, используя только целые числа?
Изменить: я не могу использовать поплавки СОВСЕМ!. Нет кастинга, нет ничего. Кроме того, значения ограничены 65535. И все без знака.
Решение
В старшей школе, вычитая дроби, наши учителя учили нас находить общий знаменатель
Итак, 1/4 — 1/6 = 3/12 — 2/12 = 1/12
Так что сделайте то же самое со своими склонами.
int slope1 = n1 / d1; // numerator / denominator
int slope2 = n2 / d2;
// All divisions below should have 0 for remainder
int g = gcd( d1, d2 ); // gcd( 4, 6 ) = 2
int d = d1 * d2 / g; // common denominator (12 above)
int n = (d/d1) * n1 - (d/d2) * n2; // (1 in 1/12 above)
// n1/d1 - n2/d2 == n/d
Надеюсь, я понял это правильно.
Другие решения
Хм ..
(0,1)
(10,2)
и (y1-y2) / (x1-x2). Ну, это описание одной линии, а не пересечение
две строки.
Насколько я помню, строки описываются в виде x * v, где x — скаляр, а v —
вектор. Тогда это
х * (0,1) = v2 и
х * (10, 2) = v2.
поэтому линии только пересекаются, если существует ровно одно решение для обоих уравнений,
перекрываются при наличии бесконечного числа решений и не пересекаются, когда они
параллельно.
http://www.gamedev.net/topic/647810-intersection-point-of-two-vectors/
объясняет расчет на основе точечного произведения.
Вход: линия L, проходящая через (x1, y1) а также (x2, y2)и линия М, проходящая через (X1, Y1) а также (X2, Y2)
Выход: (x, y) точки пересечения двух прямых L и M
Скажи Вольфраму Альфе solve y = (y1-y2)/(x1-x2)*(x-x1)+y1 and y = (Y1-Y2)/(X1-X2)*(x-X1)+Y1 for x, y чтобы получить это решение:
Но я не знаю, как написать программу для реализации вышеуказанного решения для вашего калькулятора только с uint16_t ALU.