There is an array of points X {x,y} that form a closed smooth contour ( aerodynamic profile ). The points are initially located in the array chaotically and unevenly. Prompt sorting algorithm that allows you to arrange the points in a logical order.

UPD. The limit of comments ((. The points on the profile are located approximately like this (in most cases)

alt text

those. in places with a large radius of curvature less often and vice versa. Pitch points can be both small and relatively large. (@alexz)

    4 answers 4

    Or I misunderstood the condition or there is no unambiguous solution. For example, in the picture below, points can be located at least in 2 different orders: Example

    UPD: if you assume that the profile is convex, then you can simply find the convex hull of the set (using one of the algorithms from the Wikipedia article at the end), and then take the points in the order in which they appear in the convex hull.

    • A little I did not fully described. I do not remember how to call it correctly (this kind of contour), but in my case such a situation cannot be like. Contours are [aerodynamic profile] [1]. [1]: en.wikipedia.org/wiki/… - Alexey Kotov
    • one
      All these profiles, except for Zhukovsky, are convex. Did you mean it? - dzhioev
    • Yes Yes. That's right - Alexey Kotov
    • The idea with the shell is interesting. But what about profiles like that of Zhukovsky? Or at least how to distinguish such profiles? - Alexey Kotov

    For me - to start it is enough to sort by ascending coordinates. For example, by x. If there are points with the same x coordinate - sort them by y. Now, if you connect them, you get a broken line. Zigzag. And now you need to figure out how to split the points into two classes - into one aerodynamic profile curve and into the other. While there is no idea how to do it.

    If the figure is steadily convex - it is possible to use triangulation algorithms. They just make an array of "edges" at the exit, and then you can choose the necessary ones among them.

    • With triangulation, it is a little incomprehensible how to choose the edges then. After triangulation, it seems to me, the task is not much simpler. But with the selection of the coordinates of course you can think of something. With flat convex and convex everything is clear. The first half of the array is sorted by x && y above the baseline, the second half is y below or on the line. And what about convex-concave (same Zhukovsky)? What suggestions? - Alexey Kotov
    • Complex issue. You can try to build a contour, taking an arbitrary point, find the nearest one. Then find the closest one to either of the two, and place it in the head of the list or in the tail depending on the distance to the head / tail. Then repeat for the rest (find the closest one to the last one found). Etc. It strongly depends on the source data (for example, how points are selected, which profile, etc.) - alexlz
    1. Find the center. The point with coordinates x0 = average X of all points, y0 similarly. Option: (xmin + xmax) / 2, and y as well
    2. Calculate the angle between the center and point (center in the polar coordinate system) in the range from 0 to 2pi (or -pi to pi)
    3. Sort in the desired order of traversal

    But this is only for convex figures.

    An example of a wrong order when going around counterclockwise (for a concave section) The profile is of course from a cucumber, but here it is alas.

    alt text

    Here is one of the problems of automatic building

    alt text

    • I think this is the closest thing to the truth. Suitable for convex-concave profiles if properly identify the center. If the center is inside the profile (even convex-concave), then the angle from the "right" point to the point will constantly increase (or decrease). The abscissa is simple. And how to find the ordinate center so that it is inside the profile? - Alexey Kotov
    • one
      This is hardly a good idea. Because with the center inside the profile, some points of the lower concave part will go in the wrong order. - alexlz
    • And what is the wrong order? And why some points? What are some? If the points will go in the order of "clockwise or against" starting from the point with Xmax, then this is ideal. Since then it is still necessary to draw (sometimes with a spline). - Alexey Kotov
    • Bliiin. Yes. My apologies! I am increasingly inclined to think that you first need to select the lower and upper arcs, and sort separately for each, and then sculpt the common array in some way. Any ideas? - Alexey Kotov
    • Is the problem global or need a solution to a specific problem? Probably it is necessary "to correct something in conservatory". Those. How do you get the coordinates of the points? Maybe something there? Assume that the points are cleaved from the drawing on a regular basis (well, except for inserting previously missed during removal). - alexlz
    1. Take an arbitrary point.
    2. We delete from the general list of unparsed points, put in the output list.
    3. Find the point that is closest to the source. We use the usual Cartesian distance measure.
    4. We delete it from the list of unparsed, put it in the output list.
    5. If there are still unparsed points - go to p.3.

    According to the comments and discussions, we assign the position :-):

    The classical spline of one variable is constructed as follows: the domain of definition is divided into a finite number of segments, on each of which the spline coincides with some algebraic polynomial. The maximum degree of the polynomials used is called the degree of the spline. The difference between the degree of the spline and the resulting smoothness is called a spline defect. For example, a continuous polyline is a spline of degree 1 and defect 1.

    If a simple Cartesian measure turns out to be insufficient, you can use the good old splines. Notice, I do not complicate the task ... we build a spline for combinations of 4 nearest points and choose the one for which the degree of the slide is minimal. But we must begin with one of the ends of the figure - so that we immediately begin to move along one of the lobes - the upper or lower.

    • The idea is good. But (again, my mistake in the question), the points may not be very evenly spaced. And the necessary next point may be some further "unnecessary" in the distance. - Alexey Kotov
    • In my opinion, if this is a smooth contour, it is unlikely :-) Of course, the effectiveness of the method depends largely on the sampling rate. If we are talking about the shape of the profile, then you need to ensure that in areas with small thickness readings are taken more often - at least one and a half times more often than the thickness of the profile. - Vladimir Vodolazkiy 5:53 pm
    • It is a fact. Some sections may be close to a straight line - in these places points are rarely located. - Alexey Kotov