Нужен совет (алгоритм)

[Sirik]

Имеется схема такого вида (простой вариант):


Необходимо обойти все зеленые области с некоторым шагом, на практике будет видно с каким. Координаты конечных точек, поворотов имеются, хотя это не сильно важно. В принципе обход одной области можно сделать легко, но как потом перейти на следующую? А если несколько дорожек проходят близко друг от дуга, как тогда быть? вот пример:


У кого будут какие идеи?

[Хакер]

У меня будут идеи.
viewtopic.php?f=73&t=42590

[Sirik]

post_what_you_get.png

[Хакер] :: Почему вы используете картинкообменник, на котором надо регистрироваться, чтобы не видеть эту мерзкую лягушку, при том, что на форуме есть механизм аттачей?

[Хакер]

Я не знаю, что на картинке, но наверное позволяет. Почему бы тебе не прочитать топик?

И поменяй название темы!

[Sirik]

всегда отвечал "Быстрым ответом" и не знал что можно атачить фалы(
вот атач:

Схема 1

схема1.png (9.01 Кб) Просмотров: 3284

ps/ на что поменять название темы?

[Хакер]

Найдёт, конечно.
Конкретно в данном случае алгоритм даст 8 контуров.
Контрур левой дорожки + два контура для двух отверстий + контур правой жорожки + три контура трёх дырок + контур полости.

[Sirik]

мне бы получить 3 контура: левой дорожки, правой дорожки и полость
и если не секрет сколько времени занимает расчет для данной схемы? почему возник данный вопрос, потому что это всего лишь частный случай, на деле схемы буду гораздо сложнее

[Хакер]

мне бы получить 3 контура: левой дорожки, правой дорожки и полость

Вот это мне нравится. Когда начинают говорить: мне нужно получить N контуров.
На картинке 8 замкнутых контуров. Если тебя не интересуют контуру дырок, то это вопрос не к алгоритму, а к поставщику данных для него. Не надо поставлять дырки как белые (а не зелёные) пикселы.

и если не секрет сколько времени занимает расчет для данной схемы?

В каком плане расчёт? Контурообход?
В том топике по сути есть два вопроса.
1) Контурообход. Составление списка точек, устранение разрешимых и неразрешимых тупиков, выполнение BCT.
2) Составление списка пикселей контура. Метод смыкающихся островков.

Это не две альтернативы, а два необходимых этапа, второе даёт данные для первого. Каждое занимает своё время. Для второго есть альтернативные решения.

Прочитай тот топик от корки до корки.

[Sirik]

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

схема2.png (8.1 Кб) Просмотров: 3276

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

[Хакер]

Я думал тебе надо из растрового изображения получить векторное.
А теперь надо из картинки получить красные стрелки?

Зачем это вообще нужно? Уж не траектория ли для фрезеровки?

[Proxy]

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

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

Уж не траектория ли для фрезеровки?

Скорее для плоттера (или его аналога), угадал?

[Хакер]

Тут вопрос в другом.
К чему нужно заниматься такой глупостью, как работа над битмапом, если любая подобная программа, включая P-CAD (судя по фотографии), умеет делать экспорт в Gerber-формат, который векторный и как раз для фрезеров/плоттеров (и только для них) предназначен.

[Proxy]

К чему нужно заниматься такой глупостью, как работа над битмапом, если любая подобная программа, включая P-CAD (судя по фотографии), умеет делать экспорт в Gerber-формат, который векторный и как раз для фрезеров/плоттеров (и только для них) предназначен.

Хотя бы потому, что это автор сабжа сам изъявил такое желание.

[Хакер]

Может он не знает о G-кодах.

[Sirik]

Знаю я G-коде и нормально читаю Gerber формат. Дело в том, что все программы, которые я видел делаю экспорт в Gerber формат только для плоттеров, мне же нужна фрезеровка по контуру. Тем более, что для Gerber формата надо писать свой минидрайер (не могу подобрать нужного слова) ).
Красные стрелки - это переход от одной области к следующей, причем я хочу чтобы чтобы эти переходы были минимальными.

[Хакер]

Так ты подробнее опиши, что ты делаешь? Самодельный плоттер?

[Proxy]

Знаю я G-коде и нормально читаю Gerber формат. Дело в том, что все программы, которые я видел делаю экспорт в Gerber формат только для плоттеров, мне же нужна фрезеровка по контуру.

А мне случайно показалось, что на схемах токопроводные дорожки печатных плат, не выточенные фрезером непонятного предназначения загигулины А чем для решения поставленной задачи не устраивает векторизация контуров вышеизложенными способами?

[Хакер]

Если есть Gerber-файлы, то заниматься векторизацией — это всё равно, что имея исходники, заниматься дизассемблированием, или имея проём в стене, грызть зубами новый.

Сделать из Gerber-файла, предназначенного для фотоплоттера, Gerber-файл, предназначенный для фрезерного станка, это в 1000 раз лучшее и простое решение, чем возиться с векторизацией растра.

[Proxy]

Мне из сабжевого вопроса показалось, что автор располагает только растровыми изображениями. Видимо что-то упустил или был не внимателен.

[Sirik]

Есть схема, начертил для примера, из нее можно сделать экспорт как в растр так и в Gerger. В последний только для плоттера, вот для примера: есть точка А и точка Б соединенные дорожкой (последняя схема, левая дорожка). Если экспортировать в Gerber, то получается вот такие шаги:
1. подход к точке А, включение плоттера
2. проход к точке Б
3. возврат к точке А
4. проход к точке Б, выключение плоттера
5. конец программы

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

А делаю я, точнее хочу сделать, министанок для фрезеровки печатных плат

[Хакер]

получается вот такие шаги:
1. подход к точке А, включение плоттера
2. проход к точке Б
3. возврат к точке А
4. проход к точке Б, выключение плоттера
5. конец программы

Вот из этого гербера нужно сделать другой гербер или excellon-файл. Это будет в разы лучше и проще, чем векторизировать растр. Хотя бы потому, что после векторизации получится крайне много вершин (для всего круглого), и потом поиск кратчайших переходов займёт ещё много времени.

А делаю я, точнее хочу сделать, министанок для фрезеровки печатных плат

Выбор конечно за тобой, но как человек, который с 2009 года работает над проектом схожей тематики, скажу, что сам метод (фрезеровка дорожек) — отвратителен.
Лучше уж свой фотоплоттер сделать, хотя и это имеет не много смысла в себе: фотошаблон напечатают в любой полиграфии на прозрачной плёнки. Да что уж там, даже на струйнике самому можно напечатать.

[Хакер]

Вот я подумал.
Задача «сделать из плоттерного гербера фрезеровочный» — оно сложная, и сводится к тому, чтобы вычислить эквидистанту линии.
Но если ты пойдёшь своим путём, то тебе придётся сделать компенсацию размера фрезы. А для этого придётся сделать то же самое — вычислить эквидистанту линии.

Так что если ты последуешь моему совету, то тебе придётся просто вычислить эквидистанту, а если останешься при своём мнении — векторизировать растр, а потом всё равно вычислить эквидистанту.

[Proxy]

Да что уж там, даже на струйнике самому можно напечатать.

Современные лазерные по инструкции тоже допускают применение прозрачной плёнки с определёнными свойствами. Что получается из этого пока не проверял и применимо ли это как-либо тоже не могу сказать (низкое dpi).

[Sirik]

на счет компенсации ты прав, но так как фреза будет не что иное как очень тонкое сверло, то я пока что это отложу
завтра прикину что лучше, либо растровый рисунок анализировать, либо каким-то образом строить траектории из Gerber.

ps/ как же все-таки просто программировать роботы задал нулевой фрейм, точки, указал размеры инструмента и все

[Хакер]

Сверлом фрезеровать не получится. Обычные свёрла очень скоро затупятся (стеклотекстолит — абразивный материал) и могут сломаться. Твердосплавные свёрла — не затупятся, но сломаются сразу же, как только испытают изгибающую силу. Они как стекло хрупкие.

[Sirik]

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

[Хакер]

Рабочих проектов много, мой знакомый Денис Зайцев тоже сделал себе станочек общего назначения.

Так вот в рабочих проектах фрезерует не сверлом, а полноценной фрезой. Полноценная фреза фрезерует очень хорошо. Но полноценная фреза имеет такой размер, что наплевать на компенсацию её диаметра при вычислении траектории — нельзя.

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

[Sirik]

компенсация нужна в любом случае: откуда я буду знать, чем я буду фрезеровать через неделю или год

[Хакер]

Тогда о чём разговор?
Берёшь фотоплоттерную траекторию, вычисляешь эквидистанту, используешь как траекторию для фрезы. Задача решена.

[Sirik]

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