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

Thanks

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

Jump to PostIt 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 …

tkud
0
Posting Whiz in Training

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

Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster

Teach25
0
Newbie Poster

Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster

Teach25
0
Newbie Poster

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
5,243
Achieved Level 70
Team Colleague
Featured Poster

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]

Edited
by Ancient Dragon because:
*
n/a *

Lerner
582
Nearly a Posting Maven

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.

Edited
by Lerner because:
*
n/a *

mrnutty
761
Senior Poster

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.

Broken Link

**You're trying to visit a URL that doesn't currently exist on the web.**
Most likely, a member posted a link a long time ago to a web page that has since been removed.
It's also possible that there was a typo when posting the URL.
We redirect you to this notice instead of stripping out the link to preserve the integrity of the post.