nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

О сортировке "против часовой стрелки"

Часть 1 - нахождение наиболее отдалённой точки
Часть 2 - сортировка против часовой стрелки
Комментарий об операторе упорядочивания
Часть 3 - нахождение матрицы преобразования
Часть 4 - нахождение крена
Математическая интерлюдия
Часть 5 - нахождение масштаба
Финал!

Небольшой комментарий к части 2, там мы отсортировали 3 точки против часовой стрелки, по сути введя "свой собственный" оператор упорядочивания:

A (ax, ay) < B (bx, by), если



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

Но если мы подсунем вот такие три точки:

(картинку утянул с яндекс. картинок)

то в зависимости от алгоритма сортировки, случиться может всё что угодно! Может действительно отсортировать "против часовой", а может выйти по часовой, и начнёт с любого места, а может и вовсе зависнет (уйдёт в бесконечный цикл)!

А всё из-за того, что у нашего оператора упорядочивания не всегда выполняются необходимые свойства.


Чтобы последовательность можно было отсортировать, и результат получался однозначным (какой алгоритм не применяй), наш оператор должен обладать двумя свойствами:

1. Всегда выполняется одно из 3 утверждений: либо A < B, либо A=B, либо B < A. Если мы введём равенство таким способом:

A = B, если



то ровно так всё и будет.

2. Должна выполняться транзитивность: если A < B и B < C, то A < C.

И вот с этим у нас проблемы, как явствует из рисунка выше!

Ведь для точек из этого рисунка выходит: A < B, B< C, C < A, - явное нарушение...

Не зря же оператор, обладающий такими свойствами, называют оператором ЛИНЕЙНОГО упорядочивания! (иногда - совершенного упорядочивания). А у нас тут всё закольцовано.


Но если все точки расположены в одной полуплоскости, то данные свойства начинают соблюдаться - и сортировка происходит без проблем.
Tags: tex, математика, странные девайсы
Subscribe

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments