Ответ на этот вопрос в значительной степени сводится к базовой алгебре: программное обеспечение решает проблему с помощью набора функций, которые генерируют шаблон заполнения для ВСЕГО объема сборки, а затем отбрасывают все, что находится за пределами оболочек. Что определяется алгеброй:

Основы

Функция контура

Предположим, что контур тела является функцией $O(l)$, которая имеет параметр $l$ для своей длины. Эта функция может быть вычислена в координатах XY, что дает нам $y\mapsto O^{xy}(x)$, которая параметризуется после $x$и должна давать нам значения $y$ для замкнутой функции $O(l)$.

Функции Заполнения

Теперь давайте сгенерируем функцию для шаблона заполнения. Давайте упростим это для нас и используем шаблон диагоналей: $I_n(x)=x+n\times d$ где $d$ - фиксированный параметр для "расстояния до последней строки", а $n\in\mathbb Z$ - номер строки, в которой 0 проходит начало координат.

Сравнение: Контур=Заполнение

Теперь начальная алгебра! Пусть компьютер решит для каждого $n$ термин $O(x)=I_n(x)$. Результатом должны быть (в лучшем случае) парные точки, все на линейной функции $I_n(x)$. Сначала отсортируйте эти точки по их коррелирующему $n$, а затем по $x$.

Работа с результатами

Давайте предположим, что у нас есть некоторая форма банана, и наши решения для n=0 выглядят следующим образом: $P_{i=1 \to 4}=\{\{1,1\},\{2,2\},\{3,3\},\{4,4\}\}$

Стартер для моделирования

В самых простых случаях мы надеемся получить только парные результаты - контур замкнут, и поэтому каждая линия, проходящая через него, должна разрезать его на две части. Поскольку мы не допускаем, чтобы геометрия была ниже $\{0,0\}$, линия в этом примере будет проходить в тело при первом решении этих точек и выходить из него при втором и так далее. Как правило: он входит в нечетное и выходит в четное i. Таким образом, наши линии заполнения в примере должны соединить $\{1,1\} \to \{2,2\}$ и $\{3,3\} \to \{4,4\}$.

Совершенствование моделирования

проверка касательных

Теперь у нас может быть нечетное число точек, которые решают O(x)=I_n(x) для данного n. Давайте предположим$P_{i=1 \to 5}=\{1,1\},\{2,2\},\{3,3\},\{4,4\},\{5,5\}$.

Теперь нам нужно быть осторожными, так как одна из этих точек гарантированно будет точкой, в которой $I_n(x)$ является касательной на уровне $O(x)$. Итак, нам нужно знать первый дифференциал $O(x)$ в точках, который является касательной к $O(x)$. Но нам не нужно решать все точки: мы знаем, что первый должен войти, а последний выйти из тела, поэтому нам нужно (в большинстве случаев) решить это только для точек $P_i$ с $i=2 \to i_{max-1}$. Когда $O'(x)=I_n(x)$, мы получаем касательную и удаляем эту точку из списка точек для соединения с линиями заполнения.

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

Кроме того, я использовал "обычно" там намеренно: бывают случаи, когда первая или последняя точка является касательной, и, поскольку это проще сделать, мы должны запустить процесс исключения по всем $P_1 \to P_{max}$!

Новый, уменьшенный набор точек будет представлять собой парный список: $Q_{i=1 \to 4}=\{1,1\},\{2,2\},\{4,4\},\{5,5\}$. Заполнение соединяет $Q_1 \to Q_2$ и $Q_3\to Q_4$.

Превращение точек в векторы

Теперь у нас есть наши точки $Q_1$ и $Q_2$ (или любая другая пара $n \land n+1$, где n-элемент нечетных чисел), как на $I_{n=0}(x)$. Как подключиться? Полегче! $I{n=0}$ - это функция, скорее всего, линейная. Вдоль этой линии должна быть наша соединительная линия от $Q_1\to Q_2$, поэтому движение, которое мы должны построить, является функцией нашего шаблона между точками. Для простого линейного шаблона это будет:

$L_1=\frac{I(x)}{|I(x)|} \times |\vec{Q_2}-\vec{Q_1}|+\vec{Q1}$

Оптимизация

Правильная сортировка

Теперь у нас есть набор строк $L_n$, где, как установлено в последнем абзаце, n-нечетное число, объявляющее, что оно имеет нижний конец $Q_n$и верхний конец $Q_{n+1}$. Как нам грамотно отсортировать эти линии, чтобы у нас было наименьшее движение? Давайте взглянем на наши списки:

• Список P_i, содержащий все касательные точки и конечные точки. Не очень полезно.
• Сокращенный список $Q_{n}$, содержащий все начальные и конечные точки; он отсортирован таким образом, что нечетные числа являются началом и четными концами.
• Список $L_n$ с i всегда нечетным числом, который содержит пути движения (=линии) от каждого $Q_{n}$ до соответствующего $Q_{n+1}$

Кратчайшее перемещение между отпечатками?

Теперь давайте еще раз немного посчитаем: каков ближайший $Q_{a}$ к $Q_{n+1}$, на котором мы закончили после выполнения движения $L_n$? Ну, во-первых, нам нужно убедиться, что мы не вернемся к уже перемещенным путям, поэтому давайте составим новый список $R_{i}$, который содержит все $Q_{i}$, в которые мы еще не переместились.

Итак, каков ближайший $R_{i}$ к конечной точке пути $L_e$, который мы только что переместили? Ну, полегче! Решите $min|R_i-L_e|$, где i-все нечетные числа в списке $R_{i}$ и $L_e$ точка, в которую была отправлена печатающая головка в конце последнего движения

наименьшее количество изменений направления?

Постоянное перемещение только на кратчайшее расстояние может привести к большому количеству изменений направления. Поэтому, возможно, было бы хорошей идеей сохранить списки точек, отсортированных по параметру n функции $l_n(x)$, которая в первую очередь создала точки, и запустить этот список от минимального числа n, которое сгенерировало точки (которые могут быть ниже 0), до максимального числа n, которое сгенерировало точки.

оптимизация изменений направления и траекторий движения

Теперь у нас есть 2 подхода, которые в значительной степени следуют только шаблону. Однако мы могли бы сделать наши средние траектории движения более эффективными, используя простой трюк:

До сих пор все наши линейные функции $l_n(x)$ имели один и тот же вектор и просто отличались друг от друга начальной точкой. Таким образом, все начала были на одной стороне тела, все концы-на противоположной. С помощью очень простого трюка с функцией заполнения мы можем создать группу функций, которые чередуют стороны конечных точек между каждой строкой, просто добавив обратный элемент:

$L_n(x)=-1^n\times l_n(x)$

Теперь, после того, как все движения с одинаковыми $n$ будут выполнены, проверьте ближайшую начальную точку (которая должна быть на той же стороне, но необязательно на соседней линии) и полностью спуститесь по этой линии, исключив эти точки из списка оставшихся точек $R_{i}$. Вернувшись на ту сторону, с которой мы начали сначала, мы снова ищем ближайшую неиспользуемую точку, пробегаем по этой линии, промываем и повторяем.