[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:
проверки нахождения середины диагонали предпологаемого прямоугольника внутри контура не достаточно. нужно еще проверять чтоб внутрь прямоугольника не попадали другие точки из контура