#диаграмма_вороного — Public Fediverse posts

goYSDA: Как мы в ШАДе переизобрели и сделали непрерывную игру Го, выкинув из него сетку

Привет, Хабр! Все мы знаем Го — глубокую, медитативную игру на доске 19x19. Камни, пересечения, территории... А что, если выкинуть саму сетку и разрешить ставить камни куда угодно в пределах доски? Мы в команде YSDA (Yandex School of Data Analysis или Школа Анализа Данных, ШАД) задались этим вопросом и решили проверить. Получилось азартно, хаотично и, что самое главное для нас как разработчиков, — чертовски интересно с точки зрения алгоритмов. В этой статье я расскажу, как мы реализовали эту идею на Python и Pygame, с какими геометрическими головоломками столкнулись и как Диаграмма Вороного помогает считать очки в реальном времени, превращая статичную доску в живое поле битвы. Погрузиться в игру →

https://habr.com/ru/companies/datafeel/articles/926338/

#python #pygame #игра_го #алгоритмы #вычислительная_геометрия #shapely #bfs #настольная_игра #разработка_игр #диаграмма_вороного

Об одном интересном свойстве триангуляции Делоне

В процессе решения некоторой задачи, я наткнулся на одно интересное свойство триангуляции Делоне , которое мне не удалось загуглить, как и его применение к решению разных задач. Я уверен, что не являюсь его первооткрывателем, но оно, по крайней мере, не является широко известным. Поэтому я решил написать о нем статью. Свойство: Если какой-то отрезок AB не включен в триангуляцию Делоне, то существует путь из A в B по отрезкам из триангуляции, такой что все отрезки там не длиннее |AB|. На картинке выше отсутствующий отрезок показан красным цветом, а путь - зеленым цветом. Дальше в статье я приведу пример его использования в задачах, а также формальное его доказательство. Если вам известно более красивое доказательство этого свойства, или вы его где-то видели - поделитесь, пожалуйста, в комментариях. Также буду благодарен, если вы поделитесь другими решениями для приведенных в статье задач или аналогичными задачами.

https://habr.com/ru/articles/828610/

#алгоритмы #триангуляция_делоне #диаграмма_вороного #математика #доказательство