5
$\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

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.

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

  • 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