Примечание. Заголовок этого вопроса должен быть «Loop It», но поскольку заголовок должен содержать не менее 15 символов, существуют некоторые невидимые пробелы. Это примечание таково, что вызов можно искать.

Вызов

Учитывая конечный список уникальных целочисленных точек на плоскости, найдите многоугольник, вершинами которого являются именно те точки, которые не пересекаются.

Детали

• В качестве входных данных вы можете взять, например, два списка с координатами x и y или список пар.
• Входной список содержит не менее 3 баллов.
• Обратите внимание, что это означает, что никогда не бывает уникального решения.
• Можно предположить, что список входных данных не является коллинеарным (точки не могут содержаться в одной строке), это означает, что на самом деле существует такой несамопересекающийся многоугольник.
• Углы в каждой вершине произвольны, в том числе 180 °.
• Для ввода длины n, вывод должен быть перестановкой (p1,p2,p3,...,pn)из (1,2,3,...,n)которых k-го входа pkпредставляет собой pую точку в списке ввода. Это означает, что у нас есть строка от p1до p2, строка от p2до и p3т. Д., А также строка от pnдо p1. (Вы также можете использовать индексы, основанные на 0.) В качестве альтернативы вы можете просто вывести список точек ввода в правильном порядке.

Примеры

Допустим, у нас есть точки, [(0,0),(0,1),(1,0),(-1,0),(0,-1)]и мы хотим представить следующий путь:

Это означает, что мы выведем список [5,1,4,2,3]

Вот еще одно предложение, чтобы попробовать (я рекомендую смотреть на соответствующие участки, чтобы проверить цели.)

Triangle
[(0,0),(0,1),(1,0)]

S-Curve
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(2,0),(2,1),(2,2),(2,3),(2,4),(3,4),(4,0),(4,1),(4,2),(4,3),(4,4)]

L-Shape
[(4,0),(1,0),(3,0),(0,0),(2,0),(0,1)]

Menger Sponge
[(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(9,1),(10,1),(11,1),(12,1),(13,1),(14,1),(15,1),(16,1),(17,1),(18,1),(19,1),(20,1),(21,1),(22,1),(23,1),(24,1),(25,1),(26,1),(27,1),(1,2),(3,2),(4,2),(6,2),(7,2),(9,2),(10,2),(12,2),(13,2),(15,2),(16,2),(18,2),(19,2),(21,2),(22,2),(24,2),(25,2),(27,2),(1,3),(2,3),(3,3),(4,3),(5,3),(6,3),(7,3),(8,3),(9,3),(10,3),(11,3),(12,3),(13,3),(14,3),(15,3),(16,3),(17,3),(18,3),(19,3),(20,3),(21,3),(22,3),(23,3),(24,3),(25,3),(26,3),(27,3),(1,4),(2,4),(3,4),(7,4),(8,4),(9,4),(10,4),(11,4),(12,4),(16,4),(17,4),(18,4),(19,4),(20,4),(21,4),(25,4),(26,4),(27,4),(1,5),(3,5),(7,5),(9,5),(10,5),(12,5),(16,5),(18,5),(19,5),(21,5),(25,5),(27,5),(1,6),(2,6),(3,6),(7,6),(8,6),(9,6),(10,6),(11,6),(12,6),(16,6),(17,6),(18,6),(19,6),(20,6),(21,6),(25,6),(26,6),(27,6),(1,7),(2,7),(3,7),(4,7),(5,7),(6,7),(7,7),(8,7),(9,7),(10,7),(11,7),(12,7),(13,7),(14,7),(15,7),(16,7),(17,7),(18,7),(19,7),(20,7),(21,7),(22,7),(23,7),(24,7),(25,7),(26,7),(27,7),(1,8),(3,8),(4,8),(6,8),(7,8),(9,8),(10,8),(12,8),(13,8),(15,8),(16,8),(18,8),(19,8),(21,8),(22,8),(24,8),(25,8),(27,8),(1,9),(2,9),(3,9),(4,9),(5,9),(6,9),(7,9),(8,9),(9,9),(10,9),(11,9),(12,9),(13,9),(14,9),(15,9),(16,9),(17,9),(18,9),(19,9),(20,9),(21,9),(22,9),(23,9),(24,9),(25,9),(26,9),(27,9),(1,10),(2,10),(3,10),(4,10),(5,10),(6,10),(7,10),(8,10),(9,10),(19,10),(20,10),(21,10),(22,10),(23,10),(24,10),(25,10),(26,10),(27,10),(1,11),(3,11),(4,11),(6,11),(7,11),(9,11),(19,11),(21,11),(22,11),(24,11),(25,11),(27,11),(1,12),(2,12),(3,12),(4,12),(5,12),(6,12),(7,12),(8,12),(9,12),(19,12),(20,12),(21,12),(22,12),(23,12),(24,12),(25,12),(26,12),(27,12),(1,13),(2,13),(3,13),(7,13),(8,13),(9,13),(19,13),(20,13),(21,13),(25,13),(26,13),(27,13),(1,14),(3,14),(7,14),(9,14),(19,14),(21,14),(25,14),(27,14),(1,15),(2,15),(3,15),(7,15),(8,15),(9,15),(19,15),(20,15),(21,15),(25,15),(26,15),(27,15),(1,16),(2,16),(3,16),(4,16),(5,16),(6,16),(7,16),(8,16),(9,16),(19,16),(20,16),(21,16),(22,16),(23,16),(24,16),(25,16),(26,16),(27,16),(1,17),(3,17),(4,17),(6,17),(7,17),(9,17),(19,17),(21,17),(22,17),(24,17),(25,17),(27,17),(1,18),(2,18),(3,18),(4,18),(5,18),(6,18),(7,18),(8,18),(9,18),(19,18),(20,18),(21,18),(22,18),(23,18),(24,18),(25,18),(26,18),(27,18),(1,19),(2,19),(3,19),(4,19),(5,19),(6,19),(7,19),(8,19),(9,19),(10,19),(11,19),(12,19),(13,19),(14,19),(15,19),(16,19),(17,19),(18,19),(19,19),(20,19),(21,19),(22,19),(23,19),(24,19),(25,19),(26,19),(27,19),(1,20),(3,20),(4,20),(6,20),(7,20),(9,20),(10,20),(12,20),(13,20),(15,20),(16,20),(18,20),(19,20),(21,20),(22,20),(24,20),(25,20),(27,20),(1,21),(2,21),(3,21),(4,21),(5,21),(6,21),(7,21),(8,21),(9,21),(10,21),(11,21),(12,21),(13,21),(14,21),(15,21),(16,21),(17,21),(18,21),(19,21),(20,21),(21,21),(22,21),(23,21),(24,21),(25,21),(26,21),(27,21),(1,22),(2,22),(3,22),(7,22),(8,22),(9,22),(10,22),(11,22),(12,22),(16,22),(17,22),(18,22),(19,22),(20,22),(21,22),(25,22),(26,22),(27,22),(1,23),(3,23),(7,23),(9,23),(10,23),(12,23),(16,23),(18,23),(19,23),(21,23),(25,23),(27,23),(1,24),(2,24),(3,24),(7,24),(8,24),(9,24),(10,24),(11,24),(12,24),(16,24),(17,24),(18,24),(19,24),(20,24),(21,24),(25,24),(26,24),(27,24),(1,25),(2,25),(3,25),(4,25),(5,25),(6,25),(7,25),(8,25),(9,25),(10,25),(11,25),(12,25),(13,25),(14,25),(15,25),(16,25),(17,25),(18,25),(19,25),(20,25),(21,25),(22,25),(23,25),(24,25),(25,25),(26,25),(27,25),(1,26),(3,26),(4,26),(6,26),(7,26),(9,26),(10,26),(12,26),(13,26),(15,26),(16,26),(18,26),(19,26),(21,26),(22,26),(24,26),(25,26),(27,26),(1,27),(2,27),(3,27),(4,27),(5,27),(6,27),(7,27),(8,27),(9,27),(10,27),(11,27),(12,27),(13,27),(14,27),(15,27),(16,27),(17,27),(18,27),(19,27),(20,27),(21,27),(22,27),(23,27),(24,27),(25,27),(26,27),(27,27)]

Mathematica 29 28 байт

FindShortestTour (16 байт) делает трюк, но доставляет некоторую постороннюю информацию, не запрошенную (длина пути и возврат к начальной точке).

Most@*Last@*FindShortestTour

дает только ответ (-1 байт благодаря @ user202729)

Для визуализации используйте Graphics@Line[g[[%]]], где %- перестановка, найденная выше, а g - исходный список точек.

Вот визуализация решения для губки Менгера:

Вот решение на 1000 случайных точек:

Ключевым моментом здесь является знание того, что решение задачи кратчайшего тура или коммивояжера никогда не приведет к пересечению, если в качестве метрики используется евклидово расстояние. Одним из шагов по локализации решения и обеспечению оптимальности является удаление таких пересечений.

JavaScript (ES6), 365 341 байт

Без какой-либо встроенной, это оказалось намного дольше, чем я ожидал. Многие байты расходуются на обнаружение коллинеарных перекрывающихся сегментов.

Принимает ввод как массив [x,y]координат. Возвращает перестановку ввода.

f=(a,p=[],o=([p,P],[q,Q],[r,R])=>Math.sign((S=[(p>q?r<q|r>p:r<p|r>q)|(P>Q?R<Q|R>P:R<P|R>Q),...S],Q-P)*(r-q)-(q-p)*(R-Q)))=>[...p,p[0]].some((A,i,P)=>P.some((C,j)=>j>i+1&&P[++j+!i]&&[E=o(A,B=P[i+1],C,S=[]),F=o(A,B,D=P[j]),G=o(C,D,A),H=o(C,D,B)].some(v=>!v&!S.pop())|E!=F&G!=H))?0:a[0]?a.some((_,i)=>r=f(b=[...a],p.concat(b.splice(i,1))))&&r:p

демонстрация

Этот фрагмент регистрирует выходные данные и рисует соответствующий путь на холсте.

f=(a,p=[],o=([p,P],[q,Q],[r,R])=>Math.sign((S=[(p>q?r<q|r>p:r<p|r>q)|(P>Q?R<Q|R>P:R<P|R>Q),...S],Q-P)*(r-q)-(q-p)*(R-Q)))=>[...p,p[0]].some((A,i,P)=>P.some((C,j)=>j>i+1&&P[++j+!i]&&[E=o(A,B=P[i+1],C,S=[]),F=o(A,B,D=P[j]),G=o(C,D,A),H=o(C,D,B)].some(v=>!v&!S.pop())|E!=F&G!=H))?0:a[0]?a.some((_,i)=>r=f(b=[...a],p.concat(b.splice(i,1))))&&r:p

draw(f([[0,0],[0,1],[1,0]]), 1, 1)
draw(f([[0,0],[0,1],[1,0],[-1,0],[0,-1]]), 61, 21)
draw(f([[4,0],[1,0],[3,0],[0,0],[2,0],[0,1]]), 101, 1)

function draw(a, dx, dy) {
  console.log(JSON.stringify(a));

  ctx = C.getContext('2d');
  ctx.beginPath();
  [...a, a[0]].forEach(p => ctx.lineTo(p[0] * 20 + dx, p[1] * 20 + dy));
  ctx.stroke();
}

<canvas id=C></canvas>

Как?

Вот структура основной рекурсивной функции f () , оставляя пока код тестирования пересечения:

f = (a, p = []) =>                    // a = array of points, p = current path
  [...p,                              // build a closed path array P[] by adding the first
         p[0]]                        // point at the end of p[]
  .some((A, i, P) =>                  // for each point A at position i in P:
    P.some((C, j) =>                  //   for each point C at position j in P:
      j > i + 1 &&                    //     test whether C is at least 2 positions after A
      P[++j +                         //     and C is not the last point
              !i] &&                  //     and i > 0 or C is not the penultimate point
      intersection(                   //     and there's an intersection between
        A, P[i + 1], C, P[j]          //     the segments (A, P[i + 1]) and (C, P[j + 1])
      )                               //     (j was incremented above)
    )                                 //   end of inner some()
  ) ?                                 // end of outer some(); if truthy:
    0                                 //   discard this path by stopping recursion
  :                                   // else:
    a[0] ?                            //   if there's at least one remaining point:
      a.some((_, i) =>                //     for each remaining point at position i:
        r = f(                        //       do a recursive call with:
          b = [...a],                 //         a copy b[] of a[] without a[i] and
          p.concat(b.splice(i, 1)))   //         the extracted point added to the path
      ) && r                          //     end of some(); return the result, if any
    :                                 //   else:
      p                               //     this is a valid path: return it

Ниже приведены подробности теста intersection () . Эта страница содержит подробное объяснение используемого алгоритма.

[                                     // build an array containing:
  E = o(A, B = P[i + 1], C, S = []),  //   E = test of (A, B, C) (+ initialization of S[])
  F = o(A, B, D = P[j]),              //   F = test of (A, B, D)
  G = o(C, D, A),                     //   G = test of (C, D, A)
  H = o(C, D, B)                      //   H = test of (C, D, B)
]                                     //
.some(v =>                            // the segments are collinear and overlapping if:
  !v &                                //   any value above is 0
  !S.pop()                            //   and the corresponding entry in S[] is falsy
) |                                   // the segments intersect if:
E != F & G != H                       //   E is not equal to F and G is not equal to H

Наконец, вот определение вспомогательной функции o () :

o = (                                             // given three points represented by
  [p, P], [q, Q], [r, R]                          // a lowercase letter for x
) =>                                              // and an uppercase letter for y:
  Math.sign(                                      //
    (                                             //   1) prepend to the array S[]
      S = [                                       //      a boolean which is true if the
        (p > q ? r < q | r > p : r < p | r > q) | //      segment (P, Q) would not contain
        (P > Q ? R < Q | R > P : R < P | R > Q),  //      the point R, assuming that the
        ...S                                      //      3 points are collinear
      ],                                          //
                                                  //   2) return the orientation of P, Q, R:
      Q - P                                       //        -1 = counterclockwise
    ) * (r - q) - (q - p) * (R - Q)               //         0 = collinear
  )                                               //        +1 = clockwise

APL (Dyalog Classic) , 42 38 байт

{⍋(⍪,(|z)ׯ1*⊢=⌈/)12○z←0j1⊥¨⍵-⍵[⊃⍋↑⍵]}

Попробуйте онлайн!

Ввод - это список пар координат. Выход - перестановка на основе 0.

⍵ это список точек - аргумент { }

⍵[⊃⍋↑⍵] самая левая-самая низкая точка

⍵- переводит все точки так, чтобы крайний левый-нижний элемент находился в начале системы координат

0j1 мнимая единица я = sqrt (-1)

0j1⊥¨ декодирует координаты, как будто цифры в системе счисления base-i - то есть превращает (x, y) в комплексное число ix + y

z← назначить на z

12○вычисляет аргументы комплексных чисел, или тета-углы, или круговую функцию APL 12

(⍪,(|z)ׯ1*⊢=⌈/)является поездом, который вычисляет логическую маску, где углы находятся на максимуме ( ⊢=⌈/), превращает 0 1 в маске в 1 ¯1, увеличивая ¯1 до соответствующей степени ( ¯1*), умножая на величины комплексных чисел |z, и объединяет это справа ( ,) от высокой тонкой 1-столбцовой матрицы ( ⍪) углов.

⍋ grade - возвращает перестановку, которая бы сортировала строки матрицы лексикографически в порядке возрастания