Как закрасить произвольную фигуру линиями?

Question

[andre_max]

Каким образом закрасить фигуру произвольной области непрерывной линией? Оптимальным считается алгоритм, в котором длина линии минимальна.
На вход программа получает массив координат границы (x,y) произвольной области и ширину линии. ДопустИм минимальный выход за границы области.

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

Comments

[nirvimel]

"Произвольная область" (это - не математический термин) задана чем? Ограничивающим ее многоугольником?

[abcd0x00]

Если ширина линии равна 100 точек, один из углов в контуре равен 10 градусов, а длина каждого из отрезков, образующих этот угол, равна 30 точкам, как будешь закрашивать?

[andre_max]

nirvimel: задана многоугольником, массивом координат (x,y) вершин этого многоугольника

[andre_max]

abcd0x00: с выходом за границы

Answer 1

[Альберт]

Алгоритм серьёзный, боюсь, бесплатно вам его никто не реализует. Я бы поступил как:

1. Провёл бы контур, аналогичный границе, но внутри неё на таком расстоянии, которое достаточно мало́, чтобы проведённый контур сливался с границей;
   
2. разбил бы только что проведённый контур на отдельные кольца (при наличии самопересечений);
   
3. для каждого кольца провёл бы внутри ещё один контур;
   
4. соединил бы проведённые внутренние контуры со внешними;
   
5. для каждого из оставшихся колец повторял бы алгоритм.
   

И ещё, алгоритм кратчайшего пути через все точки — это задача коммивояжёра, известная своей трудоёмкостью. Боюсь, оптимизировать тут что-либо будет достаточно тяжело, это больше задача для НИИ.

Comments

[andre_max]

разбил бы только что проведённый контур на отдельные кольца (при наличии самопересечений);
кольцо в данном случае - это окружность? Если не затруднит, можете поподробнее этот пункт объяснить?

[Альберт]

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