Триангуляция по косточкам
Всё началось невинно. Шёл 2009 год, и я просто хотел портировать Earcut на Flash - для своей мини-игры. Тогда это сработало, но с годами стало понятно: простые решения перестают работать, как только хочешь выжать из них максимум. Триангулировать
Об одном интересном свойстве триангуляции Делоне
В процессе решения некоторой задачи, я наткнулся на одно интересное свойство триангуляции Делоне , которое мне не удалось загуглить, как и его применение к решению разных задач. Я уверен, что не являюсь его первооткрывателем, но оно, по крайней мере, не является широко известным. Поэтому я решил написать о нем статью. Свойство: Если какой-то отрезок AB не включен в триангуляцию Делоне, то существует путь из A в B по отрезкам из триангуляции, такой что все отрезки там не длиннее |AB|. На картинке выше отсутствующий отрезок показан красным цветом, а путь - зеленым цветом. Дальше в статье я приведу пример его использования в задачах, а также формальное его доказательство. Если вам известно более красивое доказательство этого свойства, или вы его где-то видели - поделитесь, пожалуйста, в комментариях. Также буду благодарен, если вы поделитесь другими решениями для приведенных в статье задач или аналогичными задачами.
https://habr.com/ru/articles/828610/
#алгоритмы #триангуляция_делоне #диаграмма_вороного #математика #доказательство
Метод конечных элементов своими руками
Метод конечных элементов (МКЭ) применяют в задачах упругости, теплопередачи, гидродинамики — всюду, где нужно как-то дискретизировать уравнения сплошной среды или поля. На Хабре было множество статей с красивыми картинками о том, в каких отраслях и с помощью каких программ этот метод приносит пользу. Однако мало кто пытался объяснить МКЭ от самых основ, с простенькой учебной реализацией, желательно без упоминания частных производных через каждое слово. Мы напишем МКЭ для расчёта упругой двумерной пластины на прочность и жёсткость. Код займёт 1200 строк. Туда войдёт всё: интерактивный редактор, разбиение модели на треугольные элементы, вычисление напряжений и деформаций, визуализация результата. Ни одна часть алгоритма не спрячется от нас в недрах MATLAB или NumPy. Код будет ужасно неоптимальным, но максимально ясным. Размышление над задачей и написание кода заняли у меня неделю. Будь у меня перед глазами такая статья, как эта, — справился бы быстрее. У меня её не было. Зато теперь она есть у вас.
Habr
