Алгоритм определения визуального центра многоугольника — полюса недоступности
Представьте, что многоугольник -- это озеро, в котором нужно найти самую глубокую точку. Алгоритм ищет ее с помощью сетки, сплетенной из квадратов:
1. Накрывает озеро сеткой из больших квадратов.
2. Оценивает потенциал каждого квадрата, то есть расстояние от центра квадрата до берега (стороны многоугольника) плюс половина диагонали. Это максимально возможная глубина под этим квадратом.
3. Отсекает лишнее: если потенциал квадрата меньше уже найденной глубины, он отбрасывается -- там точно не глубже.
4. Дробит лучшее: самые перспективные квадраты делятся на 4 мелких, и цикл повторяется.
Вместо проверки каждой точки алгоритм быстро отсекает целые участки, пока не сузит поиск до крошечного квадратика. Его центр и есть нужный визуальный центр.
#алгоритм
↓
Представьте, что многоугольник -- это озеро, в котором нужно найти самую глубокую точку. Алгоритм ищет ее с помощью сетки, сплетенной из квадратов:
1. Накрывает озеро сеткой из больших квадратов.
2. Оценивает потенциал каждого квадрата, то есть расстояние от центра квадрата до берега (стороны многоугольника) плюс половина диагонали. Это максимально возможная глубина под этим квадратом.
3. Отсекает лишнее: если потенциал квадрата меньше уже найденной глубины, он отбрасывается -- там точно не глубже.
4. Дробит лучшее: самые перспективные квадраты делятся на 4 мелких, и цикл повторяется.
Вместо проверки каждой точки алгоритм быстро отсекает целые участки, пока не сузит поиск до крошечного квадратика. Его центр и есть нужный визуальный центр.
#алгоритм
↓
❤2
Алгоритм подробно описан в блоге (на английском) и на Хабре (на русском), куда я вас и приглашаю.
Также есть яваскриптовая и си-плюс-плюсная библиотека для поиска полюса недоступности -- polylabel, что-то на Питоне и других языках. То есть все уже разжевано и готово к употреблению.
↓
Также есть яваскриптовая и си-плюс-плюсная библиотека для поиска полюса недоступности -- polylabel, что-то на Питоне и других языках. То есть все уже разжевано и готово к употреблению.
↓
Medium
A new algorithm for finding a visual center of a polygon
We came up with a neat little algorithm that may be useful for placing labels and tooltips on polygons, accompanied by a JavaScript library. It’s now going to be used in Mapbox GL and Mapbox Studio…
❤2
-- А зачем все это нужно было?
Как зачем?! Для надписей! Вот перед вами карта. Она состоит из многоугольных областей неправильной формы. И вы желаете подписать каждую область, да так, чтобы надписи находились строго в визуальной центре каждого многоугольника. Вот тут то вам и пригодиться полюс недоступности -- это идеальное место для расположения центра подписей.
Кроме того, из заметки вы поняли, что понятие центр может иметь много разных определений. Поэтому когда вы говорите про центр фигуры, всегда уточняйте, какой именно центр вам нужен.
———
Иллюстрация из статьи "Сколько математики нужно, чтобы подписать многоугольник в JS API Яндекс.Карт".
↓
Как зачем?! Для надписей! Вот перед вами карта. Она состоит из многоугольных областей неправильной формы. И вы желаете подписать каждую область, да так, чтобы надписи находились строго в визуальной центре каждого многоугольника. Вот тут то вам и пригодиться полюс недоступности -- это идеальное место для расположения центра подписей.
Кроме того, из заметки вы поняли, что понятие центр может иметь много разных определений. Поэтому когда вы говорите про центр фигуры, всегда уточняйте, какой именно центр вам нужен.
———
Иллюстрация из статьи "Сколько математики нужно, чтобы подписать многоугольник в JS API Яндекс.Карт".
↓
👍1🔥1
Если кто-то из вас сочтет нужным поддержать мои посты финансово, или одарить меня чашкой ароматного кофе с пироженкой, то это можно сделать переводом на карту Т-банка:
2200 7008 9040 4238
Антон Л.
Или переводом по ссылке:
https://pay.cloudtips.ru/p/a6d81e5a
Буду благодарен за любую поддержку.
2200 7008 9040 4238
Антон Л.
Или переводом по ссылке:
https://pay.cloudtips.ru/p/a6d81e5a
Буду благодарен за любую поддержку.
❤1⚡1
Абсолютная геометрия
В ВК вышла моя заметка про абсолютную геометрию Это геометрия, в которой нет пятой аксиомы Евклида о параллельных прямых.
Переходите, будет интересно.
https://vk.com/wall-186208863_71398
#геометрия #евклид
x x x
В ВК вышла моя заметка про абсолютную геометрию Это геометрия, в которой нет пятой аксиомы Евклида о параллельных прямых.
Переходите, будет интересно.
https://vk.com/wall-186208863_71398
#геометрия #евклид
x x x
Механические калькуляторы для расчета последствий ядерного взрыва.
https://www.orau.org/health-physics-museum/collection/nuclear-slide-rules/weapons-effects/index.html
Интересно было бы разобраться в их работе.
#математика #арт
x x x
https://www.orau.org/health-physics-museum/collection/nuclear-slide-rules/weapons-effects/index.html
Интересно было бы разобраться в их работе.
#математика #арт
x x x
✍2🔥1
Sean Dinen
Multivariate Calculus and Geometry
2014
Изучение многомерного анализа часто сводится к сухому манипулированию формулами, теряя связь между алгеброй и геометрией. Третье издание монографии Шона Динина предлагает альтернативу, опираясь на геометрическую интуицию, наглядные аргументы и строгие доказательства.
#книга #геометрия #матанализ
↓
Multivariate Calculus and Geometry
2014
Изучение многомерного анализа часто сводится к сухому манипулированию формулами, теряя связь между алгеброй и геометрией. Третье издание монографии Шона Динина предлагает альтернативу, опираясь на геометрическую интуицию, наглядные аргументы и строгие доказательства.
#книга #геометрия #матанализ
↓
❤1
Главная ценность книги Динина — методический переход от базовых понятий к сложным конструкциям через геометрический смысл. Автор последовательно ведет читателя от частных производных и экстремумов к теории кривых и поверхностей, криволинейным и поверхностным интегралам. Кульминация — теоремы Гаусса—Остроградского и Стокса, основы дифференциальной геометрии. Геометрический фокус углубляет понимание результатов.
Учебник для старшекурсников, владеющих линейной алгеброй и базовым анализом, но подходит и для самостоятельного изучения благодаря ясному стилю и подробным решениям.
Книга связывает многомерный анализ и дифференциальную геометрию, являясь одним из лучших современных руководств для понимания внутренней геометрии многомерных пространств.
↓
Учебник для старшекурсников, владеющих линейной алгеброй и базовым анализом, но подходит и для самостоятельного изучения благодаря ясному стилю и подробным решениям.
Рецензенты отмечают баланс строгости и доступности.
Книга связывает многомерный анализ и дифференциальную геометрию, являясь одним из лучших современных руководств для понимания внутренней геометрии многомерных пространств.
↓
❤🔥2
"Начала" Евклида в цвете
Если вам довелось открывать "Начала" Евклида, то их чтение вряд ли доставило вам большое удовольствие. Это многотомный труд. Его текст витиеват, труднодоступен для понимания, местами алогичен, его много, а рисунков и чертежей мало и, главное, они черно-белые.
Затем, из отрицания пятого постулата родились гиперболическая и сферическая геометрии.
#геометрия #евклид #книга
↓
Если вам довелось открывать "Начала" Евклида, то их чтение вряд ли доставило вам большое удовольствие. Это многотомный труд. Его текст витиеват, труднодоступен для понимания, местами алогичен, его много, а рисунков и чертежей мало и, главное, они черно-белые.
В "Началах" Евклид сформулировал пять постулатов, на которых основана евклидова геометрия.
Затем, из отрицания пятого постулата родились гиперболическая и сферическая геометрии.
#геометрия #евклид #книга
↓
❤2