Нахождение углов произвольного многоугольника.

[KoPPeW]

Суть задачи состоит в нахождение углов произвольного n-угольника, известны координаты вершин и порядок их соединения. Вообще задача сводиться к построению облака вокруг многоугольника, но для того чтобы это облако нормально выглядело необходимо вычислить углы фигуры вокруг которой оно строиться. Единственное решение которое я нашел это вычисление угла по скалярному произведению и определение внутренний он или внешний с помощью выбора произвольной точки в направлении сторон образующих данный угол. Задаю данный вопрос в данном разделе, так как не нашел раздела алгоритмы.

[Kukurudza]

ну так и находи, в чем проблема то? или код писать лень?
вряд ли кто то захочет брать калькулятор и сидеть тыкать координаты и тп.

[Granus]

Единственное решение которое я нашел

Ну дак и используйте его. Могу разве что дополнить, что достаточно будет сначала узнать, с какой стороны от первого отрезка находится фигура - она будет с той же самой стороны для всех отрезков (это дополнение к "внутренний он или внешний").

[KoPPeW]

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

[Abstraction]

Затратный? Считаем векторы сторон (вычитания, 2n), считаем скалярные произведения (произведения, 2n), считаем длины и делим (делений, 2n).
Подсчёт длин можно ускорить за счёт точности (классический пример).

[KoPPeW]

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

[Abstraction]

Кстати, можно как-то использовать для этого векторное произведение?

Ну, можно, но нафига? Или облако в пространстве? Но тогда нужен не многоугольник, а многогранник...

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

Поток сознания. O(1) не будет со всей очевидностью, потому как требуется сгенерировать на выходе набор из n переменных. С другой стороны: тесты производительности уже нашли проблему в этом месте? Или Вы только предполагаете, что ~8n умножений это слишком много? Если второе, то сделайте пока тупо квадратные облака по габаритному прямоугольнику и посмотрите на скорость.

[KoPPeW]

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