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

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 23.05.2009 (Сб) 20:43

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


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

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

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

Сейчас придумал крайне простой по сравнению с оцтитированным способ. Проверю.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4272
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

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

Сообщение iGrok » 23.05.2009 (Сб) 21:25

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

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 23.05.2009 (Сб) 21:31

Ну начнём с того, как ты будешь находить угол? (Это не значит, что я не знаю способа, просто в зависимости от способа будет задан следующий вопрос.)
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

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

Сообщение Александр Дмитриев » 23.05.2009 (Сб) 21:43

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

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

Хакер писал(а):Ну начнём с того, как ты будешь находить угол?
Я же написал, что угол можно определить через скалярное произведение, а направление - через векторное.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 23.05.2009 (Сб) 22:24

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

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

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

Я не тебя спрашивал.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4272
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

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

Сообщение iGrok » 23.05.2009 (Сб) 22:35

Хакер писал(а):Я не тебя спрашивал.

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

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

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

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

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

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

Сообщение Александр Дмитриев » 23.05.2009 (Сб) 22:42

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

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 23.05.2009 (Сб) 22:48

Возьми знак бесконечности и скажи мне, как он нарисован. По или против часовой.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

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

Сообщение Debugger » 23.05.2009 (Сб) 22:58

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 23.05.2009 (Сб) 23:13

Мудришь ты. Когда напишешь код, который будет искать такую вершину и проверять, лежит ли всё остальное по одну сторону от некоторой воображаемой прямой, поймёшь.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

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

Сообщение Александр Дмитриев » 23.05.2009 (Сб) 23:18

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

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

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 23.05.2009 (Сб) 23:41

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

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

Код: Выделить всё
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


Если интересно, могу выложить класс целиком.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

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

Сообщение Debugger » 24.05.2009 (Вс) 10:02

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

Nord777
Гуру
Гуру
Аватара пользователя
 
Сообщения: 1144
Зарегистрирован: 22.02.2004 (Вс) 13:15
Откуда: Подольск

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

Сообщение Nord777 » 24.05.2009 (Вс) 11:22

Хакер писал(а):Если интересно, могу выложить класс целиком.
Интересно, выкладывай.
Microsoft Visual Studio 2008
Microsoft .NET Framework 3.5

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 24.05.2009 (Вс) 12:51

Debugger писал(а):Здорово, Хакер!

Спасибо.

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

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

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

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

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

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

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

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

Там оставшийся код не имеет отношения несосредственно к самому способа: там добавление вершин, изменение размера массива и т.п.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4272
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

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

Сообщение iGrok » 24.05.2009 (Вс) 12:54

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 24.05.2009 (Вс) 12:57

Хакер писал(а):Если точно так же задуматься над способом с суммированием углов, то его тоже можно упростить, приведя к моему.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 24.05.2009 (Вс) 13:01

Класс целиком:
Код: Выделить всё
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
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

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

Сообщение Debugger » 24.05.2009 (Вс) 14:30

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

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

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

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

Сообщение Александр Дмитриев » 24.05.2009 (Вс) 14:52

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

Изображение

Во-вторых, что это за мудрёный поворот такой (только что вычисленная абсцисса участвует в вычислении новой ординаты):
Код: Выделить всё
CurV.x = rcos * CurV.x - rsin * CurV.y
CurV.y = rsin * CurV.x + rcos * CurV.y

Debugger Метод не работает, например, вот в таком случае:
7.jpg
7.jpg (11.55 Кб) Просмотров: 12496

Хотя в случае самонепересекающихся многоугольников это будет, пожалуй, лучшим способом из всех предложенных.
Вложения
6.jpg
6.jpg (5.6 Кб) Просмотров: 12803

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

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

Сообщение Debugger » 24.05.2009 (Вс) 15:49

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 24.05.2009 (Вс) 15:54

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

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


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


Ещё, метод улучшится, если проходиться по многоугольнику с конца.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

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

Сообщение Александр Дмитриев » 24.05.2009 (Вс) 16:17

Хакер
Код: Выделить всё
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
Гуру
Гуру
Аватара пользователя
 
Сообщения: 1144
Зарегистрирован: 22.02.2004 (Вс) 13:15
Откуда: Подольск

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

Сообщение Nord777 » 24.05.2009 (Вс) 23:53

Погоняйте, вроде не ошибается.
Вложения
snapshot.png
snapshot.png (15.4 Кб) Просмотров: 12531
CW_OR_NOT_CW.rar
Версия 2. Нужен Framework 3.5
(15.21 Кб) Скачиваний: 358
Последний раз редактировалось Nord777 25.05.2009 (Пн) 13:42, всего редактировалось 3 раз(а).
Microsoft Visual Studio 2008
Microsoft .NET Framework 3.5

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

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

Сообщение Александр Дмитриев » 25.05.2009 (Пн) 2:41

Nord777 писал(а):Погоняйте, вроде не ошибается.

Ееее... :twisted: Контрпример во вложении.
Вложения
Figure.zip
(398 байт) Скачиваний: 322

Nord777
Гуру
Гуру
Аватара пользователя
 
Сообщения: 1144
Зарегистрирован: 22.02.2004 (Вс) 13:15
Откуда: Подольск

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

Сообщение Nord777 » 25.05.2009 (Пн) 11:03

Ееее... Контрпример во вложении.
Ахилесова пята :D Тестил на сложных, а про простое забыл.
Недочет убрал. Вложение обновил.
Microsoft Visual Studio 2008
Microsoft .NET Framework 3.5

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

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

Сообщение Debugger » 25.05.2009 (Пн) 15:55

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

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

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

Сообщение Александр Дмитриев » 25.05.2009 (Пн) 16:02

Nord777 писал(а):Недочет убрал.
Ещё хуже. Кстати, по-моему, Хакер такой метод уже предлагал.
Вложения
Figure.zip
(412 байт) Скачиваний: 331

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 25.05.2009 (Пн) 18:20

Новый класс:
Код: Выделить всё
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

Жду контрпримера :)
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

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

Сообщение Debugger » 25.05.2009 (Пн) 20:41

Судя по всему, ты использовал что-то похожее на мой алгоритм.
Код: Выделить всё
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?

Пред.След.

Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5

    TopList