program to count minimum number of straight lines that will cover all points on a plane

Question

I wanted a algorithm to find the minimum number of straight lines that will cover all the given points.

I searched the algorithm on the internet, by far only i found an article on geeksforgeeks which is slightly different, here their is a condition that all lines must pass through a single point, but my problem is that i have no point of refernce.

link to article=https://www.geeksforgeeks.org/minimum-lines-cover-points/

Answer 1

For a simple algorithm you can use my approach:

I. run a blob detector to separate shapes one from another.

II. once you have individual shapes run line detector to find longest lines.

1. Get first unused pixel
2. Find the point that is farthest away from pixel A by calculating the distance in pixels, considering the shorter of the horizontal and vertical distances.
3. Employ the Bresenham line algorithm to iterate from pixel A to pixel B. Check if all the pixels between A and B are present in the pixel set. If they are, a line has been detected.
4. If the pixels between A and B are not found, proceed to find the next farthest pixel and repeat the process.
5. If the distance between A and B is 2, then this constitutes a line.
6. If A==B then detect a pixel as the line.

The same process (with C++ code) is also described on my blog. I'm still missing the step III. This algorithm will tend to find horizontal lines first and only then move to search for vertical lines. This is good for raster as horz. lines are usually most optimized ones. But the algorithm will have troubles with crossroads. A crossroad can be drawn with only two lines or with one long and two short lines. The job of the algorithm is to find two lines solution. The way forward is by converting the problem to a graph theory problem, but I haven't had time yet to play with it.

Answer 2

You have an oracle which finds the minimum number of lines passing through all the points and a reference point in O(N). So you can iterate over all the points given, find the minimum number of lines for each of them and then take the minimum among all of those in O(N^2) time. More efficient approaches are here https://link.springer.com/chapter/10.1007/11758471_4 .

Answer 3

In general, you can assign any two points per line. So pick any two points, pass a line through them, pick next pair, pass a line, and so on. Last line my have only one point left and that’s OK - you can choose its direction arbitrarily (random or a fixed direction).

If any points are coincident, treat them as if they were just one point ie. any line passing though one of the points will pass through all of them.

When there are any groups of 3 or more collinear points, then you can as well pass one line through all, and you’d want to “eat up” the points in decreasing order of the size of a collinear set. So if you have a set of 3 collinear points and another of 10 collinear points, it makes most sense to be greedy I imagine, but perhaps some special cases could be devised where this is not the best approach.

In any case, it all depends on whether you’re solving a real problem or an imaginary one (aka homework). If it’s a homework problem then the solution will be vastly different from practical problems.

But in almost any application of the algorithm, the basic primitive you should implement is finding of collinear point sets, or equivalently partitioning a set of points into collinear subsets.

You’ll have to allow a non-zero width of the line that passes through points, since outside of synthetic examples, real point coordinates (obtained from physical data) will never exactly lie on a line, but may be very close - then it totally depends on the application whether a line 1micrometer wide is all you can allow vs a line 20metres wide.

The exact meaning of the term “width” as it applies to the line depends on the number of dimensions: it naturally is the width of a rectangle in 2D, becomes the diameter (thickness) of a cylinder in 3D, the and finally turns into the hyperdiameter of hypercylinders in 4- and more dimensional datasets.

In 2D the width is the length of a line segment swept along the primary line to create the rectangle, in 3D the width is the diameter of the circle swept along the primary line to create a cylinder, in 4D it is the diameter of a sphere sphere swept along the primary line creating a hypercylinder, and so on.

Now, because the meaning of the width is always the same: the maximum allowed distance from the line to the points it passes “through”, the algorithm easily scales to any number of dimensions: the distance is simply your chosen vector length metric, and this also can be parametrized depending on the application. The Eudlidean metric would be a good default, but nothing says that it is useful in all circumstances.

Finally, a lot will also depend on the particular vector space the points are in. You may naturally think of R^n, ie. vectors of real numbers, but that’s not even true when you use floating point numbers: those are not reals but rationals, so if you want to guarantee full accuracy, you will need to use a numerical library that can do exact arithmetic on rational numbers - internally this calls for variable precision integer support, and now you’re in for a delightful exploration of such topics. Basically, an algorithm at a high level must assume nothing about these details - they are the application-specific parameters. If you go for a generic application, using any particular type to represent vectors or their coordinates is a dead end and would make the algorithm only useful for very narrow range of applications. Eg. if you do it in floating point you will never get exact results, and simple changes to data like permuting the points (changing their order) will reclassify some points that were collinear as not collinear anymore - due to numerical errors. Exact arithmetic means that no numerical errors are introduced. You might do well to allow your algorithm enough flexibility to have such details implemented using eg. the cgal library. It has various kernels, including the exact kernel which can give answers to questions such as “is this point no farther from a line than given distance” in exact manner.

The algorithm you wish to work on is only superficially simple. The implementation details needed to make it useful for real world use are far from trivial and require a good grasp of the underlying mathematics. It is a very nice way to learn such mathematics along the work on the algorithm - some people (myself included) understand mathematics much better in an application context. I had a use for a similar algorithm and have had splendid time exploring the beauty of the mathematics involved in the implementation!

Practically none of geometric “algorithms” as presented on Code Project and similar sites have much practical use, since they are written with the mathematical depth of a high-school curriculum: a good starting point, but not something you can just plug in into a product without knowing enough maths to be able to articulate an argument that the limitations of the implementation, and specifically the inexact arithmetic that leads to different outputs based only on reshuffling of identical data (!!) is acceptable for the task at hand. It may we’ll be - mind you - but you do need to be able to articulate exactly why, and show examples where the algorithm gives unstable results and demonstrate that the overall application doesn’t suffer. Furthermore, you have to put it into the test suite, so that if something changes in your application that might silently assume that the results are stable as-if from an exact arithmetic implementation, the tests will fail.