Возможное решение с итеративным процессом:
ПРЕДВАРИТЕЛЬНОЕ ЗАМЕЧАНИЕ: - Я помечаю имена переменных, которые буду использовать позже, символом ‹...>, а в квадратных скобках я отмечаю размерность переменной, если это массив. - В круглых скобках вы найдете проходы итераций с обычно "i" в качестве счетчика итераций.
ДАННЫЙ:
I1) массив [2,n] вершин двумерной фигуры с прямым краем: (1:i:2, 1:j:n), поэтому массив целых чисел размером 2 x n.
I2) максимальное количество используемых элементов сетки для покрытия фигуры: , поэтому скалярное значение
I3) 2D OCS (ортогональная система координат), рассматриваемая в качестве эталона для позиционирования вершин: по умолчанию все вершины предоставляют OCS своими собственными значениями. Назовите это ссылкой, но на самом деле это не переменная.
ВЫХОД:
O1) обеспечил длину стороны квадратной сетки, в лучшем случае покрывающую заданную форму: , поэтому скаляр.
O2) количество сгенерированных строк: , другой скаляр
O3) массив значений X каждой строки (строки) квадратов, представляющий левый нижний угол первого квадратного элемента сетки: с 1:i:R, где R — упомянутый выше результат, поэтому количество сгенерированных строк по алгоритму.
O4) массив целых чисел, содержащий количество элементов сетки в строке: с 1:i:R
ВСПОМОГАТЕЛЬНЫЕ ФУНКЦИИ:
//рассчитываем коэффициент покрытия
ACF: (средний коэффициент покрытия), вычисление отношения между площадью всей исходной формы и суммой всего массива сгенерированных квадратов (данный список нижних левых углов квадратов добавляет длину стороны).
SCF: (коэффициент покрытия одним элементом): вычисление процента каждой отдельной квадратной области, которая покрыта (перекрывается) фигурой. это сложно, но его можно вычислить с небольшими усилиями путем триангуляции в стиле сетки конечных элементов (вы можете найти методы создания сетки треугольных элементов в Интернете).
АЛГО:
1) Определите минимальную ограничивающую рамку (первый квадрат, содержащий всю фигуру)
1.1) определяют самую нижнюю точку формы Y в исходной OCS: скаляр, представляющий вертикальное смещение между OCS0 и OCS1.
1.2) определить самую левую точку формы (одну из вершин) в исходной OCS:
1.3) Сдвиг формы с жестким линейным преобразованием T:T(x,y) -> (x-dx, y-dy); теперь ограничительная рамка имеет левый нижний угол в начале новой системы координат (это то, что отображает OCS0 в OCS1)
1.4) сдвинуть всю фигуру в ОСК1;
1.6) рассчитать средний коэффициент покрытия на шаге 0;
ПРИМЕЧАНИЕ: это уже решение, не лучшее, но математически приемлемое решение.
1.7) проверяем, сколько элементов (на данном этапе только один) полностью входят в фигуру, называют ее (на этом первом шаге это ноль), сколько полностью исключено границами фигуры (на этом первом шаге это ноль), и сколько частично перекрываются (на этом первом шаге это 1). Обратите внимание, что во время итераций сумма длин этих трех массивов должна быть равна количеству квадратов, сгенерированных в результате уточнения ограничивающего квадрата.
1.8) удалить из сетки все квадраты, принадлежащие NFULLOUT(0). На нулевом шаге эта процедура не дает никакого результата, так как в массивах решений есть только один частично покрывающий элемент.
2) Цикл по уточнению
2.1) рассчитать коэффициент уточнения по RF = M/(сумма QTY(1:R))
ПРИМЕЧАНИЕ: в пункте 2.1 учитываются все элементы полного покрытия с весом 1 в вычислении площади, а также частичные элементы, более точным способом будет использование функции SCF для каждого отдельного квадрата частичного покрытия для расчета эффективного веса элемента, который будет использоваться для расчет площади сетки.
2.2) рассчитать новую длину стороны квадрата по формуле L(1) = L(0)/RF;
2.3) ЕСЛИ (количество квадратов меньше допустимого количества квадратов), уточнить сетку, перегенерировав матрицу квадратов с новой стороной.
2.3.1) проверить, сколько элементов (на данном этапе только один) полностью входят в форму (на этом первом шаге это ноль), сколько полностью исключено границами формы (на этом первом шаге это ноль ), и сколько частично перекрываются (на этом первом шаге это 1), где «i» представляет шаг итерации для уточнения.
2.3.2) удалить из сетки все квадраты, принадлежащие NFULLOUT(i). На нулевом шаге эта процедура не дает никакого результата, так как в массивах решений есть только один частичный элемент.
2.3.4) рассчитать коэффициент уточнения по RF = M /(сумма QTY(1:R))
2.3.5) рассчитать новую длину стороны квадрата по формуле L(1) = L(0)/RF;
2.3.6), если L(i) > 0, то повторите цикл с 2), иначе сломается.
3) после перерыва разделяй и властвуй на улучшение
3.1) для каждого отдельного ряда сетки попробуйте сдвинуть весь ряд примерно на половину длины стороны вправо и влево, посчитайте эффективность и решите, что лучше. затем вы сдвигаете эту линию на количество, проверенное и проверенное как лучшее, продолжайте снова, выбирая влево и вправо с длиной стороны 1/4 и так далее, пока вы не получите более низкую эффективность, чем на предыдущем шаге.
ПРИМЕЧАНИЕ: этот последний раздел «разделяй и властвуй» применяется только в том случае, если вы взвешиваете каждый отдельный частичный элемент весом от 0 до 1. Если вы считаете частичные покрывающие элементы полностью покрывающими элементами, это не дает вам никаких улучшений.
ПОСЛЕДНЕЕ ПРИМЕЧАНИЕ: учтите, что вы можете применить коэффициент масштабирования к RF, например, при первом проходе коэффициент масштабирования даст вам RF = M, что, возможно, немедленно выведет вас из ограничений. Всякий раз, когда вы получаете RF> 2, вы можете применить коэффициент 0,8 к RF, если ваше обычное количество элементов находится в диапазоне 100-1000 элементов или даже больше.
ПОСЛЕДНЕЕ ПРИМЕЧАНИЕ 2: если бы вы могли убрать ограничение, согласно которому все квадраты должны иметь одинаковую длину, это стало бы намного проще и, прежде всего, намного быстрее, поскольку вы уточняете только приближение к границам.
Извините, если это не совсем формула, но я думаю, что это один из самых быстрых элементов, который позволяет вам избежать сложных алгоритмов создания сетки, которые вы могли бы взять из вычислительного анализа. Я также извиняюсь за необычное обозначение. Я изо всех сил старался объясниться, я не привык к стандартным обозначениям.
person
Pinoba
schedule
16.07.2012
