Не могу придумать алгоритм такой сортировки

[Хакер]

Да, кстати, при коллапсировании нельзя допускать изменения топологии, т.е. коллапсировать нужно в определённом порядке. На вскидку: составить список вершин и углов, отсоритировать по углу в порядке убывания, убрать последние три пункта из списка, и в путь. После каждого коллапсе одну (устранённую) вершину надо из списка удалять, а для двух других (которые соединили ребром) обновлять угол. При этом, вероятно, придётся изменять их положение в списке.


ADDED: нет, при сортировке по углу тоже возможно нарушение топологии.

Придумал:
Нужно провести триангуляцию фигуры. Коллапсировать можно только те рёбра, которые принадлежат одному триангуляционному треугольнику (тафтология, но всё же). После коллапса полученная новая грань становится частью какого-то другого треугольника. И так до тех пор, пока не останется единственный треугольник.

И ещё один вариант придумал, двух проходный, но пусть автор пока попробует найти контрпример (если такой существует) к вышеописанному способу с триангуляцией.

Сейчас придумал крайне простой по сравнению с оцтитированным способ. Проверю.

[iGrok]

Ммм... Я, конечно, всё понимаю. Дискуссия, там. Обсуждение. Опять же, в споре обычно истина рождается...

Но поясните мне, плиз, чем плох способ с суммированием углов между векторами?

[Хакер]

Ну начнём с того, как ты будешь находить угол? (Это не значит, что я не знаю способа, просто в зависимости от способа будет задан следующий вопрос.)

[Александр Дмитриев]

И вообще, дай строгое математическое определение своим понятиям «по часово» и «против». Пока ты этого не сделаешь, решение проблемы будет глупым брутфорсом.

Сначала определяю понятие направления ломаной относительно точки как сумму углов между парами векторов, соединяющих данную точку с двумя смежными вершинами (с учётом направления), разделённую на 2*pi. Далее, если часть плоскости, строго ограничиваемая ломаной, не пуста, и относительно каждой её точки направление ломаной одно и то же, то считаю, что ломаная направлена в этом направлении.

Нужно провести триангуляцию фигуры. Коллапсировать можно только те рёбра, которые принадлежат одному триангуляционному треугольнику (тафтология, но всё же). После коллапса полученная новая грань становится частью какого-то другого треугольника. И так до тех пор, пока не останется единственный треугольник.

Да, идея хорошая, но триангулировать можно только несамопересекающийся многоугольник, определённое направление же можно дать и некоторым самопересекающимся многоугольникам (см. мой цветной рисунок).

Ну начнём с того, как ты будешь находить угол?

Я же написал, что угол можно определить через скалярное произведение, а направление - через векторное.

[Хакер]

Да, идея хорошая, но триангулировать можно только несамопересекающийся многоугольник, определённое направление же можно дать и некоторым самопересекающимся многоугольникам (см. мой цветной рисунок).

Стоп. Во-первых, по условию задачи самопересечения исключены, разве нет?
Во-вторых, если самопересечения есть, то ответ на вопрос дать нельзя! С чего ты взял, что цветная фигура нарисована против часовой, я не знаю. Очевидно, это просто эффект перцептивной готовности, и если я нарисую фигуру, гомеоморфную твоей, но с другими размерами рёбрами, то есть шанс, что ты скажешь, что фигура нарисована по часовой.

Я же написал, что угол можно определить через скалярное произведение, а направление - через векторное.

Я не тебя спрашивал.

[iGrok]

Я не тебя спрашивал.

Ну я, в общем-то, своего способа не выдумывал. Просто проверил данный Александром Дмитриевым.
С виду он работоспособен. На относительно простых многоугольниках работает.

Естественно, при условии, что все точки дествительно ставятся последовательно либо по часовой, либо против.

Если точки идут "вразнобой", и нужно не только направить все векторы по часовой стрелке, но и выстроить их в правильном порядке (убрать пересечения, сделать замкнутый контур), всё получается несколько труднее...

Или я чего-то ещё не учитываю?

[Александр Дмитриев]

С чего ты взял, что цветная фигура нарисована против часовой, я не знаю.

Я взял с того, что она удовлетворяет данному выше определению.

[Хакер]

Возьми знак бесконечности и скажи мне, как он нарисован. По или против часовой.

[Debugger]

Что-то вы намудрили.
Давайте выдерним из многоугольника такую вершину, чтобы все другие точки многоугольника по одну сторону (на одной полуплоскости) от этой вершины(плохо объяснил... вспоминаем, как определить, является ли это многоугольник выпуклым. Так вот, берем эту "выпуклую" вершину) и две соседние точки. Имея их и центр нашего многоугольника, мы точно сможем сказать, идут ли они по или против часовой стрелки. Как - сейчас покажу в картинках, а потом отшлифую на словах.
Теория у меня не хорошая. Утро вечера мудренее, завтра выложу хороший вариант.

[Хакер]

Мудришь ты. Когда напишешь код, который будет искать такую вершину и проверять, лежит ли всё остальное по одну сторону от некоторой воображаемой прямой, поймёшь.

[Александр Дмитриев]

Возьми знак бесконечности и скажи мне, как он нарисован. По или против часовой.

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

Debugger Во-первых, (по тексту) что такое центр многоугольника? Во-вторых, (по картинке) углов между отрезком и прямой будет два - меньший и больший (180 - меньший). Как из них определить нужный?

[Хакер]

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

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

Код: Выделить всё

Public Function IsClockwise() As Boolean
    Dim rsin    As Double
    Dim rcos    As Double
    Dim CurV    As VECTOR
    Dim PrevV   As VECTOR
    Dim CurS    As Double
    Dim PrevS   As Double
    Dim i       As Long
   
    CurV = VecSubstact(VerteciesArr(2), VerteciesArr(1))
    CurS = Sqr(CurV.x ^ 2 + CurV.y ^ 2)
    rsin = CurV.x / CurS
    rcos = CurV.y / CurS
   
    For i = 3 To VerteciesCnt
        CurV = VecSubstact(VerteciesArr(i), VerteciesArr(2))
        CurV.x = rcos * CurV.x - rsin * CurV.y
        CurV.y = rsin * CurV.x + rcos * CurV.y
        CurS = Sgn(CurV.x)
        If CurS <> PrevS Then
            If PrevV.y - (CurV.y - PrevV.y) * PrevV.x / (CurV.x - PrevV.x) >= 0 Then IsClockwise = CurS > PrevS
        End If
        PrevV = CurV
        PrevS = CurS
    Next i
End Function

Если интересно, могу выложить класс целиком.

[Debugger]

Здорово, Хакер!
Только объясни, пожалуйста, в чем сложность моего метода:
Взять такую вершину (и 2 соседних ребра), чтобы через нее можно было провести такую прямую, чтобы все остальные точки многоугольника лежали по одну сторону от нее. По идее, эти 2 ребра и точку можно рассмотреть, как треугольник, и определить направление в нем.
Ребро, которое идет ИЗ выбранной вершины, обозначим "1", а которое идет В вершину - "2". Замерим угол по часовой стрелке от ребра 1 до ребра 2. Если он меньше 180 градусов, то вершины идут ПО часовой, если больше 180 градусов - идут против часовой. Сейчас кто-нибудь спросит "а если равно 180?". А если равно - не может быть, это не удовлетворяет первому условию.
И еще интересно, почему теорию Хакера с коллапсированием забраковали?

[Nord777]

Если интересно, могу выложить класс целиком.

Интересно, выкладывай.

[Хакер]

Здорово, Хакер!

Спасибо.

Только объясни, пожалуйста, в чем сложность моего метода:
Взять такую вершину (и 2 соседних ребра), чтобы через нее можно было провести такую прямую, чтобы все остальные точки многоугольника лежали по одну сторону от нее.

Сложность заключается в выделенном слове. Это ты легко можешь взять, а компьютер может взять только конкретную, которую прикажут, так что, чтобы он взял нужную, нужно по очереди брать все и проверять, подходит ли выбранная. Т.е. если у тебя фигура из 1000 вершин, то ты будешь перебирать всю 1000 вершин и каждый раз из тысячи разов будешь 998 раз проверять факт пересечения прямой (какой? Какую прямую ты собрался брать?) с остальными 998 рёбрами?

По идее, эти 2 ребра и точку можно рассмотреть, как треугольник, и определить направление в нем.
Ребро, которое идет ИЗ выбранной вершины, обозначим "1", а которое идет В вершину - "2". Замерим угол по часовой стрелке от ребра 1 до ребра 2. Если он меньше 180 градусов, то вершины идут ПО часовой, если больше 180 градусов - идут против часовой. Сейчас кто-нибудь спросит "а если равно 180?". А если равно - не может быть, это не удовлетворяет первому условию.

Предлагаю тебе реализовать свой способ на VB6 и потом сравнить с реализацией моего последнего способа. Тогда ты поймёшь, в чём сложность.
Другое дело, мне кажется, ты свой способ нашёл «интуитивно». И ты понимаешь суть моего способа? Если ты сядешь и станешь размышлять над своим первым условием, то в некоторый момент осознаешь, что его выполнение не обязательно, если вместо него делать другие (гораздо более мелкие) проверки. Но фишка будет в том, что наличие этих мелких проверок сделает ненужным измерение угла. И тогда, по сути, ты получишь мой способ.

Если точно так же задуматься над способом с суммированием углов, то его тоже можно упростить, приведя к моему.

И еще интересно, почему теорию Хакера с коллапсированием забраковали?

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

Интересно, выкладывай.

Там оставшийся код не имеет отношения несосредственно к самому способа: там добавление вершин, изменение размера массива и т.п.

[iGrok]

Так тут кто-нибудь наконец скажет, чем плох способ с подсчётом углов?

[Хакер]

Если точно так же задуматься над способом с суммированием углов, то его тоже можно упростить, приведя к моему.

[Хакер]

Класс целиком:

Код: Выделить всё

Option Explicit
Private Type VECTOR
    x As Double
    y As Double
End Type
Private VerteciesArr()      As VECTOR
Private VerteciesCnt        As Long

Private Function VecSubstact(a As VECTOR, b As VECTOR) As VECTOR
    VecSubstact.x = a.x - b.x
    VecSubstact.y = a.y - b.y
End Function

Public Function IsClockwise() As Boolean
    Dim rsin    As Double
    Dim rcos    As Double
    Dim CurV    As VECTOR
    Dim PrevV   As VECTOR
    Dim CurS    As Double
    Dim PrevS   As Double
    Dim i       As Long
   
    CurV = VecSubstact(VerteciesArr(2), VerteciesArr(1))
    CurS = Sqr(CurV.x ^ 2 + CurV.y ^ 2)
    rsin = CurV.x / CurS
    rcos = CurV.y / CurS
   
    For i = 3 To VerteciesCnt
        CurV = VecSubstact(VerteciesArr(i), VerteciesArr(2))
        CurV.x = rcos * CurV.x - rsin * CurV.y
        CurV.y = rsin * CurV.x + rcos * CurV.y
        CurS = Sgn(CurV.x)
        If CurS <> PrevS Then
            If PrevV.y - (CurV.y - PrevV.y) * PrevV.x / (CurV.x - PrevV.x) >= 0 Then IsClockwise = CurS > PrevS
        End If
        PrevV = CurV
        PrevS = CurS
    Next i
End Function

Private Sub Class_Initialize()
    ReDim VerteciesArr(1 To 256)
End Sub

Public Sub AddVertex(ByVal x As Double, ByVal y As Double)
    On Error GoTo ErrorHandler
    VerteciesCnt = VerteciesCnt + 1
    VerteciesArr(VerteciesCnt).x = x
    VerteciesArr(VerteciesCnt).y = y
    Exit Sub
ErrorHandler:
    If Err.Number = 9 Then
        ReDim Preserve VerteciesArr(1 To VerteciesCnt + 255)
        Resume
    End If
End Sub


[Debugger]

Я взял бумажку и мой алгоритм. И упрощал. Потом переписал слегка модифицированный алгоритм. Все так же, без теории и доказательств, но работает. Даже в некоторых замысловатых фигурах:

thatsgood.png (16.43 Кб) Просмотров: 13058

Не удивлюсь, если кто-то нарисует пример, который программа не прожует.
Кстати. Я использую DirectX8'ю функцию D3DXVec2CCW, которая определяет угол между двумя векторами. Можно ли ее как-то заменить? Я пробовал использовать скалярное произведение, но я получал только косинус нужного угла. Что делать с ним дальше?

[Александр Дмитриев]

Хакер Во-первых, метод не работает для следующего многоугольника:



Во-вторых, что это за мудрёный поворот такой (только что вычисленная абсцисса участвует в вычислении новой ординаты):

Код: Выделить всё

CurV.x = rcos * CurV.x - rsin * CurV.y
CurV.y = rsin * CurV.x + rcos * CurV.y

Debugger Метод не работает, например, вот в таком случае:

7.jpg (11.55 Кб) Просмотров: 13019

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

[Debugger]

Конечно, не работает. Он же самопересекается, или у меня глюки?

[Хакер]

Хакер Во-первых, метод не работает для следующего многоугольника:

Работает. Дай кооридинаты вершин, с которыми у тебя наблюдается ошибка.

Во-вторых, что это за мудрёный поворот такой (только что вычисленная абсцисса участвует в вычислении новой ординаты):

Код: Выделить всё

CurV.x = rcos * CurV.x - rsin * CurV.y
CurV.y = rsin * CurV.x + rcos * CurV.y

Косяк, должно быть:

Код: Выделить всё

Private Function VecSubstact(a As VECTOR, b As VECTOR) As VECTOR
    VecSubstact.x = a.x - b.x
    VecSubstact.y = a.y - b.y
End Function

Private Function VecRotate(ByRef v As VECTOR, ByVal rSin As Double, ByVal rCos As Double) As VECTOR
    VecRotate.x = v.x * rCos - rSin * v.y
    VecRotate.y = v.x * rSin + rCos * v.y
End Function

Public Function IsClockwise() As Boolean
    Dim rSin    As Double
    Dim rCos    As Double
    Dim CurV    As VECTOR
    Dim PrevV   As VECTOR
    Dim CurS    As Double
    Dim PrevS   As Double
    Dim i       As Long
   
    CurV = VecSubstact(VerteciesArr(2), VerteciesArr(1))
    CurS = Sqr(CurV.x ^ 2 + CurV.y ^ 2)
    rSin = CurV.x / CurS
    rCos = CurV.y / CurS
   
    For i = 3 To VerteciesCnt
        CurV = VecRotate(VecSubstact(VerteciesArr(i), VerteciesArr(2)), rSin, rCos)
        CurS = Sgn(CurV.x)
        If CurS <> PrevS Then
            If PrevV.y - (CurV.y - PrevV.y) * PrevV.x / (CurV.x - PrevV.x) >= 0 Then IsClockwise = CurS > PrevS
        End If
        PrevV = CurV
        PrevS = CurS
    Next i
End Function

Ещё, метод улучшится, если проходиться по многоугольнику с конца.

[Александр Дмитриев]

Хакер

Код: Выделить всё

Sub Main()
  Dim Polygon As New Class1
  Polygon.AddVertex 0, 2
  Polygon.AddVertex 0, 3
  Polygon.AddVertex 2, 3
  Polygon.AddVertex 2, 0
  Polygon.AddVertex -2, 0
  Polygon.AddVertex -2, 5
  Polygon.AddVertex 2, 5
  Polygon.AddVertex 2, 4
  Polygon.AddVertex -1, 4
  Polygon.AddVertex -1, 1
  Polygon.AddVertex 1, 1
  Polygon.AddVertex 1, 2
  MsgBox Polygon.IsClockwise
End Sub


[Nord777]

Погоняйте, вроде не ошибается.

[Александр Дмитриев]

Погоняйте, вроде не ошибается.

Ееее... Контрпример во вложении.

[Nord777]

Ееее... Контрпример во вложении.

Ахилесова пята Тестил на сложных, а про простое забыл.
Недочет убрал. Вложение обновил.

[Debugger]

Описание алгоритма расскажи, прямо интересно.

[Александр Дмитриев]

Недочет убрал.

Ещё хуже. Кстати, по-моему, Хакер такой метод уже предлагал.

[Хакер]

Новый класс:

Код: Выделить всё

Option Explicit
Private Type VECTOR
    x As Double
    y As Double
End Type
Private VerteciesArr()      As VECTOR
Private VerteciesCnt        As Long
Private PivotIndex          As Long

Private Function VecSubtract(ByRef a As VECTOR, ByRef b As VECTOR) As VECTOR
    VecSubtract.x = a.x - b.x
    VecSubtract.y = a.y - b.y
End Function

Public Function IsClockwise() As Boolean
    Dim a As VECTOR
    Dim b As VECTOR
    a = VecSubtract(VerteciesArr((PivotIndex + VerteciesCnt - 2) Mod VerteciesCnt + 1), VerteciesArr(PivotIndex))
    b = VecSubtract(VerteciesArr((PivotIndex + VerteciesCnt) Mod VerteciesCnt + 1), VerteciesArr(PivotIndex))
    IsClockwise = a.x / Sqr(a.x ^ 2 + a.y ^ 2) < b.x / Sqr(b.x ^ 2 + b.y ^ 2)
End Function

Private Sub Class_Initialize()
    ReDim VerteciesArr(1 To 1)
End Sub

Public Sub AddVertex(ByVal x As Double, ByVal y As Double)
    On Error GoTo ErrorHandler
    VerteciesCnt = VerteciesCnt + 1
    VerteciesArr(VerteciesCnt).x = x
    VerteciesArr(VerteciesCnt).y = y
    On Error GoTo 0
    On Error Resume Next
    If y > VerteciesArr(PivotIndex).y Then Else Exit Sub
    PivotIndex = VerteciesCnt
    Exit Sub
ErrorHandler:
    If Err.Number = 9 Then
        ReDim Preserve VerteciesArr(1 To VerteciesCnt + 255)
        Resume
    End If
End Sub

Жду контрпримера

[Debugger]

Судя по всему, ты использовал что-то похожее на мой алгоритм.

Код: Выделить всё

IsClockwise = a.x / Sqr(a.x ^ 2 + a.y ^ 2) < b.x / Sqr(b.x ^ 2 + b.y ^ 2)

Что значит эта строчка?
ADDED: Косинус по отношению к горизонтали одного вектора больше другого вектора?
ADDED2: все, понял.
ADDED3:

Код: Выделить всё

If y > VerteciesArr(PivotIndex).y Then Else Exit Sub

Сусанишь!

Код: Выделить всё

If y <= VerteciesArr(PivotIndex).y Then Exit Sub

ADDED4:

Код: Выделить всё

    On Error GoTo 0
    On Error Resume Next

Зачем два On Error?