RM
Привет!
Size: a a a
2018 May 26
Ι
Как можно найти границы для полигона, если он может быть повёрнут как захочет? Здесь определённо мин/макс по X, Y не пройдёт
EZ
Как можно найти границы для полигона, если он может быть повёрнут как захочет? Здесь определённо мин/макс по X, Y не пройдёт
границы в каком смысле
X
what.
Ι
Красные линии = границы
То есть я нашёл самые крайние точки и провёл квадратную границу
У каждой точки есть позиция по X,Y
То есть я нашёл самые крайние точки и провёл квадратную границу
У каждой точки есть позиция по X,Y
EZ
Красные линии = границы
То есть я нашёл самые крайние точки и провёл квадратную границу
У каждой точки есть позиция по X,Y
То есть я нашёл самые крайние точки и провёл квадратную границу
У каждой точки есть позиция по X,Y
ну минимум X, Y и максимум даст тебе эти 4 линии
Ι
А, точно.. я думал такое решение не пройдёт написав же об этом сам
Ι
Как вдруг представил себе картинку и нашёл крайние точки
MK
Многоугольник выпуклый?
MK
А, впрочем не важно, надо обойти все вершины все-равно
GD
Как можно найти границы для полигона, если он может быть повёрнут как захочет? Здесь определённо мин/макс по X, Y не пройдёт
Отвечаю как не специалист по приложению, только по математике. Ограничение сверху по длине прямоугольника очевидно и достигается тоже очевидно: это диаметр многоугольника, т.е. его наибольшая диагональ. Соответственно, о(n^2) операций, чтобы выиграть. Вторая сторона при этом может быть второй по величине диагональю (достигается для ромба)
GD
Вообще, не совсем ясна формулировка. Какого размера взять прямоугольник, чтобы повернутый полигон гарантировано в него вписался? Тогда см выше. Может асимптотика можно подкрутить, но не факт. Задача о поиске самой длинной диагонали явно гуглится
Ι
Отвечаю как не специалист по приложению, только по математике. Ограничение сверху по длине прямоугольника очевидно и достигается тоже очевидно: это диаметр многоугольника, т.е. его наибольшая диагональ. Соответственно, о(n^2) операций, чтобы выиграть. Вторая сторона при этом может быть второй по величине диагональю (достигается для ромба)
Спасибо!
Понял, с диагоналем тоже вариант)
Понял, с диагоналем тоже вариант)
GD
Спасибо!
Понял, с диагоналем тоже вариант)
Понял, с диагоналем тоже вариант)
А какой контекст задачи, если не секрет? Размер объекта на дисплее?
GD
Спасибо!
Понял, с диагоналем тоже вариант)
Понял, с диагоналем тоже вариант)
Кстати, ещё. Если все упирается в асимптотику, то есть способ читерства. Есть алгоритмы, которые, например, сортируют быстрее квиксорта, но с не 100 вероятностью (сортируют то есть всегда, но иногда быстро, иногда медленно). Возможно, в нашем случае можно что-то такое замутить
Ι
А какой контекст задачи, если не секрет? Размер объекта на дисплее?
Зачада найти размер четырёхугольника, в который вписывается этот многоугольник. Это нужно чтобы изображение правильно наложилось в полигон, так как изображение тоже четырёхугольное
То есть на полигон будет проецироваться изображение
То есть на полигон будет проецироваться изображение
GC
вот тут интерактивный учебник по линейной алгебре, и похоже это настолько хорошо, насколько звучит
MK
вот тут интерактивный учебник по линейной алгебре, и похоже это настолько хорошо, насколько звучит
А почему с афинных пространств начинается? Как-то кверх ногами
GD
Например, я так сходу не сообразил насколько часто диаметром является сторона многоугольника. Закинул в чат математикам. То есть приходит в голову такой некорректный алгоритм: берём первую вершину, берём самую дальнюю от нее. Берём вторую и самую дальнюю от нее. Продолжаем, пока очередная вершина не укажет на предыдущую. Берём эту пару. Возможно, с хорошей вероятностью это быстро и то, что нужно