Good day. I have an array with the coordinates of the contour of the object, the coordinates in the array in a random order. It is necessary to arrange the elements in such a order that when connecting the points, a closed contour would turn out (a continuous line). Tell me how this can be implemented, or in which direction to move? I find the contour of the object as follows

//FIND LEFT EDGE OF COLOR AREA int LFillLoc = x; //the location to check/fill on the left while (true) { PixelsChecked[LFillLoc, y] = true; LFillLoc--; //de-increment counter bool ret = CheckPixel(LFillLoc, y, imgBrush, startcolor); if (LFillLoc <= 0 || !ret || (PixelsChecked[LFillLoc, y])) break; //exit loop if we're at edge of bitmap or color area } LFillLoc ++; //FIND RIGHT EDGE OF COLOR AREA int RFillLoc = x; //the location to check/fill on the left while (true) { PixelsChecked[RFillLoc, y] = true; RFillLoc++; //increment counter bool ret = CheckPixel(RFillLoc, y, imgBrush, startcolor); if (RFillLoc >= bmpsize.Width || !ret || (PixelsChecked[RFillLoc, y])) break; //exit loop if we're at edge of bitmap or color area } RFillLoc --; //START THE LOOP UPWARDS AND DOWNWARDS //ptr = (int)bmpsize.Width * (y1) + x; for (int i = LFillLoc; i <= RFillLoc; ++i) { //START LOOP UPWARDS //if we're not above the top of the bitmap and the pixel above this one is within the color tolerance if (y > 0 && CheckPixel(i, y - 1, imgBrush, startcolor) && !PixelsChecked[i, y - 1]) LinearFloodFill4(i, y - 1, bmpsize, startcolor, imgBrush); //START LOOP DOWNWARDS if (y < (bmpsize.Height - 1) && CheckPixel(i, y + 1, imgBrush, startcolor) && !PixelsChecked[i, y + 1]) LinearFloodFill4(i, y + 1, bmpsize, startcolor, imgBrush); } bool CheckPixel(int x, int y, Color[] imgBrush, Color original) { int index = (int)imagerender.Size.Width * (y) + x; bool ret = true; if (30 * Math.Pow((imgBrush[index].R - original.R), 2) + 59 * Math.Pow((imgBrush[index].G - original.G), 2) + 11 * Math.Pow((imgBrush[index].B - original.B), 2) > sl) { position.Add(index); // координата контура ret = false; } return ret; }

The Magic Wand tool in Photoshop.

  • 3
    Well, the closed line will work out anyway :) As I understand it, it’s more important to you - without self-intersections ... But! The task is ambiguous. You can't draw here ... Take points (0,0) - (0,2) - (2,2) - (3,1) - (4,2) - (6,2) - (6,0) - (0,0). Circuit? Circuit. But (0,0) - (0,2) - (2,2) - (4,2) - (6,2) - (6,0) - (3,1) - (0,0) - also contour, but different and in a different ordering ... How to be? In short, the task must be set more strictly. You are not exactly interested in the convex hull of a set of points ? - Harry
  • 3
    Not understood. You don’t care what the result is the contour, the main thing is that there are no self-intersections? Or how? In the general case, it is impossible to unambiguously restore the original polygon from a random placer of its vertices, except for cases when there is an additional. Innovation. For example, if it is known that the polygon is convex. But you haven't said anything in the condition. So what you need to do. - AnT
  • 3
    Um ... What kind of image are you going to use the “magic wand tool in Photoshop” to an unordered vertex set ??? And what does he have to do with it? - AnT
  • If you need to find the contour of an object by its raster image, then what does the question in question do "an array with the coordinates of the contour of the object, coordinates in an array in random order"? Where is the connection? - AnT

3 answers 3

If you need to build an arbitrary simple N-gon on this set of randomly mixed N vertices, then one of the elementary solutions of the problem is simply to select an arbitrary vertex of the polygon as the “center” (vertex O), and then perform a radial sweeping of the plane with the ray emerging from the vertex O - like a radar beam. (Assume that sweeping is performed in the angle range [0, 360) counterclockwise, although the direction and the starting angle do not play a role.)

The first vertex detected by our "ray of radar" connects to the point O, and the rest to the previous detected vertex. The last detected vertex is connected to the point O, thereby closing the polygon.

If there are several vertices on a ray of a radar, you can add them in the order of distance from O or approach to O. In this case, a small subtlety is that on the very first ray you should always add points in the order of distance from O, but at the very last, in order of approaching O.

enter image description here

Such an algorithm will construct a polygon of a special class - a star-shaped (star-shaped?) Polygon. Inside or on the border of a star-shaped polygon there is a point (points) from which the entire interior of the polygon is viewed.

    It is already possible for UWP to use both EmguCV and OpenCV , including all the contour functions available. To draw an outline (as written in the title) - you need to use the drawContours function

    The description of the original problem does not quite correspond to the title, in general, the task is ambiguous, as the proposed AnT algorithm for solving it (different contours can be obtained when going around the beam clockwise and against).

      If you are engaged in essentially image processing (otherwise where did this task come from?), It makes sense not to build a bicycle, but to use the ready and already “adult” OpenCV framework. It has a ready-made functionality for finding the contours of objects .

      The only difficulty is: OpenCV is a native framework, so you need either your own C ++ / CLI wrapper, or you can use a ready-made Emgu CV .

      • Yes, OpenCV is a good thing, but not yet under uwp Emgu CV. I myself can not write .. - Ivan