Рубрика «многоугольники»

Всё началось невинно. Шёл 2009 год, и я просто хотел портировать Earcut на Flash — для своей мини-игры. Тогда это сработало, но с годами стало понятно: простые решения перестают работать, как только хочешь выжать из них максимум.

Я углубился в теорию, и начал перебирать статьи и просматривать ролики на youtube. Сильно помогла книга А.В. Скворцова. В итоге я остановился на подходе разбиения на монотонные многоугольники. Он казался самым очевидным. И ох, сколько я набил себе шишек, пока его реализовал.

Первым прорывом стало осознание, что float нужно заменить на intЧитать полностью »

Как неуловимый «эйнштейн» помог решить давнюю математическую задачу - 1

В ноябре прошлого года, после десяти лет неудачных попыток, Дэвид Смит, самопровозглашенный «любитель фигур» из Бридлингтона в Восточном Йоркшире, Англия, заподозрил, что, возможно, он наконец-то решил давнюю задачку в математике замощения плоскости: иначе говоря, он решил, что нашёл «эйнштейна».

В менее поэтичных терминах, «эйнштейн» — это «апериодическая моноплитка», фигура, которая покрывает плоскость или бесконечную двумерную плоскую поверхность неповторяющимся образом. (Термин «эйнштейн» происходит от немецкого «ein stein» или «один камень», в более свободной трактовке — «одна плитка» или «одна фигура»). Ваши обычные обои или кафельный пол представляют собою часть бесконечного узора, который периодически повторяется; при смещении или «переносе» узор может быть точно наложен сам на себя. Апериодическая плитка не обладает такой «трансляционной симметрией», и математики давно ищут единственную фигуру, которая могла бы покрыть плоскость такой плиткой. Эта задача известна под названием «проблемы Эйнштейна».
Читать полностью »

Недавно на хабре была статья, в которой описывалось как можно определить, где находится точка по отношению к многоугольнику: внутри или снаружи. Подобная проблема встречается в геометрическом моделировании и в компьютерной графике достаточно часто. А так как метод, описанный в статье, был несколько не оптимален, а в комментариях был небольшой хаос, возникла мысль написать эту статью. Итак, какие алгоритмы существуют в современной компьютерной графике, чтобы определить, принадлежит ли заданная точка многоугольнику или нет.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js