[swkx]

Контур - замкнутая 2D-полилиния неправильной формы.
Условия размещения: макс. и мин. расстояния между точками и макс. и мин. расстояния от точек до границ контура.
Подскажите алгоритм.

[Supermax]

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

[swkx]

Мне это тоже пришло в голову))
Вернее, не именно это, но тоже использовать взорванную штриховку.

Хочу другие варианты!

[T-Yoke]

Сообщение от swkx Контур - замкнутая 2D-полилиния неправильной формы. Условия размещения: макс. и мин. расстояния между точками и макс. и мин. расстояния от точек до границ контура. Подскажите алгоритм.

Если Контур - замкнутая 2D-полилиния, то возможен вариант использовать эквидистант с типом линии "точки"
Варьируете отсупом между линиями и расстоянием между точками, думаю должно получиться.

[swkx]

Тоже вариант. Затем полученный меньший контур считать исходным и т.д.
Но, может, есть что попроще...

[Елпанов Евгений]

интересная задачка
я бы решал так:
Алгоритм 1
1. делаем аппроксимацию контура с небольшим шагом (достаточно в два раза меньше расстояния между точками)
2. округляем вершины и удаляем повторы
3. сортируем полученные вершины, чтоб получить подсписки с одинаковой Х
на этом этапе имеем точки примерного пересечения вертикальных линий с контуром, находящиеся на расстоянии шага искомых точек.
4. начинаем заполнять внутренние диапазоны в списках недостающими данными, например подсписок: '(0 18 20 50 55) где первый элемент это координата по Х, тогда получим:
'((0 19)(0 51)(0 52)(0 53)(0 54))
аналогично обработать все подсписки...

Алгоритм 2
Если не хочется много вычислять математически, можно все сделать объектно: создаем две штриховки - горизонтальную и вертикальную с шагом равным шагу искомых точек и ищем все пересечения объектов штриховок.

[swkx]

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

[Елпанов Евгений]

Сообщение от swkx но потом неизбежно вылезет задача удаления "лишних" точек, особенно в узких каналах.

находим ближайшую точку на контуре, потом расстояние и принимаем решение удалять или нет...
Если пересортировать все точки, как в предыдущем алгоритме, то можно проверять только первые и последние точки в столбцах...

[swkx]

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

[Елпанов Евгений]

почему единственный? Второй алгоритм у меня реализован в двух коммерческих проектах и работает уже восемь лет очень стабильно! Первый был опробован, но отброшен как довольно медленный - разговор о тысячах контуров...

[swkx]

Евгений,
я имел в виду не единственный из существующих в природе, а из рассматриваемых мной))
А о каком 2-м вы говорите ?

[Елпанов Евгений]

Сообщение от swkx Евгений, я имел в виду не единственный из существующих в природе, а из рассматриваемых мной)) А о каком 2-м вы говорите ?

в 6 посте, я описал один алгоритм использующий чистую математику, без построений и второй с построениями - используются дополнительные штриховки

[swkx]

Так я его и рассматриваю пока как главного кандидата на реализацию
Кандидат #2: разбить контур на прямоугольники.

[zamtmn]

Если все контура подобны #7 надо придумывать как разбивать на прямоугольники. ИМХО.

[swkx]

Нахожусь в процессе придумывания.
Результат нулевой

[Supermax]

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

Берем первую в наборе и по заданному радиусу удаляем из набора все точки попавшие в круг.
Берем следующую, первую попавшуюся и вытираем по радиусу вокруг нее. И так далее, пока не дойдем до конца набора.

В теории, когда круг замкнется, останется некое расстояние больше радиуса, но меньше двух радиусов, что соответствует заданным условиям.
Ни о какой упорядоченности внутри контура речи не шло, значит получим равномерное хаотичное поле. Правда если точки были распределены по клеточкам, то и результат вроде должон получится ровненький. Надо смотреть.

[Хмурый]

рассмотрите, в качестве примера, _superhatch из комплекта Express Tools

[zamtmn]

swkx
Контура всегда состоят из стыкованых прямоугольников?

[swkx]

zamtmn,

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

Supermax,

я помню твоё предложение. Но пока нужно определиться, работать с различными вариантами (в т.ч. с твоим) со штриховкой или попытаться разбить контур на прямоугольники.
У штриховок большой плюс - годится для любых контуров, у 2-го способа - идеальное размещение.

Хмурый,

у меня нет Express Tools. Нужно обойтись стандартным набором инструментов.

[zamtmn]

Для начала можно попробовать для начала вырезать малые приямоугольники:
перебираем вершины по 4 рядом стоящие
если они образуют прямоугольник с серидиной диагонали лежащей внутри контура - запоминаем прямоугольник и выкидываем 2, 3 вершины из набора, оптимизируем набор (одаляем вершины лежащие на 1 прямой)

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

так пока в итоге не останется прямоугольник, или ниче не возможно отрезать.

edit:
проверки нахождения середины диагонали предпологаемого прямоугольника внутри контура не достаточно. нужно еще проверять чтоб внутрь прямоугольника не попадали другие точки из контура

[KAI]

swkx #1 Контур - замкнутая 2D-полилиния неправильной формы. 1. Условия размещения: макс. и мин. расстояния между точками. 2. И макс. мин. расстояния от точек до границ контура. Подскажите алгоритм.

В отличии от уважаемого Е.Елпанова я в своей программе MINS_HATCH решал эти задачи по "рабоче-крестьянски":

1.
а. Вычисляем мин. и макс. координаты точек контура.
б. Определяем начальные координаты массива (в зависимости от расстояния между точками), так чтобы координаты массива были заведомо больше контура (на расстояние между точками). А также количество строк и столбцов массива.
в. По команде -Array заполняем массив (предварительно отрисовав точку в нижнем левом углу массива). Следует не забывать об ограничении количества блоков массива.
г. По ssget находим эти блоки внутри контура и удаляем из набора блоки, созданные командой Array за пределами этого контура.

2. А вот в этом случае задача значительно усложняется:
а, б, в - можно оставить те же.
г. Делаем offset (отступ) контура внутрь, находим перечень его точек (правда тут надо не забывать, что команда Offset может создать несколько контуров отступа). Желательно проверять предварительно также самопересечение исходного контура и сдвоенность его точек.
д. И далее по пункту г. режима 1. (но уже по контуру отступа).

[zamtmn]

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

[swkx]

Да, похоже на правду.

[zamtmn]

>>Да, похоже на правду.
В смысле? какой мне резон врать))
Исходники не прилагаю т.к. сделано просто для проверки алгоритма а не для реального использования, мне данная тема тоже интереснна. и исходники не для автокада

[swkx]

zamtmn,

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