Алгоритм заполнения многоугольника

Question

Я работаю над утилитой для нарезки сетки для 3D-печати. В общем случае он должен нарезать 3d-сетчатую модель на 2d-фигуры (несколько полигонов, возможно с отверстиями) и заполнить их дорожками определенной толщины с использованием определенного шаблона. Эти пути будут использоваться для генерации команд gcode для прошивки 3D-принтера.

Существуют различные инструменты с открытым исходным кодом с одинаковыми целями, написанные на python и perl. Но моя цель - понять рабочий процесс slicer и написать собственный инструмент на C или C++.

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

Может ли кто-нибудь советовать, как создавать эти пути заполнения? Благодарю.

---

В настоящее время я использую следующий алгоритм:

1. Найти ограничительную рамку формы
2. Split Bb вертикально с линиями (количество строк = bb.width/path.thickness)
3. поиск точек пересечения для каждой формы и линии (должно быть две точки на линии)
4. построить сегменты из этих точек со смещением от границы
5. Добавить сегменты, которые соединяют оригинальный сегменты вместе образуют линию полосы
6. Мы готовы генерировать GCode или нарисовать путь

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

Answer 1

После некоторого времени исследования я закончил работу по следующему алгоритму: Однако существует ряд возможностей оптимизации.

Answer 2

Вы можете посмотреть на this webpage об алгоритмах применения штриховки в регионах.

Answer 3

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

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

Теперь сформируйте граф, взвешенный по краю, содержащий вершину для каждой точки, с ребром, соединяющим две вершины, когда их соответствующие точки меньше или равны одному блоку сетки. Также добавьте края между соседними крайними точками сегментов линии и между соседними нижними точками. Используйте евклидово расстояние между точками для веса края.Наконец, волшебная часть: найдите минимальный вес Hamiltonian path на этом графике. Это путь, который посещает каждую вершину ровно один раз и имеет минимальную длину. Ограничение минимальной длины гарантирует, что путь никогда не пересечет себя, поскольку, если любые две линии пересекаются, скажем, строка от a до b и строка от c до d, тогда всегда будет возможно создать более короткий общий путь, удалив эти две строки и создание двух новых строк с использованием другой комбинации конечных точек (либо --- c, и b --- d, либо --- и b --- c). Это путь, который вы заполните.

Поиск пути гамильтониана (не говоря уже о гамильтоновском пути минимального веса) является NP-трудной задачей, которая тесно связана с более известной проблемой Traveling Salesman. Поскольку многие хорошие точные решатели TSP уже существуют (например, Concorde), было бы разумно вместо этого использовать один из них, чтобы найти путешествие для путешествующих, а затем просто удалить один из ребер, чтобы создать короткий путь Гамильтона. (Даже если вы удалите самый тяжелый ребро, это не обязательно приведет к гамильтоновскому пути минимальной длины, поскольку может быть, что существуют более короткие пути, которые не начинаются и не заканчиваются на соседних вершинах, но мы не очень заботимся о общая длина здесь, нам просто нужен путь, который посещает все вершины и не пересекает себя.)

К сожалению, на графике не гарантируется ни гамильтонов путь, ни путешествие путешествующих продавцов. (Очевидно, что они не могут существовать, если граф отключен, например, но даже подключенные графы могут не иметь одного или обоих: например, граф с любой вершиной степени 1 не может иметь тур TSP.) В этом случае, если Решатель TSP, который вы используете, может найти туры, которые не посещают все вершины, вы можете просто повторить это, пока не будут охвачены все вершины. Если этого не случится, я вернусь к исходному алгоритму.