Calculate intersection of two lines using integers only

Question

I can quite easily calculate the point of intersection given two lines. If I start with two vertices:

(x1,y1)
(x2,y2)

I can calculate the slope by doing (y1-y2)/(x1-x2), and then calculating the intercept

y1 - slope * x1

Then do that again, so I have to sets of slope and intercept, then just do:

x = (intercept2 - intercept1) / (slope1 - slope2)
y = slope1 * x + intercept1
(disclaimer: this might not even work, but i've gotten something very close to it to work, and it illustrates my general technique)

BUT that only works with data types with decimals, or non integral. Say the vertices are:

(0,1)
(10,2)

To calculate the slope would result in (1-2)/(0-10), which is -1/-10 which is not 1/10, it is 0.

How can I get code that yields a valid result using only integers?

Edit: I can't use floats AT ALL!. No casting, no nothing. Also, values are capped at 65535. And everything is unsigned.

Answer 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.

Answer 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.

Answer 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.

Answer 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))
}