Probem regarding a problem

[Teach25]

Given n points, how can I find how many different lines can be drawn through these points?

Thanks

[tkud]

Dude, try to post some code... you can't just throw a question or assignment at us to solve for you.

[Ancient Dragon]

It sounds like a math problem not a programming problem (combination theory). How many combinations are there in N values taken two at a time? If there were just 2 points, X and Y, there would be just one line. Given 3 points, X, Y, and Z, there would be 3 lines. etc. There must be a mathametical formula for that series, but I don't know what it would be. google for combination theory and you will find lots of mathametical models.

[Teach25]

The formula is n*(n-1) / 2 , where n is number of points. But I can't come up with a formula which deals with collinear points.

[Ancient Dragon]

In that case there would only be one line. If there are 10 points all in a straight line then it would only take a single line to intersect then all.

[Teach25]

But what if some are collinear and some aren't? For example, 3 points are collinear, but the fourth one isn't. Then the number of different lines is 4.

I would like a formula that deals with that case also.

[Ancient Dragon]

If you have four points, A, B, C and D, where the first three are in a straight line and the fourth one is not, then I suppose there could be 4 lines. You would probably have to solve the problem in several steps. First make a list of the points in a straight line (given enough points there may be more than one set of these). That may (or may not) reduce the value of N to the number of sets plus the number of points not in any of the sets. Now all you have to do is use that new value, say N1, in the formula you previously posted.

[edit]That's probably wrong, but will give you a starting place to think it out.[/edit]

[Lerner]

Here's a brute force method that should work. Make a list of all line segments using every 2 point combination and count them. These line segments represent all possible unique lines defined by the set of points. However points, or line segments, that are colinear need to be taken into account. To be colinear line segments must have the same slope. So calculate the slope for each line segment and group like ones together. But parallel line segments have the same slope eventhough they aren't colinear so you'll need to separate them into separate groups, too. Then, let's say you find a line for which you have x number of line segments contained within that line that are also found in your group of line segments. The number of unique lines defined by the set the points that was originally calculated will need to be decreased by x - 1 to account for the fact that several of the points/lines segments were colinear. Obviously, you can do the same for all lines for which you have found more than one line segment that are contained within that given line.

Given the speed with which calculations can be done, you can evaluate a very large number of points this way very fast. Is it as pretty as a neat little formula? No. But it should get the job done without any uncertainty.

[mrnutty]

>> Given n points, how can I find how many different lines can be drawn through these points

If thats the exact question then the answer is infinitely many solution.