Задача : определить периметр
Всем привет,
задача :
программа получает координаты прямоугольников, стороны прямоугольников параллельны с осами x и y. Некоторые прямоугольники могут перекрыватся, а задача заключается в том, чтобы найти периметр созданный этими прямоугольниками, внизу на изображении видно, как они могут быть примерно, и что необходимо найти, т.е. то что я должен найти означено красным цветом :
изображение 1 :
http://i006.radikal.ru/1012/7c/7e2fc47a3166.jpg
изображение 2 :
http://s42.radikal.ru/i096/1012/95/eb7e529dcd1e.jpg
Есть ли какой нибудь алгоритм решения этой задачи, я не прошу готовое решение, просто если кто нибудь решал подобную задачу скажите в каком направлении копать.
задача :
программа получает координаты прямоугольников, стороны прямоугольников параллельны с осами x и y. Некоторые прямоугольники могут перекрыватся, а задача заключается в том, чтобы найти периметр созданный этими прямоугольниками, внизу на изображении видно, как они могут быть примерно, и что необходимо найти, т.е. то что я должен найти означено красным цветом :
изображение 1 :
http://i006.radikal.ru/1012/7c/7e2fc47a3166.jpg
изображение 2 :
http://s42.radikal.ru/i096/1012/95/eb7e529dcd1e.jpg
Есть ли какой нибудь алгоритм решения этой задачи, я не прошу готовое решение, просто если кто нибудь решал подобную задачу скажите в каком направлении копать.
P=(max(x)-min(x))*2+(max(y)-min(y))*2
как то так..., с нахождением минимумов и максимумов проблем не должно возникнуть, ну и язык реализации выбери сам
как то так..., с нахождением минимумов и максимумов проблем не должно возникнуть, ну и язык реализации выбери сам
Цитата: ArtemP
P=(max(x)-min(x))*2+(max(y)-min(y))*2
как то так..., с нахождением минимумов и максимумов проблем не должно возникнуть, ну и язык реализации выбери сам
как то так..., с нахождением минимумов и максимумов проблем не должно возникнуть, ну и язык реализации выбери сам
Можно поподробнее про алгоритм, или под каким "псевдонимом" найти в гугл ?
Пардон, привел вариант решения для частного случая, когда все прямоугольники образуют единое целое ( как на картинке). Периметр прямоугольника, образованного кассательными к твоей фигуре равен периметру этой фигуры. Линейка, карандаш и лист бумаги помогут тебе в решении лучше гугла.
касательные к фигуре также паралельны осям
задача только для 3-х прямоугольников?
Цитата: freets
задача только для 3-х прямоугольников?
Нет, прямоугольников неопределенное количество.
Вариант номер 1: "Высокоуровнево" решение задачи можно описать следующим образом: любой (первый) прямоугольник принимаем взять за базовую фигуру, каждый следющий прямоугольник прибавлять к фигуре. Полученную в результате фигуру проверить на связность и посчитать периметр. В таком виде задача может быть решена с помощью API для регионов (в Win32 и .NET он есть).
Вариант номер 2: Используем алгоритм построения выпуклой оболочки над множеством точек, образующих вершины прямоугольников, с некоторой модификацией: диагональные ребра нужно трактовать как гипотенузы и использовать вместо них "вогнутые" катеты.
Вариант номер 2: Используем алгоритм построения выпуклой оболочки над множеством точек, образующих вершины прямоугольников, с некоторой модификацией: диагональные ребра нужно трактовать как гипотенузы и использовать вместо них "вогнутые" катеты.
Цитата: hardcase
Вариант номер 1: "Высокоуровнево" решение задачи можно описать следующим образом: любой (первый) прямоугольник принимаем взять за базовую фигуру, каждый следющий прямоугольник прибавлять к фигуре. Полученную в результате фигуру проверить на связность и посчитать периметр. В таком виде задача может быть решена с помощью API для регионов (в Win32 и .NET он есть).
Вариант номер 2: Используем алгоритм построения выпуклой оболочки над множеством точек, образующих вершины прямоугольников, с некоторой модификацией: диагональные ребра нужно трактовать как гипотенузы и использовать вместо них "вогнутые" катеты.
Вариант номер 2: Используем алгоритм построения выпуклой оболочки над множеством точек, образующих вершины прямоугольников, с некоторой модификацией: диагональные ребра нужно трактовать как гипотенузы и использовать вместо них "вогнутые" катеты.
О первом варианте в моем случаи не может быть речи, ничего кроме ANSI C использовать для реализации задачи нельзя.
За второй варинт спасибо.