Сортировка точек по часовой стрелке?

Учитывая массив точек x, y, как мне отсортировать точки этого массива по часовой стрелке (вокруг их средней средней точки)? Моя цель - передать точки в функцию создания линий, чтобы в итоге получилось нечто "сплошное", настолько выпуклое, насколько это возможно, без пересекающихся линий.

Для чего это стоит, я использую Lua, но любой псевдокод был бы оценен.

Обновление: Для справки: это код Lua, основанный на превосходном ответе Ciamej (игнорируйте мой префикс "app"):

function appSortPointsClockwise(points)
    local centerPoint = appGetCenterPointOfPoints(points)
    app.pointsCenterPoint = centerPoint
    table.sort(points, appGetIsLess)
    return points
end

function appGetIsLess(a, b)
    local center = app.pointsCenterPoint

    if a.x >= 0 and b.x < 0 then return true
    elseif a.x == 0 and b.x == 0 then return a.y > b.y
    end

    local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
    if det < 0 then return true
    elseif det > 0 then return false
    end

    local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
    local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
    return d1 > d2
end

function appGetCenterPointOfPoints(points)
    local pointsSum = {x = 0, y = 0}
    for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end
    return {x = pointsSum.x / #points, y = pointsSum.y / #points}
end

Ответы

Ответ 1

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

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

det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)

если результат равен нулю, то они находятся на одной линии от центра, если он положительный или отрицательный, то он находится на одной стороне или другой, поэтому одна точка будет предшествовать другой. Используя его, вы можете построить меньшее, чем отношение для сравнения точек, и определить порядок, в котором они должны появляться в отсортированном массиве. Но вы должны определить, где начало этого порядка, я имею в виду, какой угол будет начальным (например, положительная половина оси x).

Код для функции сравнения может выглядеть так:

bool less(point a, point b)
{
    if (a.x - center.x >= 0 && b.x - center.x < 0)
        return true;
    if (a.x - center.x < 0 && b.x - center.x >= 0)
        return false;
    if (a.x - center.x == 0 && b.x - center.x == 0) {
        if (a.y - center.y >= 0 || b.y - center.y >= 0)
            return a.y > b.y;
        return b.y > a.y;
    }

    // compute the cross product of vectors (center -> a) x (center -> b)
    int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0)
        return true;
    if (det > 0)
        return false;

    // points a and b are on the same line from the center
    // check which point is closer to the center
    int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
    return d1 > d2;
}

Это будет порядок точек по часовой стрелке, начиная с 12 часов. Точки в том же "часе" будут заказываться начиная с тех, которые находятся дальше от центра.

Если вы используете целые типы (которые на самом деле не присутствуют в Lua), вы должны убедиться, что переменные det, d1 и d2 имеют тип, который сможет удерживать результат выполненных вычислений.

Если вы хотите добиться чего-то прочного, как можно более выпуклого, то, думаю, вы ищете выпуклый корпус. Вы можете вычислить его с помощью Graham Scan. В этом алгоритме, вы также должны сортировать точки по часовой стрелке (или против часовой стрелки), начиная с особой точкой поворота. Затем вы повторяете простые шаги шага каждый раз, проверяя, поворачиваете ли вы влево или вправо, добавляя новые точки к выпуклой оболочке, эта проверка основана на перекрестном продукте, как в приведенной выше функции сравнения.

Edit:

Добавлен еще один оператор if if (a.y - center.y >= 0 || b.y - center.y >=0), чтобы убедиться, что точки, которые имеют x = 0 и отрицательные y, сортируются, начиная с тех, которые находятся дальше от центра. Если вам не нужен порядок точек в один и тот же "час", вы можете опустить этот оператор if и всегда возвращать a.y > b.y.

Исправлены первые операторы if с добавлением -center.x и -center.y.

Добавлен второй оператор if (a.x - center.x < 0 && b.x - center.x >= 0). Было очевидно, что он пропал без вести. Операторы if могут быть реорганизованы сейчас, потому что некоторые проверки являются излишними. Например, если первое условие в первом операторе if является ложным, то первое условие второго if должно быть истинным. Я решил, однако, оставить код, как и для простоты. Вполне возможно, что компилятор будет оптимизировать код и в любом случае получить тот же результат.

Ответ 2

То, о чем вы просите, это система, известная как полярные координаты . Преобразование из декартовых координат в полярные координаты легко выполняется на любом языке. Формулы можно найти в в этом разделе.

Я не знаю Lua, но эта страница, как представляется, предлагает фрагменты кода для этого преобразования.

После преобразования в полярные координаты просто отсортируйте по углу, theta.

Ответ 3

Интересным альтернативным подходом к вашей проблеме будет поиск приблизительного минимума для Задачи коммивояжера (TSP), т.е. самый короткий маршрут, связывающий все ваши очки. Если ваши точки образуют выпуклую форму, это должно быть правильное решение, в противном случае оно должно выглядеть хорошо ( "твердая" форма может быть определена как та, которая имеет низкое соотношение по периметру и площади, что мы и оптимизируем здесь).

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

Ответ 4

Другая версия (верните true, если a предшествует b в направлении против часовой стрелки):

    bool lessCcw(const Vector2D &center, const Vector2D &a, const Vector2D &b) const
    {
        // Computes the quadrant for a and b (0-3):
        //     ^
        //   1 | 0
        //  ---+-->
        //   2 | 3

        const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
        const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
        const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);

        /* The previous computes the following:

           const int qa =
           (  (a.x() > center.x())
            ? ((a.y() > center.y())
                ? 0 : 3)
            : ((a.y() > center.y())
                ? 1 : 2)); */

        const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
        const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
        const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);

        if (qa == qb) {
            return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
        } else {
            return qa < qb;
       } 
    }

Это быстрее, потому что компилятор (протестированный на Visual C++ 2015) не генерирует переход для вычисления dax, day, dbx, dby. Вот выходная сборка от компилятора:

; 28   :    const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;

    vmovss  xmm2, DWORD PTR [ecx]
    vmovss  xmm0, DWORD PTR [edx]

; 29   :    const int day = ((a.y() - center.y()) > 0) ? 1 : 0;

    vmovss  xmm1, DWORD PTR [ecx+4]
    vsubss  xmm4, xmm0, xmm2
    vmovss  xmm0, DWORD PTR [edx+4]
    push    ebx
    xor ebx, ebx
    vxorps  xmm3, xmm3, xmm3
    vcomiss xmm4, xmm3
    vsubss  xmm5, xmm0, xmm1
    seta    bl
    xor ecx, ecx
    vcomiss xmm5, xmm3
    push    esi
    seta    cl

; 30   :    const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);

    mov esi, 2
    push    edi
    mov edi, esi

; 31   : 
; 32   :    /* The previous computes the following:
; 33   : 
; 34   :    const int qa =
; 35   :        (   (a.x() > center.x())
; 36   :         ? ((a.y() > center.y()) ? 0 : 3)
; 37   :         : ((a.y() > center.y()) ? 1 : 2));
; 38   :    */
; 39   : 
; 40   :    const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;

    xor edx, edx
    lea eax, DWORD PTR [ecx+ecx]
    sub edi, eax
    lea eax, DWORD PTR [ebx+ebx]
    and edi, eax
    mov eax, DWORD PTR _b$[esp+8]
    sub edi, ecx
    sub edi, ebx
    add edi, esi
    vmovss  xmm0, DWORD PTR [eax]
    vsubss  xmm2, xmm0, xmm2

; 41   :    const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;

    vmovss  xmm0, DWORD PTR [eax+4]
    vcomiss xmm2, xmm3
    vsubss  xmm0, xmm0, xmm1
    seta    dl
    xor ecx, ecx
    vcomiss xmm0, xmm3
    seta    cl

; 42   :    const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);

    lea eax, DWORD PTR [ecx+ecx]
    sub esi, eax
    lea eax, DWORD PTR [edx+edx]
    and esi, eax
    sub esi, ecx
    sub esi, edx
    add esi, 2

; 43   : 
; 44   :    if (qa == qb) {

    cmp edi, esi
    jne SHORT [email protected]

; 45   :        return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());

    vmulss  xmm1, xmm2, xmm5
    vmulss  xmm0, xmm0, xmm4
    xor eax, eax
    pop edi
    vcomiss xmm0, xmm1
    pop esi
    seta    al
    pop ebx

; 46   :    } else {
; 47   :        return qa < qb;
; 48   :    }
; 49   : }

    ret 0
[email protected]:
    pop edi
    pop esi
    setl    al
    pop ebx
    ret 0
[email protected]@[email protected]@[email protected] ENDP            ; lessCcw

Наслаждайтесь.

Ответ 5

  • vector3 a = новый вектор3 (1, 0, 0).............. w.r.t X_axis
  • vector3 b = любая_точка - Центр;
- y = |a * b|   ,   x =  a . b

- Atan2(y , x)...............................gives angle between -PI  to  + PI  in radians
- (Input % 360  +  360) % 360................to convert it from  0 to 2PI in radians
- sort by adding_points to list_of_polygon_verts by angle  we got 0  to 360

Наконец-то вы получаете отсортированные по вертикали Anticlockwize

list.Reverse().................. Clockwise_order