points to line/curve conversion

[Mrinny]

Hi people,

I am doing this funky bit of code where i have the coordinates of several points making a single line... did some work to join the dots and kinda get the equation of a line/curve (cubic/quadratic beziers). This part is pretty much functioning well.:cool:

Now, where i want help is,:sweat:
Now i have like 2-3 or even more lines that are criss-crossing each other. I do not know which point belongs to which. Nor do i know how many lines there could be.

It is like a join the dots problem.

Luckily... yeah guys take a breather...:P
Luckily all the points are associated with each other strongly ie.right next to each other. So figuring out a pattern should not be too hard.

Any inputs are welcome... even tiny ideas that will fit in a larger picture.

Thanks in advance.:)

[Rashakil Fol]

Draw lines between every pair of points, order lines by number of points covered or nearly missed, remove lines with the fewest intersections until no more can be removed. Optimal solution not guaranteed. This is an n^2 log(n) algorithm though.

[Mrinny]

Thanks rashakil,

I have tried this method. When i have something as simple as a grid, this algorithm gives trouble because there are more than one valid lines.

Now, once i have all the lines figured out, say of a grid, the threshold value is different for different zones in the image.

I say image because i have plotted the dots as pixels on a bitmap in order to see the structure with the naked eye. That brings out the shape really well.

So, imagine i have a teapot... so many points near the top and so little near the base. Here the algo trips and deletes imp details.

Meanwhile an trying some vectorizing algorithms for bitmaps... since i have a b&w image anyway. This is working better.

[DavidB]

Are those two separate problems? Or are they the same problem?

You have created a single line joining the points and that seems to be working well.

Now you have several lines criss-crossing each other and you don't know which line to pick? Is this the same data set for which you have a working solution mentioned above? Does the data represent a known relation (in which case, perhaps you know it should have a quadratic, cubic, etc. relationship)?

Normally, if data contains errors, an experimenter might do a least-squares data fit. If the data does not contain errors, and a smooth line is desired going through all points, an experimenter might do a spline interpolation.

I am really not clear what you are trying to do.

[Mrinny]

Sorry David if my post seems unclear.

Yes you are right. I do have a functioning function for a single line joining points.
But, this is data regarding a single line in the form of dots. Like a graph or something showing a single jaggedly noisy reading but 'single' nonetheless.
Now that part works OK.

The moment i have a figure, ie. like an outline of say... an apple, I do not know where a line begins or ends

*Sometimes a single line forks into two
*Sometimes a line abruptly dies with no further traces
*Sometimes you follow along the curve and you find the same line continued with missing data.
*Or a new line is generated at some point.

So basically you are looking at a completely different data set here which is comprised of multiple criss-crossing lines (like you said). Now my simplistic "one line to fit all" thing doesn't work anymore. This is a more sophisticated problem

Actually i am a bit bad with the programming jargon coz i am not actually a "programmer". Just started programming as a hobby and have steered clear of the conventional training available.

Cheers!