Создание набора прямоугольников для формирования сетки в неправильном многоугольнике с помощью надстройки

Question

Создание набора прямоугольников для формирования сетки в неправильном многоугольнике с помощью надстройки

Мне нужно создать набор прямоугольников заданного размера, которые образуют сетку внутри неправильного (вероятно, не выпуклого) многоугольника. (Я понимаю, что на краях будут биты, которые не будут помещаться в прямоугольнике. Их можно просто отбросить.) Все в двух измерениях, и мой тип точек — двойной. Я работаю с данными UTM, так что мои полигоны не находятся близко к источнику. Я должен работать с C ++. У меня есть два вопроса:

Можно ли это сделать с помощью Boost? Я посмотрел на конструктор диаграмм Вороного, но у меня возникли проблемы с созданием прямоугольной решетки точек внутри моего многоугольника.

Есть ли другая библиотека геометрии, которую я могу использовать, которая лучше подходит для генерации набора прямоугольников внутри многоугольника?

1

boost boost-polygon c++geometry

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я написал свою собственную функцию, которая делает это. Это может быть не красиво, но это работает. Сначала я определил самые высокие и самые низкие значения x и y. Затем я передаю их этой функции и определяю границы моих ячеек на основе постоянных значений.

using namespace std;

typedef boost::geometry::model::d2::point_xy<double> point_xy;
typedef boost::geometry::model::polygon<point_xy> polygon_type;

vector<polygon_type> createNScells(double nex, double ney, double swx, double swy) {
vector<polygon_type> cells;

double x1 = swx;
double x2 = swx;

point_xy first;
point_xy second;
point_xy third;
point_xy fourth;

while (x2 > nex) {//move x's
x2 -= const1;
double y1 = ney;
double y2 = ney;
while (y2 > swy) {//move y's
y2 -= const2;
//assign x's and y's to points
first.x(x1);
first.y(y1);
second.x(x2);
second.y(y2);
third.x(x1);
third.y(y2);
fourth.x(x2);
fourth.y(y1);
polygon_type r;
//assign points to polygon
boost::geometry::append(r, first);
boost::geometry::append(r, third);
boost::geometry::append(r, second);
boost::geometry::append(r, fourth);
boost::geometry::append(r, first);
cells.push_back(r);

y1 = y2;
}
x1 = x2;
}
return cells;
}

const1 и const2 определяют размер моих клеток. Наконец, я написал функцию удаления ячеек за пределами моего многоугольника.

for (int i = 0; i < cells.size(); ++i) {
if (!boost::geometry::within(cells.at(i), polygons)) {
swap(cells.at(i), cells.back());
cells.pop_back();
}
}

Это, конечно, не самое удачное решение, но я бы приветствовал способы повысить эффективность моего кода.

0