0
$\begingroup$

I have series of points extracted from a regular grid, with their X/Y coordinates. A previous algorithm (that I cannot modified!) output a list of these coordinates, but the ordering of these point is random in regard to the scope of this problem as expressed byt the following python-style notation:

[ [X_O,Y_O], [X_M, Y_M], [X_D, Y_D], ... ]

Where X Y are the X and Y coordinates of each point. I am now trying to "order" them with the following logic (from point A to point R on the grid visualisation):

[ [X_A,Y_A], [X_B, Y_B], [X_C, Y_C], ... ]

Point ordering aim

The final aim being to plot a profile with the actual value on the Z grid. I have tried a "hacky" way by just identifying the neighbours of each point and ordering the one that have not been processed yet, but it is not reliable enough as I faced many artifacts.

Is there an algorithm I missed that is designed for that problem? I have done some research but I feel I am missing out something.

Thanks!

Improve this question
$\endgroup$
  • $\begingroup$ Could you explain a bit more what is meant by "the following logic". I do not really get the logic behind your ordering. Is point A always in the lowest row? Why does it have to be there? Do the empty cells in your picture also contain some data? Because you wrote "I series of points extracted...". Are the points stored in an array or something? $\endgroup$ – vydesaster Feb 28 '19 at 21:48
  • $\begingroup$ Thanks for your reply! I have the list of these points with their row/col coordinates. But the list is unordered: for example [ [X_O,Y_O], [X_M, Y_M], [X_D, Y_D], ... ]. What I aim for is the same list ordered form A to R: [ [X_A,Y_A], [X_B, Y_B], [X_C, Y_C], ... ]. I am editing the text. I am probably not using the correct vocabulary, is it clearer? $\endgroup$ – boris Mar 1 '19 at 8:49
  • $\begingroup$ Now it is much more clear. I am just missing one thing. What exactly makes point A the first point. Is point A e.g. the lowest value of something? You need something to identify the order. I am not quite common to Python but in C++ I would put the X and Y coordinate and the value which determines the order into a tuple and all tuples into a vector. Then let some basic sorting algorithm do the work for you. $\endgroup$ – vydesaster Mar 1 '19 at 13:57
  • $\begingroup$ Thanks! That's actually an issue! The actual format is in c++, I have three vector (X, Y and Z). The Z value is elevation and these point determine drainage basin boundaries. Point A will always be the lowest one, however there is no constrains on the others: elevation can increase or decrease along that line, which is what I'd like to visualise in a continuous way. Moreover the algorithm extracting the drainage basin is very optimised for that purpose and would be hard to modify. That's why I more looking for a geometrical approach if that makes sense? $\endgroup$ – boris Mar 1 '19 at 15:05
  • $\begingroup$ Is it supposed to be an oriented boundary? I remember reading about data structures fit for that in a computer graphics book. $\endgroup$ – Emil Mar 31 '19 at 21:22
2
$\begingroup$

This is the classic contour tracking problem, which is usually sovled with an algorithm by Pavlidis described in

Pavlidis: Algorithms for Grapics and Image Processing. pp. 129-165, Springer, 1982

A ready to use python function is available as contour_pavlidis in the Gamera framework. The C++ code of this implementation can be found on github, which is subject to the GNU GPL license.

Improve this answer
$\endgroup$
1
$\begingroup$

I think the easiest way in C++ would be to make a vector of tuple. std::vector< std::tuple< int, int, double>> This vector than contains the X and Y coordinate as well as the Z value as tuples. After that you can simply use sort(). If you store the Z value at the third place of the tuple, you need an extra function for sorting. Therefore I would suggest to put the value for which you need the sorting at the first place of the tuple. Have a look at this tutorial here. Hope this was what you were looking for.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks! I'll give it a go as soon as I can and let you know $\endgroup$ – boris Mar 4 '19 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.