|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
08.01.2015, 16:42 | #1 |
Подтвердите свой е-майл
Регистрация: 14.12.2014
Сообщений: 3
|
Найти контур фигуры
Здравствуйте, вот задачка: Задано n прямоугольников на плоскости. Найти контур их объединения - минимальный многоугольник, охватывающий все заданные прямоугольники. Задача для паскаля в модуле Graph. Помогите пожалуйста.
|
08.01.2015, 17:03 | #2 |
Участник клуба
Регистрация: 03.06.2009
Сообщений: 1,834
|
попытался нарисовать на листе 5 прямоугольников: в столбик, а линию, в кучу... и понял, что математически там придётся повозиться, а ещё в паскаль перекладывать.
а если ещё и 5< N взять прямоугольников.... до какого числа тебе эту экзаменационную задачку надо сдать? если нет наработок своих, то хоть за денюжку - во Фриланс иди
Программирование - это единственный способ заставить компьютер делать то, что тебе хочется, а не то, что приходится.
|
09.01.2015, 00:20 | #3 |
Участник клуба
Регистрация: 14.06.2011
Сообщений: 1,138
|
1. берется первый много угольник.
2. перебираются все точки прочих n-угольников. 3. 1. если точка внутри - берем следующую точку 3. 2. иначе расширяем "охватыватель" 3. 2. 1. добавляем точку в контур "охватывателя" 3. 2. 2. проверяем "охватыватель" на выпуклость, при необходимости - удаляем ненужные точки. Как правильно определить, в какое место в упорядоченном наборе точек "охватывателя" надо вставить новую точку, чтоб не получалась "самопересекающаяся звезда".... Ну, предположим, что центр будет в центре прямоугольника, в который вписывается "охватыватель", все равно координаты истинного центра масс надо знать лишь примерно, ведь подойдет любая точка, лишь бы однозначно лежала внутри фигуры. То есть, надо предусмотреть что допущение про центр фигуры не верно, и проверять, а действительно ли точка внутри? Или теоретически удостовериться, что центр любого описанного четырехугольника ВСЕГДА лежит внутри вписанного многоугольника. Теперь от этой внутрилежащей точки строим отрезок до рассматриваемой добавляемой вершины и проверяем, с какой гранью он пересекся. Вот между точками этой грани новую вершину и вставляем. А уже после проверяемся на выпуклость. А хотя, проще по другому: ведь у нас известен знак обхода проверки на "внутрилежащность", достаточно просто найти грань, относительно которой знак проверки будет равен "знаку внележащности". Последний раз редактировалось Smogg; 09.01.2015 в 00:25. |
09.01.2015, 01:42 | #4 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
Безымянный.bmp
Решаем в лоб 1. Ищем самые верхние точки 2. Выбираем из них самую левую (идти будем по часовой стрелке) - это наша отправная точка T[1]. 3. Angle := 0; // Не помню как там у нормальных людей. // В данном посте отсчитываю угол по часовой стрелке. // За ноль взял 3 часа // Но сути это не меняет 4. Count := 1; 5. Выбираем из них самую правую - Tтекущая. . 6. Inc (Count); T[Count] := Tтекущая; . 7. Ищем точки угол поворота до которых больше Angle, но минимален (Их может быть несколько). Это и есть новый Angle . 8. Выбираем самую дальнюю - это новая Tтекущая. 9. Если Tтекущая <> T[1] возврат на п.6 Комментарии 1. Можно оптимизировать задачу заранее отсортировав точки и по X и по Y. Зная направление движения можно не обрабатывать заведомо ненужные точки. 2. В задании написано: "Задано n прямоугольников". Видимо это подсказка на способ отсечения ненужных обработок. За один ход при любом раскладе мы не сможем повернуть более чем на 90 градусов. А точнее: мы обязательно посетим 0, 90, 180 и 270. Например: Если мы шли СТРОГО ВВЕРХ, то на следующем шаге нас интересуют только точки не ниже (не сможем переволить через ортогонали не отметившись) и не левее (мы же по часовой стрелке идем). 3. Еще. Если мы движемся вниз - нас интересуют только правые грани. Если влево - только нижние. Ну и так далее. Последний раз редактировалось Sibedir; 09.01.2015 в 01:55. |
09.01.2015, 08:47 | #5 |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Вот тут и обход по контуру и формирование регионов из изображений произвольной конфигурации:
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder |
09.01.2015, 13:04 | #6 |
Подтвердите свой е-майл
Регистрация: 14.12.2014
Сообщений: 3
|
большое спасибо
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Найти площадь фигуры, ограниченную графиками функций | Bagira_svs | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 23.10.2012 15:03 |
Найти площадь фигуры, ограниченной двумя кривыми!!! | Alex56 | C# (си шарп) | 0 | 28.12.2011 16:03 |
Найти площадь фигуры | samouelson | Помощь студентам | 2 | 17.12.2010 20:22 |
Найти центр сложной фигуры | mutabor | Свободное общение | 25 | 01.03.2010 23:36 |