HPGL ??

From

Alexander V. Lushnikov (2:5005/42.19)

To

Alex Astafiev

Date

2002-05-16T08:06:58Z

Area

RU.ALGORITHMS

          Привет тебе, Alex!

          Дело было 15 мая 02,
 Alex Astafiev и Ilja обсуждали тему "HPGL ??".

AA> 1. По изображению построить контур A.
AA> 2. Из данного конутра A построить контур B.
AA> Условия построения таково - контур B должен охватывать контур A.
AA> Дополнительное условие - каждая бесконечно малая точка контура B 
AA> находится на расстоянии равном R от эквивалентной ей точки контура A. То 
AA> есть линии контура B находятся на растоянии  R от линий контура A.
С большой вероятностью, у человека задача типа изготовления печатных плат или печатей фрезеровкой. 
Т.е. рисунок может быть векторный, каждый элемент изображения составлен из некоторого набора сопрягающихся элементов типа отрезок, дуга, полигон, круг и т.д. с заданной толщиной линии, или может быть монохромным битмапом, или вообще их сочетанием, но в любом случае все это надо приводить к векторному варианту.

AA> Решение:
AA> Находится такой контур простым линейным увеличением, масштабированием 
AA> исходного контура на расстояние R.
_масштабированием_ не получится. Попробуй линейно смасштабировать прямоугольник, скажем, 1мм х 1000мм, и прикинь изменение по одной и по другой оси - они разные. К тому же, что контур там может быть весьма замысловатый, с дырами внутри.

Вообще говоря, задача сводится действительно к обводке произвольного объекта контуром В на расстоянии R от границы этого объекта (контур А). 
А она в свою очередь бьется на а) построение границы каждого элемента объекта А', б) обводку (оконтуривание) каждого элемента объекта (построение контура B' вокруг контура-границы каждого элемента A'), в) объединения этих контуров B' и г) удаления "внутренних" линий. Причем подзадачи а) и б) делаются за один проход, а подзадача г) делается попутно с подзадачей в).
Подзадача а)+б) достаточно тривиальна, хотя и весьма объемна - отрезок с координатами (x1,y1)(x2,y2), толщиной линии d, и зазором R заменяется на четыре отрезка (нулевой толщины) с соответствующими координатами (или, что лучше, на пару отрезков и пару дуг радиуса d вокруг концов), окружность - на пару окружностей, дуга - на пару дуг и пару отрезков (или опять же дуг вокруг концов), круг - на окружность, и т.д.
Не менее объемна подзадача в)+г) - надо искать точки пересечения дуг/отрезков/окружностей, и выкидывать куски линий, попадающих внутрь получающегося контура.
Последняя задача - сортировка полученных кусков контура так, чтобы начало каждой следующей линии было концом предыдущей, чтобы получилась непрерывная линия прорезки.

AA> Твоя специфика:
AA> Когда ты найдешь такой контур, тебе останется обойти его центром фрезы.
еще одна специфика - оптимизация движения, и как ее часть - исключение участков двух налагающихся контуров. Скажем, при ширине прорезки 1мм и расстоянии между соседними прямоугольниками тоже 1мм достаточно одного прохода между ними вместо полного оконтуривания каждого персонально. Вторая часть оптимизации - уменьшение "холостого" движения инструмента от одной линии прорезки до другой. Обе части зависят от требований к точности формы элементов изображения и еще от ряда ограничений. 
Например, в случае изготовления печатной платы часто вполне допустимо некую сложную конфигурацию вырезаемых дорожек заменить описывающим полигоном с минимальным числом вершин, а разделение этих полигонов с соседними сделать одной прорезанной линией вместо вырезания двух отдельных контуров. При этом сложность (и время) прорезки может уменьшиться на порядки.

2Илья: В общем, подробное описание задачи в студию.


Удачи! 
Александр Лушников.

--- FIPS v.1.10.02 on DarkBeard Station
 * Origin: Invalid SysOp! Replace and press any key... (2:5005/42.19)