Реализация автоматического алгоритма масштабирования c линейных сегментов

Question

Я получаю следующие точки в качестве входных данных:

Point A(200 ; 400)
Point B(400 ; 400)
Point C(400 ; 200)
Point D(600 ; 200)
Point E(700 ; 500)
Point F(500 ; 700)
Point G(200 ; 600)

Эти точки образуют сегменты AB, B C, CD, DE, EF, FG и GA, которые будут нарисованы таким образом:

Теперь мне было поручено написать алгоритм автоматического масштабирования c, основанный на ближайших числах, определяющих длину реального сегмента:

Поскольку мне приходится самостоятельно определять ограничения, я просто решил сделать все возможное, чтобы углы не изменились. Во-первых, я определяю самый длинный сегмент, чтобы установить sh шкалу (например, «с меткой длины 6» = 250 пикселей, затем с меткой длины 1 ~ = 41,7).

Затем я обрабатываю следующий сегмент короче, измените его масштаб с центра и примените тот же векторный перевод к соседнему элементу.

Это лучший вывод, который я могу получить прямо сейчас:

Но этот метод будет в конечном итоге бесконечным l oop, или будет действительно неточным в других случаях, особенно когда линии нарисованы от руки и не совсем прямые.

Существуют ли хорошо известные алгоритмы для решения эта ситуация? Я понятия не имею, с чего начать при поиске в некоторых геометрических библиотеках, таких как GEOS, libigl, ...

Answer 1

Очень тяжелая проблема, если вы углубитесь в это. Наивное масштабирование путем умножения на константу не подлежит сомнению, поскольку это меняет форму, углы и т. Д. c ...

Для увеличения и сжатия многоугольников лучше всего использовать методы смещения сторон внутрь / наружу в перпендикулярном направлении и отремонтируйте точки соединения впоследствии. Но остерегайтесь его очень сложной проблемы, здесь есть некоторые основы:

• нарисуйте контур для некоторых соединенных линий
• Как создать внутреннюю спираль для многоугольника ?

Ваша проблема в этом случае добавляет неизвестные длины сторон. Очень похоже на технику резки бумажных коробок (но гораздо проще). Поэтому, с моей точки зрения, вы должны:

1. кодировать ваш многоугольник в полярном кодировании

   , поэтому вместо простой декартовой системы используйте также полярные линии. Полигон кодируется как набор соединенных линий (l oop). Каждая строка нуждается в этой информации:

   float angle;
   float length;
   int flag;
   float x0,y0,x1,y1; // computed endpoints for rendering
   

   angle может быть вычислено как atan2(y1-y0,x1-x0), а длина очевидна sqrt((x1-x0)^2+(y1-y0)^2). Флаг может хранить, какое из значений является окончательным (измеренным).

2. установить измеренные значения

   , поэтому измените длины сторон, которые вы знаете, и установите их флажки соответственно

3. снова пересчитать конечные точки

   line[i].x0=line[i-1].x1;
   line[i].y0=line[i-1].y1;
   line[i].x1=line[i].lengths*cos(line[i].angle);
   line[i].y1=line[i].lengths*sin(line[i].angle);
   

   , где x0,y0 в первой строке будет началом вашего полигона. Чтобы вычислить строку, предыдущий сегмент должен быть вычислен, и должны быть установлены все значения фактической линии. Поэтому вычислите все строки, которые вы можете, и остановите, когда больше строк не будет вычислено.

   Если у вас нет информации о позиции из предыдущей строки, вы должны пометить это как плавающую позицию и выбрать несколько вслепую (например, (0,0)) .

4. примерка

   будет множество невычисленных линий (с ненастроенными действительными длинами / углами). если строка до и после вычислена, вы можете просто использовать их x0,y0,x1,y1

   , если вы вычислили строку, а следующая помечена как плавающая, пересчитайте ее и всех ее последователей до тех пор, пока не будет вычислена или не будет достигнута та же строка.

   реальная проблема - набор подключенных невычисленных линий. для них вы можете масштабировать, умножая на константу + перевод или изменяя длину первой и последней строки, пока они не соединят вычисленные части. Зависит от того, какие свойства формы вы хотите сохранить.

Как видите, это не простая задача, и, скорее всего, будут некоторые крайние случаи, которые я забыл обработать.

Геометрия масштабируемой бумажной коробки основана на уравнениях масштабирования. Каждое измерение линии определяется строкой, а не числом, а также может использовать полярное и декартовое (переключаемое) представление линий. Строка может содержать число, предопределенную константу размера или уравнение. Таким образом, изменяя всего несколько коэффициентов (обычно высоту, ширину, глубину, толщину бумаги в коробке), вся форма масштабируется без необходимости подгонки. Но создание такой геометрии не простая задача. Есть машины для создания коробок (режущие и скремблирующие / внедряющие плоттеры), такие как BoxMaker, но для них обычно требуется дорогая машина, подключенная для работы, и они не предназначены для бесплатного использования.

Если вы хотите вместо этого использовать go вам нужно будет выполнить оценку выражения, см .:

• Знак символа c алгебра c выражение