Сортировка по полярному углу относительно точки

Помогите пожалуйста с проблемой, у меня есть множество точек в декартовой системе координат. Как отсортировать их по полярному углу относительно нижней-левой точки?

0

сортируйте по косинусу угла

0

Сообщение от Shamil1 сортируйте по косинусу угла

Хотя в 3D это может не иметь смысла

0

Сообщение от Shamil1 сортируйте по косинусу угла

проще по тангенсу - это отношение разницы абсцисс и ординат двух точек

0

Сообщение от vlisp проще по тангенсу - это отношение разницы абсцисс и ординат двух точек

по тангенсу нельзя
во-первых, он не определён для пи/2
во-вторых, он не является монотонной функцией на отрезке [0, пи]

0

Угол между точками равен

Сообщение от Shamil1 по тангенсу нельзя во-первых, он не определён для пи/2 во-вторых, он не является монотонной функцией на отрезке [0, пи]

Что делать, если угол лежит в нижней полусфере [pi, 2pi]?
Во многих языках есть встроенная функция atan2, в лиспе функция tan может принимать 2 аргумента. Диапазон значений [-pi pi] - это уже целая окружность, все что нужно сделать - посчитать разности абсцисс и ординат точек.

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

0

Сообщение от vlisp Что делать, если угол лежит в нижней полусфере [pi, 2pi]?

Угол не может лежать в нижней полусфере. (по условию задачи)

Сообщение от vlisp Вычисление корня и тригонометрических функций - это по сути вычисление рядов.

По моему опыту вычисление корня занимает примерно столько же времени, сколько деление. И в два раза меньше времени, чем непредсказуемое ветвление.
(но если Вы принципиально против корней, то от них можно легко избавиться, домножив на abs(cos))

Сообщение от vlisp Диапазон значений [-pi pi] - это уже целая окружность, все что нужно сделать - посчитать разности абсцисс и ординат точек.

Не совсем понял, что это значит. Но если Вы предлагаете сначала вычислять и сравнивать квадранты, то см. выше про непредсказуемое ветвление.

0

Сообщение от Shamil1 Угол не может лежать в нижней полусфере. (по условию задачи)

Где это написано?

0

в условии:

Сообщение от nexs относительно нижней-левой точки

0

Сообщение от Shamil1 относительно нижней-левой точки

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

0

Сообщение от vlisp ах, ну, да... если квадрат повернуть на 45 градусов, где будет левая нижняя точка?

внизу
только не "левая нижняя", как Вы пишете, а "нижняя-левая", как в условии.

Сообщение от vlisp А если точка будет в нижнем левом углу, чему будет равен синус???

не понял, если квадрат повернуть на 45%, то какой угол можно назвать "нижним левым"?
точка будет внизу, а синус нас не интересует, так как не используется в алгоритме

Сообщение от vlisp От условия тут не избавиться в любом случае

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

0

Сообщение от Shamil1 не понял, если квадрат повернуть на 45%, то какой угол можно назвать "нижним левым"?

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

0

Сообщение от vlisp Вот и я о том же

а я о другом
я не знаю, какой угол будет "нижним левым", а "нижнюю-левую" точку назову легко (я и назвал), так что никакой неточности в ней нет

Сообщение от vlisp Если речь идет о прямоугольнике ограничивающем точки, то в нижнем левом углу может не быть ни одной точки, а может и быть и не одна...

возьмите описание любого алгоритма, используещего подобные углы
например, алгоритм Джарвиса для вычисления выпуклой оболочки:
"В качестве начальной берётся самая левая нижняя точка"
то есть, это устоявшийся термин
левая нижняя точка - это самая левая точка, а если таких несколько, то самая нижняя из них

Сообщение от vlisp В таком случае расстояние до точки из угла равно нулю и косинус не посчитать

если "нижних левых" точек несколько, то это выяснится на этапе вычисления нижней левой точки
да, на этом этапе без сравнения не обойтись, но этот этап имеет меньшую сложность = O(n)
и на этом этапе мы косинусы не вычисляем, так что никаких проблем с вычислением косинуса не будет

0

Сообщение от Shamil1 это выяснится на этапе вычисления нижней левой точки

Точно так же можно отфильтровать точки, которые дают деление на ноль при вычислении тангенса

Сообщение от Shamil1 я не знаю, какой угол будет "нижним левым", а "нижнюю-левую" точку назову легко (я и назвал), так что никакой неточности в ней нет

Точка, ниже которой нет других точек, хоть и самая нижняя, не необязательно самая левая, то, есть она может входить в исходное множество, а может и не входить, чтоб это проверить, нужно сравнивать и x и y, каждой точки с минимальными значениями, чтоб не получить деление на ноль. В моем случае достаточно проверить только значение x, чтоб не получить значение на ноль

0

Сообщение от vlisp Точно так же можно отфильтровать точки, которые дают деление на ноль при вычислении тангенса

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

Сообщение от vlisp Точка, ниже которой нет других точек, хоть и самая нижняя, не необязательно самая левая, то, есть она может входить в исходное множество, а может и не входить

а нам и не надо, чтобы она была самой левой - прочитайте внимательно, что я написал
а в множество она входит по-определению - мы выбираем среди точек множества
если Вас не устраивает общепринятое толкование термина "нижняя левая точка множества", то спросите у ТС, что он имеет ввиду

Сообщение от vlisp В моем случае достаточно проверить только значение x, чтоб не получить значение на ноль

недостаточно (если числа не целые)
можно получить переполнение, просто деля большое число на маленькое


vlisp,
Вы уже 3 раза меняли/дополняли свой алгоритм, а он всё не работает. Что Вы хотите доказать? Что, когда Вы, наконец, учтёте все ньюансы и составете работающий алгоритм, то он будет проще моего?

на всякий случай, напомню Вам, что является предметом дискуссии:

Сообщение от vlisp проще по тангенсу

Вы по-прежнему утверждаете, что проще сортировать по тангенсу?

0

Сообщение от Shamil1 Вы по-прежнему утверждаете, что проще сортировать по тангенсу?

Я так понимаю вы про это говорите? https://ru.wikipedia.org/wiki/Алгоритм_Джарвиса и ему подобные? Ну так там все написано, что тут обсуждать? Заморочили мне голову...

0