Determine the points from a set of coordinates that will form a line

[Kronos90]

I want to make a program that generates between 10 - 100 random coordinates on the Cartesian plane and it should find which points will form a line.

It should be a combination of at least four points that can form a line. To do this, I can find the slope between the four selected points to find out if they can form a line.

However, the hard part is how can I make a combination of all the points? I want to use the brute force method which finds all combinations of at least four points and then checks the slope between them to see if they can form a line.

Any advice as to how I can approach this problem e.g find the combinations efficiently will be appreciated.

[LB]

What line are you looking for? If you say any, what if there are 0 lines or more than 1 line?

If you are dealing with real numbers, brute force is the way to go. If you are dealing with integers, you can make some assumptions about the locations of points and make a more efficient algorithm.

[Kronos90]

The program generates random points (amount of points entered by user) and should find a combination of four points that can form a line.

The problem is that if I try to find all combinations of four points, it will take a long time. For example, the user enters 100 points as the input. So the total combination of four points/coordinates will be 100C4 which is 3,921,225 combinations that are possible and this takes a lot of for the program to compute.

So my question is that is there any other approach to brute force?

[LB]

You can assign points to grid sections and only search in grid sections that would contain points that line up with your current points - this will easily eliminate many other points.

[ne555]

http://docs.opencv.org/doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.html
Or you could transform each point in a line and then using an arrangement to find the intersections.

If you want to use a brute-force approach

for(int K=0; K<n; ++K)
   for(int L=K+1; L<n; ++L)
      for(int M=L+1; M<n; ++M)
         for(int J=M+1; J<n; ++J)
            test(K,L,M,J, points);

just keep in mind that all the lines that you find for the pair (K,L) are the same line.

Edit: using that property you may optimize the algorithm

std::map< pair, std::set<int> > line;
for(int K=0; K<n; ++K)
   for(int L=K+1; L<n; ++L)
      for(int M=L+1; M<n; ++M)
         if( aligned(K, L, M) ){
            line[K,L].insert(K); //excuse the syntax
            line[K,L].insert(L);
            line[K,L].insert(M);
         }

then you've got all the lines that are composed of 3 or more points, and by checking the size of the set you may filter them to 4 or more points.
the issue is that you would have repeated lines. If you have found that (K,L,M) is aligned, then you may have it in the map as (K,L), (K,M) and (L,M). You may find out the equivalences by checking the last two elements of the set.


> and then checks the slope
I'll recommend you to use the cross product instead

[coder777]

One idea would be:

Take an arbitrary first point.

First point:
Sort all other points according to the smallest distance to this point. Now check whether there are four or more points that have the same slope as the first -> second point. Either you have a line then eliminate those points or you eliminate the second point. Continue as long as there are points.

Second point:
Take the list without the first point and the found lined up point (if they cover at least 4 points). Proceed as first point.

[ne555]

> First point
> Sort all other points according to the smallest distance to this point.
¿what for?

> Second point
> Take the list without the first point and the found lined up point
you may only remove the "found lined up point" if they are aligned to the second point.

> Third point
there is no third point... ¿how do you generalize?
especially the "remove the found lined up point" part

[LB]

Really ugly code using my technique:
http://ideone.com/sWMvc4

[ne555]

@LB: you are dividing the space according to the diameter of the set.. That means that an scale operation would change the running time of the algorithm (however, the same lines remain, with the same scope, and the same points that form part of them)

(it could be considered a feature if instead of 'radius' you named it 'number_of_divisions')

You may also use a quadtree to perform the divisions. However, the limits for the problem (100) seems too small to justify it.


Also, again would recommend the use of the cross product instead of the slope to do the check

[LB]

Ah, yes I realized that changing the radius changed the running time. Good point - a better name would indeed be number of divisions.

I am only now taking Calc 3 and so I am not familiar with how cross product can be used in this situation, but I believe you.

[coder777]

@ne555
It's obviously a recursive. You're not willing to wrap your mind around algorithm which is perfectly fine with me.