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

  • О вытягивании себя из болота по методу Мюнхгаузена

    Всё готовлюсь к встрече с представителями РКК Энергия, нужно убедить их в моём способе определения положения ВидеоИзмерителя Параметров Сближения на…

  • Ремонт лыжных мостиков

    Вернулся с сегодняшнего субботника. Очень продуктивно: отремонтировали все ТРИ мостика! Правда, для этого надо было разделиться, благо народу…

  • Гетто-байк

    В субботу во время Великой Октябрьской резни бензопилой умудрился петуха сломать в велосипеде. По счастью, уже на следующий день удалось купить…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments