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

[Александр_ФФ]

Обалдеть!!!
Всем участникам респект за кучу алгоритмов!
Я использовал сумму значений углов. угол = скалярому *, но вместо второго вектора берется его нормаль - получается не cos, a sin угла. чтобы были отрицательные углы.
Уже всё работает!
Самопересечений быть не может - это сечение физ. объекта.

[Хакер]

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

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

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

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

Я тебе говорил, что если ты подумаешь над своим алгоритмом, то приведёшь его к моему. Оба алгоритма основываются на том факте, что любой экстрасложный (но не самопересекающийся) многоугольник гомеоморфен выпуклому многоугольнику, т.е. его его можно деформировать, не допуская разрывов/склеек/пересечений так, что он будет топологически эквивалентен исходному многоугольнику. А clockwise-ность как раз и определяется топологией и никак не зависит от деформации. С выпуклым многоугольником clockwise-ность определить проще: достаточно провести отрезок из многоугольника во внешний мир, тогда, если ломаная пересекает этот отрезок слева направо, то clockwise, в обратном случае — против. С неправильным многоугольником сложнее: там этот отрезок может пересекаться более чем одним ребром. При этом, я посчитал, что актуальной будет информация о самом последнем (по мере обхода вершин) пересечении, т.к. это будет самым внешним ребром (и это то было моим заблуждением). Но зато я сделал другую хитрость: этот отрезок, который мы проводим из многоугольника во внешний мир допустимо проводить даже из какой-нибудь вершины многоугольника. Я решил проводить его из конца первого ребра (т.е. из второй вершины), причём проводить его «в продолжение» первого ребра. Кроме того, я определяю локальную систему координат, начало которой лежит в начале данного отрезка, и ось oY совпадает с направлением отрезка. Тогда для определения факта пересечения какого-нибудь ребра с нашим отрезком уже не нужно решать систему уравнений, достаточно определить, пересекает ли ребро ось oY, а это проще простого: надо сравнить знаки X-координат концов ребра. Поэтому-то там и встречает Sgn(). Если Sgn(Начало.x) < Sgn(Конец.x) — значит ребро пересекло oY слева направо, т.е. по часовой.
Но из-за заблуждения алгоритм оказался нерабочим, тогда надо было отказаться от ошибочного утверждения и взязть на вооружение какой-то иной способ найти определить пресечение самого внешнего ребра с отрезком. Очевидно, самым естественным способ это сделать, было сравнение y-коориданты пересечения. Но тут есть иной облом: если вершина попадёт на ось oY, то координаты пересечения двух соседних рёбер (сочленённых между собой этой вершиной) с осью oY будет одинаковыми (по сути, это будут координаты «нехорошей вершины»). И как теперь определить, которое из рёбер «внешнее»? Только дополнительной обработкой таких ситуаций. А написание такой обработки делает алгоритм не таким простым и красивым, какой он был изначально.

Тогда надо отказываться от этого метода. Вместо того, чтобы «крутить фигуру», строить отрезок и смотреть, «откуда куда» пересекает самое внешнее ребро наш отрезок, мы будем делать что-то другое. Начнём с того, что изначально мы не можем найти самое внешнее ребро, потому что смысл этого понятия есть только тогда, когда есть направленный отрезок и несколько рёбер, его пересекающих. Так что изначально мы можем найти только самую внешнюю точку (т.е. точку, через которую можно провести касательную). Имея касательную к фигуре, мы точно знаем, что вся остальная фигура лежит по одну сторону сторону от касательной (если часть фигуры лежит по одну сторону, часть — по другую, то это уже не касательная, а секущая). Предположив наличие некоторой точки в той полуплоскости, в которой лежит касательная, можно точно сказать, по часовой или против часовой стрелки начерчена касательная относительно этой точки, причём не важно, где именно (на каком расстоянии) находится такая точка. Скажем, если касательная проведена слева направо, а фигура лежит под касательной, то направление проведения касательной (слева направо) соответствует направлению «по часовой». Для удобства, мы и найдём такую точку, чтобы вся остальная фигура лежала под ней. Теперь представим, что «входящее» в точку ребро лежит на касательной, и «исходящее» тоже на ней лежит. Т.к. самопересечения у нас недопустимы, возможно только две интерпретации такого предположения: входящее ребро слева от точки касания, исходящее — справа, и наоборот. В первом случае, направление ломаной совпадает с направлением касательной, значит ломаная нарисована по часовой, во втором случае — направление противоположенное, следовательно — против. Если отклонять исходящее ребро к входящему, то, очевидно, что направление не изменится, пока рёбра не совпадут. Аналогично, есто то же самое делать с входящим. Можно сфорумлировать это правило так: кусочек ломаной направлен по часовой, если первое по мере обхода ребро («входящее») лежит правее исходящего. Левее или правее можно сравнивать по углу. Углол можно считать относительно чего угодно, но удобнее считать относительно касательной (у нас она горизонтальна). Тогда, вместо того, чтобы сравнивать углы (которые надо высчитывать, используя обратные триг. функции), можно сравнивать косинусы (большему углу соответствует меньший косинус). Косинусы высчитываются легко: отношение проекции ребра на ось oX к длине ребра. Всё.

ADDED3:

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

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

Сусанишь!

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

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

Ты мало думал. В моём случае при обращении к несуществующему вертексу код будет выполнять дальше (Resume Next, а Next в данном случае — пустой Statement). В твоём случае при обращении к несуществующему вертексу тоже выполнится следующий Statement, в твоём случае это Exit Sub. А надо, чтобы при обращени к несуществующему вертексу код выполнялся дальше.

[Хакер]

Обалдеть!!!
Всем участникам респект за кучу алгоритмов!
Я использовал сумму значений углов. угол = скалярому *, но вместо второго вектора берется его нормаль - получается не cos, a sin угла. чтобы были отрицательные углы.
Уже всё работает!
Самопересечений быть не может - это сечение физ. объекта.

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