4
$\begingroup$

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!

3 Answers 3

3

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.

  • 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.2010-09-23
  • 0
    I was talking about equation 9 in that link, but the three parallel lines "intersecting at infinity" works too. :)2010-09-23
  • 0
    Thanks for the info. I ended up using this very approach.2010-09-23
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.

  • 0
    Thanks. Im trying something different here, and it's not working, so i'll check out your suggestion!2010-09-23
  • 0
    Looks like 18 "line evaluations" to me.2010-09-23
  • 0
    Yup, they were :)2010-09-23
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.

  • 1
    Agreed, the "Unix philosophy" works well in this case: keep the concurrency test and the routine for taking three lines at a time separate.2010-09-23
  • 0
    Thanks, that's exactly what I did. As I just needed to know, if there are at least 3 lines that intersect at a single point, this method worked out quite well.2010-09-23