Calculate intersection of two lines using integers only

Question 1

In high school when subtracting fractions, our teachers taught us to find a common denominator

So 1/4 - 1/6 = 3/12 - 2/12 = 1/12

So do the same with your slopes.

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

I hope I got that right.

Question 2

Hm..
(0,1)
(10,2)
and (y1-y2)/(x1-x2). Well, this is the description of one line, not the intersection of
two lines.
As far as I remember lines are described in the form of x * v with x an skalar and v be a
vector. Then it's
x * (0,1) = v2 and
x * (10, 2) = v2.
therefore the lines only intersect if exactly one solution to both equitions exist,
overlap when there are infinitive numbers of solutions and don't intersect when they are
parallel.
http://www.gamedev.net/topic/647810-intersection-point-of-two-vectors/
explains the calcuclation based on the dot - product.

Question 3

Input: line L passing thru (x1, y1) and (x2, y2), and line M passing thru (X1, Y1) and (X2, Y2)

Output: (x, y) of the intersecting point of two lines L and M

Tell Wolfram Alpha to solve y = (y1-y2)/(x1-x2)*(x-x1)+y1 and y = (Y1-Y2)/(X1-X2)*(x-X1)+Y1 for x, y to get this solution:

http://www.wolframalpha.com/share/clip?f=d41d8cd98f00b204e9800998ecf8427e3at5u9evl8

But I have no idea on how to write a program to implement the above solution for your calculator with only uint16_t ALU.

Question 4

Thanks to Graham Toal's answer, below is a primitive Rust implementation of the linked C code in their answer, modified to return the point of intersection for the complete line, as opposed to the line segment. It doesn't use much Rust-specific magic so should be reasonably easy to port to other languages.

The function returns a Point where the Lines intersect, if at all, and a flag denoting whether the intersection point lies on both intersected lines (true) or not (false).

/// 2D integer point
struct Point {
    /// The x coordinate.
    pub x: i32,

    /// The y coordinate.
    pub y: i32,
}

/// Line primitive
struct Line {
    /// Start point
    pub start: Point,

    /// End point
    pub end: Point,
}

/// Check signs of two signed numbers
///
/// Fastest ASM output compared to other methods. See: https://godbolt.org/z/zVx9cD
fn same_signs(a: i32, b: i32) -> bool {
    a ^ b >= 0
}

/// Integer-only line segment intersection
///
/// If the point lies on both line segments, the second tuple argument will return `true`.
///
/// Inspired from https://stackoverflow.com/a/61485959/383609, which links to
/// https://webdocs.cs.ualberta.ca/~graphics/books/GraphicsGems/gemsii/xlines.c
fn intersection(l1: &Line, l2: &Line) -> Option<(Point, bool)> {
    let Point { x: x1, y: y1 } = l1.start;
    let Point { x: x2, y: y2 } = l1.end;
    let Point { x: x3, y: y3 } = l2.start;
    let Point { x: x4, y: y4 } = l2.end;

    // First line coefficients where "a1 x  +  b1 y  +  c1  =  0"
    let a1 = y2 - y1;
    let b1 = x1 - x2;
    let c1 = x2 * y1 - x1 * y2;

    // Second line coefficients
    let a2 = y4 - y3;
    let b2 = x3 - x4;
    let c2 = x4 * y3 - x3 * y4;

    let denom = a1 * b2 - a2 * b1;

    // Lines are colinear
    if denom == 0 {
        return None;
    }

    // Compute sign values
    let r3 = a1 * x3 + b1 * y3 + c1;
    let r4 = a1 * x4 + b1 * y4 + c1;

    // Sign values for second line
    let r1 = a2 * x1 + b2 * y1 + c2;
    let r2 = a2 * x2 + b2 * y2 + c2;

    // Flag denoting whether intersection point is on passed line segments. If this is false,
    // the intersection occurs somewhere along the two mathematical, infinite lines instead.
    //
    // Check signs of r3 and r4.  If both point 3 and point 4 lie on same side of line 1, the
    // line segments do not intersect.
    //
    // Check signs of r1 and r2.  If both point 1 and point 2 lie on same side of second line
    // segment, the line segments do not intersect.
    let is_on_segments = (r3 != 0 && r4 != 0 && same_signs(r3, r4))
        || (r1 != 0 && r2 != 0 && same_signs(r1, r2));

    // If we got here, line segments intersect. Compute intersection point using method similar
    // to that described here: http://paulbourke.net/geometry/pointlineplane/#i2l

    // The denom/2 is to get rounding instead of truncating. It is added or subtracted to the
    // numerator, depending upon the sign of the numerator.
    let offset = if denom < 0 { -denom / 2 } else { denom / 2 };

    let num = b1 * c2 - b2 * c1;
    let x = if num < 0 { num - offset } else { num + offset } / denom;

    let num = a2 * c1 - a1 * c2;
    let y = if num < 0 { num - offset } else { num + offset } / denom;

    Some((Point::new(x, y), is_on_segments))
}