#arrays #c
#массивы #c
Вопрос:
Как мы находим пересечение внутренних частей n квадратов, стороны которых параллельны осям x и y, учитывая их центры и длины сторон?
Входные данные-это количество квадратов, за которыми следует такое количество описаний квадратов. Описание каждого квадрата-это координаты x и y его центра и длина его стороны. Например:
35 11 10 7 9 10 10 6 8
описывает три квадрата, начиная с одного с центром в (5, 11) с длиной стороны 10.
Комментарии:
1. Поиск пересечения 2 квадратов.
2. Начните с нахождения пересечения первых двух. Это будет прямоугольник. Затем найдите пересечение предыдущего пересечения и следующего квадрата.
3. @klutt: Технически это означало бы пересечение внутренних частей квадратов (областей внутри всех квадратов), а не пересечений квадратов (точек, общих для линий, составляющих квадраты). Возможно, это то, чего хочет ОП, и в этом случае следует уточнить вопрос и название. (Подумайте об этом так: если кто-то попросит вас нарисовать квадрат на бумаге, вы нарисуете заполненный черный прямоугольник или только четыре линии?)
4. @EricPostpischil Ах, это правда
Ответ №1:
Алгоритм для нахождения пересечения внутренних поверхностей квадратов (со сторонами, параллельными осям x и y), заданных их центрами и длинами, является:
- Конвертировать центр (Точка (х, г)) и длина (л) в первом квадрате х — координаты левого края (х−л/2) и правый край (х л/2) и г — координаты нижнего края (г−л/2), и верхним краем (г л/2). Держите их слева, справа, снизу и сверху.
- Для каждого следующего квадрата:
- Преобразуйте его центр и длину в координаты, как указано выше.
- Выясните, какая координата x больше, старая левая или новая левая кромка, и сохраните ее как новую левую.
- Выясните, какая координата x меньше, старая правая или новая правая кромка, и сохраните ее как новую правую.
- Определите, какая координата y больше, старое дно или новый нижний край, и сохраните ее как новое дно.
- Определите, какая координата y меньше, старая вершина или новый верхний край, и сохраните ее как новую вершину.
После обработки всех квадратов слева, справа, снизу и сверху отображаются координаты прямоугольника, ограничивающего область, которая находится внутри всех квадратов. (Если справа lt; слева или сверху lt; снизу, пересечение пустое. В противном случае, если справа = слева или сверху = снизу, пересечение представляет собой линию [если верно только одно] или точку [если верно и то, и другое].)
Ответ №2:
Вот простая функция для вычисления пересечения двух прямоугольников. Квадрат-это прямоугольник, поэтому его можно использовать для квадратов. Я предполагаю, что высота и ширина прямоугольников параллельны осям y и x.
struct point { double x, y; };struct rectangle { struct point a, b; };double max(double a, double b) { return agt;b ? a : b; }double min(double a, double b) { return alt;b ? a : b; }// Calculate the intersection of r1 and r2 and store the result in output// Assumes that a.x lt; b.x and a.y lt; b.y for r1 and r2// Returns NULL if there is no intersection // Will always modify output. Do do NOT read output if this function returns NULLstruct rectangle *intersection( struct rectangle *output, const struct rectangle *r1, const struct rectangle *r2) { output-gt;a.x = max(r1-gt;a.x, r2-gt;a.x); output-gt;b.x = min(r1-gt;b.x, r2-gt;b.x); if(output-gt;a.x gt; output-gt;b.x) return NULL; output-gt;a.y = max(r1-gt;a.y, r2-gt;a.y); output-gt;b.y = min(r1-gt;b.y, r2-gt;b.y); if(output-gt;a.y gt; output-gt;b.y) return NULL; return output;}