Question/Feature request: sort order for closed contours

[uwezi]

When trying to trace a contour along a border on a map with the "automatic extraction" I get a nice and clear list of points on the border. The algorithm works beautifully, but no available sort order for the acquired data follows the closed line of the border in a sequential manner.

• "raw" puts most parts of the border in an increasing X sorting, which means that the points jump alternating between the northern and the southern side of the border
• "x" and "y" do as expected
• "nearest neighbor" appeared at first sight to do what I wanted, but seems to choke on some details... especially when tracing the contour with several hundred points.

[nbehrnd]

I had a similar problem today, where the continuity of the path along one direction is of importance. A solution to this is to skip the default identification (a.k.a. mask), and to use the pen tool instead, i.e., use the third extraction mode offered and follow e.g., with your mouse all around the frontier on the map. It helps if the underlying image is of high resolution, too.

Pen width, colour tolerance, and increments along abscissa and ordinate are as usual adjustable parameters available to you. As expected, the entries in the .cvs follow nicely the direction of the path chosen by you. Because of using the pen tool collects the points continuously along your path, it is not problematic if the path actually intersects with itself in a loop.

For displaying the result later, the more important question may be if your program to plot the path then attempts any kind of sort, or not. If it sorts the x (and thus the y attributed, too, like the plotly-bridge offered here), then no, you won't recognize the perimeter any more. In fact, similar to what is already described by you.

Thus, I reopened the saved the project's archive, intentionally used the increments delta-x and delta-y so tiny that even formally I instructed gnuplot to plot a scatter plot with small dot style dots the path was recognizable enough, without joining the dots by a line. LibreCalc may plot the tiny dots scatter plot via a GUI, too if you prefer. Note both gnuplot as well as spreadsheet still may distort the representation if not instructed to plot abscissa and ordinate in the same scale, too.

[uwezi]

thanks, that sounds very promising! I will try it out.

I was using the coordinates in my own python script afterwards - so I have full control over possible sorting issues which happen, once I have the extracted points.

Except that it doesn't seem to work for me. I traced the contour of a border with the PEN tool clockwise starting from the western most point, but the generated list in "RAW" sort order is almost perfectly sorted by X coordinates, alternating between the northern and southern periphery.

If it matters, I am using the 4.2 Windows-binary, Windows 10

[nbehrnd]

This back-and-forth is expected, because the increments along x and y are along the four reference points set for the 2D map. Just find a plotter accepting the extracted data as they are (i.e., without any sort), and plot them as fine scatter plot.

Example, the perimeter of a Canadian province, a coarse analysis by the digitizer and large dots as crosses:

and the same analysis requesting the points to be joined by lines instead -- a not at all easily recognizable perimeter:

The data used -- including the archive of the project -- is attached below as a .zip. If opting for gnuplot (platform independent, tons of documentation and example at gnuplot.info), the minimal code to enter in gnuplot's interface to get the pointed map of the Canadian province follows a pattern of

set terminal pngcairo
set output "Canada_province.png"
set size ratio -1
plot "Canada2.csv" with points

The explicitly set command set size ratio -1 instruction, by the way is responsible to scale the kilometer in vertical equal to the horizontal direction here. Otherwise, gnuplot will fall back to its default 4:3 ratio causing map distortions otherwise (equally) seen in spreadsheets like Excel, LibreCalc, gnumeric, etc. pp. If wished, other output formats than .png may be selected by opting for an other «terminal» (gnuplot's parlance of the output generator), e.g., .svg, .[e]ps, .pdf.

example_in_canada.zip

[uwezi]

I am not planning to "plot" the points afterwards, I want to use them for other purposes. And for this reason I would like to have them sorted along the curve, also with curves which are themselves not monotonous in either X or Y, possibly even self-intersecting like a figure-8 path.

So then this is a FEATURE REQUEST rather than a question whether I understood all features of the program...

[nbehrnd]

Not the solution you aim for, but you may split the perimeter into sections where, in respect to the outer coordinate system, you run either from left to right, or from right to left. And apply the pen tool on these using multiple datasets a project archive may contain (Dataset -> Add Datasets on the left hand side). A geographical map of course may require more work than only splitting the upper and lower hysteresis or a cyclovoltagram, a suggestion already filed earlier in 2016. And the overall-direction should match the one in the sections, too.

[ankitrohatgi]

Sorting unordered points along the perimeter is tricky and nearest neighbor is a crude solution for this - I know it doesn't always work. A commonly used alternative is to sort by the polar angle, but it only works ok if you can guarantee that the polygon is convex. For non-convex/unknown shapes, it is hard to find a unique perimeter. The reply here captures this quite well: https://scicomp.stackexchange.com/questions/31069/a-robust-algorithm-to-sort-a-non-convex-polygon-vertices

What you are really wanting is a proper vectorization capability that doesn't just work off of a crude list of points. I know many softwares do this, but I haven't explored this area much myself (e.g. https://desktop.arcgis.com/en/arcmap/latest/extensions/arcscan/what-is-arcscan-.htm)

[uwezi]

Sorting unordered points along the perimeter is tricky

Thank you very much for this answer. I was assuming somehow that the digitizer would "crawl" along the lines. I now understand that this is not the case - still I highly appreciate your work and your software!