Дана произвольная фигура с замкнутым контуром.Требуется "заполнить" фигуру графическими примитивами (прямоугольниками минимальный размер стороны и максимальный размер стороны которых известны).Примитивы можно вращать, дискретность вращения - 1 градус. Цель сводится к максимальной аппроксимации этой фигуры графическими примитивами при заданной величине погрешности. Т.е. аппроксимация с заданной величиной погрешности.
God_Father Опишите контур фигуры. Матчасть я сдесь вылаживал подробную. Использовал для выделения образов и быстрой заливки фигур. Добавлю что есчо во времена спектрума юзал для заливки.
Судя по картинке, прямоугольники могут пересекаться. Тогда можно просто задать начальное разбиение какой-нибудь прямоугольной сеткой, потом пройтись по границе фигуры, расставляя прямоугольники вдоль неё, где потребуется.
Clerk допустим фигуру разбил на полигон, который аппроксимирует её с заданной точностью. (стороны аппроксимировал отрезками заданной длины), дальше что? Ravager а как потом обнаруживать пустые места, где нет прямоугольников?
Надо взять точки пересечения линий сетки с контуром фигуры, участок между двумя такими соседними точками аппроксимировать отрезком или ломаной, эти отрезки и будут основаниями добавочных прямоугольников.
Хорошо, а вот у меня полигоном из N точек аппроксиморован бублик с дыркой. Как мне узнать, куда строить добавочный прямоугольник, наружу или внутрь. Тоесть мне нужен алгоритм, который определит находится ли точка на бублике или в другом месте (дырка или снаружи). Естественно бублик со швом, который связывает его внутренний контур с наружным.
Это как я понял алгоритм трассировки луча нужен, чтоб определить находится ли точка в бублике или нет. Теперь про построение, а если угол между 3-мя точками острый, то тут как?
По-моему задача сводится к нахождению OBB(oriented bounding box). Только поиск не описанных боксов, а вписанных. Находим первый вписанный бокс(по алгоритмам схожими с описанными), получаем множество фигур которые нужно разбивать далее, и продолжаем разбивать. Также у нас есть некий люфт(наложение), который позволяет улучшать алгоритм. Но вообще алгоритмы нахождения OBB, не слишком быстры и порой требуют квадратичной сложности.
