2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Координаты вершин прямоугольника
Сообщение27.05.2015, 22:50 
Аватара пользователя


27/05/15
5
Херсон
Здравствуйте!
Есть некоторый набор точек на плоскости (>=2), две из этих точек должны лежать на противоположных сторонах прямоугольника, все остальные могут лежать как внутри него так и снаружи, необходимо:
1) получить ответ, можно ли построить этот прямоугольник таким образом, чтобы все точки лежали внутри него, а самые отдалённые точки лежали на сторонах (т.е. можно ли построить прямоугольник который обводит все точки, но он должен быть ориентирован так чтобы две заданные точки лежали на противоположных сторонах, см. Рис. 1, 2);
Изображение
Рис. 1 - Набор точек для которого можно построить прямоугольник (заданы точки 1 и 6)

Изображение
Рис. 2 - Набор точек при котором невозможно построить прямоугольник (заданы точки 1 и 6)

2) если прямоугольник можно построить, то необходимо найти координаты всех вершин минимального по размерам прямоугольника.
Данная задача является подзадачей оптимизации пути (уменьшения к-ва точек - выбрасывания избыточных) по заданны параметрам, далее характеристики этого прямоугольника будут сравниваться с заданными: ширина - с удвоенным максимальным отклонением от курса, длина - с минимальным расстояним между точками. На основании этих данных (и некоторых других не связанных с геометрией) будет приниматься решение какой из прямоугольников использовать для приближения. Для приближения предполагается использовать среднюю линию прямоугольника, проведённую в направлении движения. Если кто-то может предложить какие-то варианты получше, для решения основной задачи, буду только рад.

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение27.05.2015, 22:58 
Заслуженный участник
Аватара пользователя


01/03/06
13104
Москва
Так и для второго рис. прямоугольник построить можно.

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение27.05.2015, 23:11 
Заслуженный участник


23/07/08
7667
Харьков
А так можно?
Изображение

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение27.05.2015, 23:15 
Аватара пользователя


27/05/15
5
Херсон
Brukvalub в сообщении #1020559 писал(а):
Так и для второго рис. прямоугольник построить можно.

нельзя! не выполняется условие:
Цитата:
...чтобы две заданные точки лежали на противоположных сторонах...


-- 27.05.2015, 22:20 --

svv в сообщении #1020560 писал(а):
А так можно?
Изображение

так, как вы нарисовали, в приципе можно, кроме того, возможно тот случай который я нарисовал не очень коректно илюстрирует ситуацию, но наверняка есть такие наборы точек, на котрых это не получится, так как некотрые точки будут лежать за пределами, например такой (заданы точки 1 и 6):
Изображение

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение27.05.2015, 23:29 
Заслуженный участник


23/07/08
7667
Харьков
Так Brukvalub примерно о таком варианте и говорил.

-- Ср май 27, 2015 23:38:11 --

Вот мой пример, когда нельзя: перенумеруйте вершины правильного пятиугольника, обходя по периметру, возьмите вершины 1 и 2 в качестве заданных.

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение27.05.2015, 23:46 
Аватара пользователя


27/05/15
5
Херсон
svv в сообщении #1020567 писал(а):
перенумеруйте вершины правильного пятиугольника, обходя по периметру, возьмите вершины 1 и 2 в качестве заданных

можно и так, конечно, но, думаю, последеней илюстрации достаточно, как к ней не подойди - прямоугольником обрисовать не получится. А как насчёт самой задачи, идеи есть?

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение27.05.2015, 23:48 
Заслуженный участник


23/07/08
7667
Харьков
Есть. С помощью простого алгоритма можно определить, существует ли такой прямоугольник. Но мне нужно время, чтобы облечь в словесную форму.

-- Чт май 28, 2015 00:17:32 --

Изображение
Вам известны координаты $(x, y)$ всех точек. Берём заданную точку (на рисунке красная) и проводим векторы от неё ко всем остальным точкам. У каждого вектора есть направление (угол, который вектор составляет с осью $Ox$, отсчитывая против часовой стрелки). Сортируем направления по возрастанию угла. У нас получается список, который мы считаем кольцевым (считаем, что после последнего вектора в списке идёт первый, и эти два вектора тоже соседние). Находим углы между всеми соседними векторами. Задаёмся вопросом: есть ли такие два соседних вектора в списке, между которыми угол $\geqslant\pi$? Если нет, нужного прямоугольника не существует. На рисунке как раз изображен случай, когда такого угла нет.

Если да, повторяем ту же процедуру для второй заданной точки. Смотрим, есть ли для неё такие два соседних направления, угол между которыми $\geqslant\pi$? Если нет, нужного прямоугольника не существует.

Если в обоих случаях ответ «да», остался простой тест... но сначала скажите, всё ли понятно выше?

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение28.05.2015, 00:38 
Аватара пользователя


27/05/15
5
Херсон
т. е. мы таким образом доказываем, что существует прямая проходящая через данную точку, и при этом все остальные точки либо лежат на этой прямой, либо находятся по одну сторону от неё?

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение28.05.2015, 00:39 
Заслуженный участник


23/07/08
7667
Харьков
Совершенно верно. Чувствую, что Вы так хорошо поняли меня, что мне и добавлять ничего не надо. :P

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение28.05.2015, 00:49 
Аватара пользователя


27/05/15
5
Херсон
да, только этого недостаточно для подтверждения существования, даже если проделать это и для второй точки, кроме того остаётся самое сложное - найти вершины этого прямоугольника.

 Профиль  
                  
 
 Re: Координаты вершин прямоугольника
Сообщение28.05.2015, 01:12 
Заслуженный участник


23/07/08
7667
Харьков
Ну да, я ж говорю, что остался ещё один простой тест.
Попробуйте догадаться по картинке, что надо делать дальше, если оба ответа — «да».
Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group