Hi
I have an array of Points. I KNOW that these points represent many lines in my page.
How can I find them? Do I need to find the spacing between clouds of points?
Thanks Jonathan
+1
A:
Maybe the Hough Transform is what you are looking for? Or a linear regression?
[EDIT] As it turns out the problem is to identify lines inside a list of 2d coordinates I would proceed this way.
A linear regression can only be used for making the best linear adjustment for a set of points, not to detect many lines. Maybe use hough to get roughly the lines, check if many points align on these lines. Have a look at the points left aside. Do they have to belong to a line?
Using an accumulator to determine the lines seems to me a good solution in general but if your points follow some relations, try to adapt the accumulator to it to make it fit better.
The problem definition is not so specific, it is difficult to tell exactly how to proceed. The use of an accumulator for such kind of problems seems a basis to me that must be kept.
At least the problem is interesting!
jdehaan
2009-09-30 19:26:36
I have tried HoughTransform, but it misses many lines...
2009-09-30 19:27:39
In the past I had to detect road signs inside pictures (which contain regular forms like triangles and circles, ...) It worked quite well. Your array of points is not an image, is it? I mean it is a set/list of 2D points coordinates or a picture?
jdehaan
2009-09-30 20:03:31
yes exactly.only points. Do you have C# code for that ?
2009-09-30 20:06:44
No I am sorry. I will try to formulate how I would proceed if I had to do the job in the response, as there is more place.
jdehaan
2009-09-30 20:21:43
I think this is an excellent case for the Hough Transform. If you are missing lines have you played with you bin radius? I suggest you look at AForge.NET http://code.google.com/p/aforge/ it's written in C# and is a brilliant image processing library (contains a Hough Transform implementation)
ParmesanCodice
2009-09-30 20:59:30
Question to jdehaan: what do you mean but an accumulator ? the hough transfom ?
2009-09-30 21:19:51
The accumulator is where you add the results of the transformations
jdehaan
2009-10-01 05:20:01
A:
This is the same as considering what are all the overlapping lines between 2 points.
Go over all point-to-point lines and convert it to a structure that contains:
a) the y intercept
b) the slope
c) the lower x-bound
d) the upper x-bound
Sort by y-intercept and slop.
Now you know that 2 lines can overlap only if they have the same y intercept and the same slope.
For each set of lines with the same y-intercept and slope, check if the x-bounds overlap. If they do then you don't have separate lines, you have 1 line with more than 2 points.
Handle vertical lines as a special case.
tster
2009-09-30 19:33:14