Given n arbitrary points on the plane. It is necessary to combine all existing points with a closed broken line so that it does not have self-intersections. Input: A list of arbitrary coordinates of points on the plane. Output: A list of coordinates of points on the plane, which, when connected in series, form a closed polyline that has no self-intersections.

Closed due to the fact that the issue is too general fori1ton , Harry , iluxa1810 , Kromster , Denis participants . Nov 13 '16 at 18:23 .

Please correct the question so that it describes the specific problem with sufficient detail to determine the appropriate answer. Do not ask a few questions at once. See “How to ask a good question?” For clarification. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • one
    The task is not clearly formulated. Connect one broken line? Closed? not? maximum number of non-intersecting segments? In short, formulate the task more precisely ... - Harry
  • Olympics do you decide? - nick
  • perhaps meaning Delaunay Triangulation ru.wikipedia.org/wiki/… ? - Evgenii

1 answer 1

I will not write the code. Idea:

  1. find the point that will be exactly inside the convex hull (average for all coordinates for example)
  2. shift all coordinates so that the center is at (0,0). You can implicitly.
  3. Sort all the points first by the polar angle, with equality modulo
  4. Connect the dots starting from the very first in that order.
  5. Connect 1 with the last

Then the intersection is impossible at 1 corner (there is something modulo) And at different, because we immediately go to the nearest.

PS sort carefully) there are a lot of nasty tests for accuracy of calculations

  • I had a chance to find the extreme point of x-su and a top from it upwards and to the right to dance. Divide the points into two arrays: what do you see in y and the points that are lower than the starting point. first pass on the upper points and then on the lower, so that the other points gradually come to the first. but there are moments that one point "breaks" the line and everything is lame. you can tell if there is an algorithm, it is desirable to write, there is a line with coordinates and a point which is not on it. How to determine that the point lies under the pram. - Maxim Bondarenko
  • @MaximBondarenko can of course connect all points, first by x and then y. But you will not close the cycle. And if you need a cycle, then my decision is one of the few correct ones) - pavel
  • It does not work at 4 points on one straight line (however, in this case there is no solution, so it is not a completely counterexample). - VladD
  • @VladD is a single situation when the cycle is not closed - 3 or more points on 1 straight line, but there are no others. - pavel
  • @pavel I seem to understand your idea, though not immediately, we push through all the degrees of the angles from 0 to 360, then we will connect the points to increase the degree of the angle. - Maxim Bondarenko