Заполнение пространства между случайными 2D линиями

23

Рассмотрим область (2D), заполненную линиями случайным образом (см. Рисунок). Мы заинтересованы в заполнении пустых пространств между строками, включая четыре граничных ребра:

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

Итак, на данный момент есть три разных сценария.
Обратите внимание, что линии имеют форму [x1,y1,x2,y2]точки набора, реальные цифры.

[* * *] Идеи возможных решений / алгоритмов / фрагментов кода / и т. Д. Приветствуются.

введите описание изображения здесь


Обновление 1: мы можем управлять решением для первого случая:
введите описание изображения здесь
Шаги:
1 - строки
2 - растеризация строк в растровое изображение
3 - поиск соседних ячеек для каждой ячейки желаемого цвета (то есть того же цвета) с целевой функцией для максимизации площадь, т. е. количество клеток.

Это работает хорошо, но охватывает только первый сценарий и также медленно.


Обновление 2:
мы предположили, что читатель знаком с концепцией заполнения-заполнения-пространства. Вы можете перейти по ссылке для вдохновения. Однако учтите, что наша проблема в другом. Поскольку мы не заполняем пустое пространство случайным образом и не выбираем размер случайно. Решение должно быть итеративным. Во всех случаях не существует ограничений на количество отправляемых посылок. Действительно, пользователь может ограничить число итераций, выбрав, например, минимальную площадь для посылок. Это очевидно в приведенном выше примере, в котором мы разделили строки на пиксели с указанным размером. То есть процедура должна выполняться до тех пор, пока не будет заполнена вся пустая область в соответствии с критерием, например, максимальной площадью участков.


Обновление 3:
резюме:
Одно из приложений - выяснить распределение извлекаемых неповрежденных «каменных» блоков в сильно разломанной «шахте». Это может быть очень полезным для многих аспектов , включая буровую конструкцию, финансовую оценку и т.д.
Описание:
Для мины декоративной породы (камень) продукты , которые являются блоками неповрежденных пород , вырезанных в виде прямоугольных кубов цены сильно зависят от размера блок. Извлечение блока из подходящей области, то есть без значительного разрушения, будет желательно, если количество оставшихся частей будет как можно меньше. Обычно небольшие куски камней не имеют относительно экономической ценности и рассматриваются как отходы.
Вопрос в этом посте исследует решения для такого рода проблем.

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


Поскольку это является частью продолжающегося исследования, некоторые из вопросов, заданных в комментариях ниже, не имеют определенных ответов, которые мы можем предоставить. Мы считаем, что предоставленной информации здесь действительно достаточно, чтобы получить общую картину проблемы. Тем не менее, мы предоставляем некоторые подробности, как мы можем для общественных выгод.
Вы можете наложить некоторые ограничения на решение окончательного вопроса, хотя, мы считаем, что всегда можно добавить больше позже. Например, выполните следующие действия: {2D case}
Наилучший размер блока (экономически оптимальный прямоугольник), который должен быть извлечен в условиях, указанных выше, 1x1 mприведен 10x10 mдля региона в примере. Это одно ограничение, определенное на основе экономической ценности. Минимальный рабочий размер для резки и т. Д., Пусть будет0.15x0.15 m; так что это второй предел размера.
введите описание изображения здесь
На рисунке выше показана функция экономической стоимости в зависимости от размера блока. Так что для этого конкретного случая каждый кусок камня меньше, чем 0.15x0.15 mпросто отходы. Там не будет размер блока больше, чем 1.7x1.7 mиз-за пределов работы.

разработчик
источник
3
@RK - я не согласен. Он / она уже очень четко изложил то, что они ищут. Конечно, есть несколько возможных решений, но ничто не мешает им быть полезными и за них проголосовали.
ГИС-Джонатан
1
Поскольку это вопрос алгоритмического характера, который может быть довольно сложным по
GIS-Jonathan
1
Тесно связанный: gis.stackexchange.com/questions/27303 . Настоящий вопрос, как отмечает @RK, не имеет однозначного ответа, потому что он не достаточно корректен. Сколько прямоугольников разрешено? Что значит «максимизировать размер»? Также обратите внимание, что это не проблема «случайного разбиения на листы»: линии просто определяют, посредством своего дополнения, области, которые могут быть заняты; решения определенно не будут случайными. Также обратите внимание, что сразу доступно простое упрощение: проблема может быть решена отдельно в рамках каждого компонента дополнения.
whuber
1
@whuber: Ну, одно из приложений, которое нас интересует, - это выяснение распределения извлекаемых неповрежденных «каменных» блоков в сильно разломанной «шахте». Ну, ГИС кажется многообещающей для этой проблемы, мы думаем. Мы добавили это и к вопросу. Мы предполагаем, что ГИС-сообщество может извлечь выгоду из этой идеи для других связанных с ним проблем. Во всяком случае, это зависит от вас, если вы перенесете его;)
Разработчик
4
Как подсказывает @whuber, на самом деле это не вопрос ГИС (хотя я не обижаюсь на то, что его здесь задают). Вам будет гораздо лучше получить ответ на форуме по вычислительной геометрии или оптимизации.
Llaves

Ответы:

2

У меня есть идея, как вы итеративно работаете от больших блоков до более мелких блоков, используя FME (от Safe Software.) Для справки, я не работаю на них, но, кажется, хвалят их инструмент достаточно ...

  1. Используйте «BoundingBoxReplacer» на интересующей области.
  2. Перепроектируйте его в локальную систему координат (для дальнейшего, когда вам нужно «разбить» на футы / метры.)
  3. Буферные линии с трансформатором "Bufferer". Вам нужен только произвольный размер, скажем, 0,01 фута / метр. Здесь мы ищем многоугольник линии для следующего шага.
  4. Добавить "Tiler" Трансформер. Укажите большой (примерный или другой) размер плитки в футах или метрах. То, что мы делаем здесь, это разбиение интересующей области на квадратные блоки. В зависимости от набора данных начните с большого, чтобы действительно получить большие выбросы.
  5. Добавьте трансформатор "Clipper". То, что мы здесь делаем, - это нарезка набора данных, чтобы увидеть, какие плитки хороши / плохи. На выходе плитки, которые "Внутри", слишком велики. Тем не менее, плитки "Снаружи" достаточно велики и готовы для резки ...
  6. Вот где это получается сложно, но не сложно ... Мы собираемся зациклить трансформатор, чтобы мы снова использовали оригинальный BoundingBox, но вырезали области, которые уже готовы для резки. Таким образом, добавьте клипер и направьте клипер в качестве тайлов «Выходных данных» на более раннем выходе клиппера. Теперь у нас есть один полигон, который снова готов к работе.
  7. Используйте тайлер снова, на этот раз указав меньшую плитку. Например, если раньше вы использовали 100-метровую плитку, попробуйте 90 метров.
  8. Добавьте другой клипер, с входным клипером, являющимся буферизованными строками, и входным клипом, являющимся меньшими тайлами в качестве ввода.

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

Исходя из вашего (очень подробного) описания, он пока будет работать только с вашим вариантом 1. Пока не уделяю слишком много времени.

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

Пример плитки FME

Мэтью Брукер
источник