5

I've got a programming exercise I need to do, but I just can't figure out the math part.

I need to check if $3$ of $6$ lines intersect in the same point. I am given the equation $ax+by=c$, and I input random numbers in $a,b,c$. How would I go about solving this mathematically?

Thanks!

Vincent
  • 2,329
Janis Peisenieks
  • 229

3 Answers3

4

You're trying to check for the condition of concurrency of three lines; the last determinant formula involving the coefficients of your three lines in that link may be of help.

Once you've shown that your three lines are concurrent, take any two of the three and solve as simultaneous equations (two equations in two unknowns) to get the coordinates of the intersection point.

J. M. ain't a mathematician
  • 75,051
  • 1
    If you check for concurrency of 3 lines using the determinant formula at the link in the answer above, note that the description involves writing the equation of a line in homogeneous coordinates. The line ax + by = c in this environment would be al + bm - cn = 0. If exactly two of the lines are parallel (but distinct) then one will be certain the the determinant will not be zero. If the three lines are distinct but all three parallel then the determinant will be zero because the condition stated involves concurrency in the "real projective plane" and three parallel lines "meet" at infinity. – Joseph Malkevitch Sep 23 '10 at 01:02
  • I was talking about equation 9 in that link, but the three parallel lines "intersecting at infinity" works too. :) – J. M. ain't a mathematician Sep 23 '10 at 01:21
  • Thanks for the info. I ended up using this very approach. – Janis Peisenieks Sep 23 '10 at 07:59
1

HINT:$\;$ Divide and conquer. $\:$ Split the lines into two sets of three lines. Compute the intersection points of each set (at most three). If either intersection set has cardinality one then you're done. Else check if any intersection point from one set lies on any line in the other set. Total operation count: 6 line intersections and 6 line evaluations.

Note: if the lines need not be distinct then you need to make slight modifications to the above.

Bill Dubuque
  • 272,048
1

The first step to write a program is to break down a problem into small parts. I would do the following:

  1. Write a function to decide whether given three lines intersect at one point. J. M.’s answer gives some material to do this.
  2. Iterate over all combinations of three lines out of six.

If the program does not work, try to test the two parts separately. Smaller, simpler programs are easier to verify.

Community
  • 1
Tsuyoshi Ito
  • 2,018