2014 dxdy logo

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

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




 
 Координаты вершин прямоугольника
Сообщение27.05.2015, 22:50 
Аватара пользователя
Здравствуйте!
Есть некоторый набор точек на плоскости (>=2), две из этих точек должны лежать на противоположных сторонах прямоугольника, все остальные могут лежать как внутри него так и снаружи, необходимо:
1) получить ответ, можно ли построить этот прямоугольник таким образом, чтобы все точки лежали внутри него, а самые отдалённые точки лежали на сторонах (т.е. можно ли построить прямоугольник который обводит все точки, но он должен быть ориентирован так чтобы две заданные точки лежали на противоположных сторонах, см. Рис. 1, 2);
Изображение
Рис. 1 - Набор точек для которого можно построить прямоугольник (заданы точки 1 и 6)

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

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

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

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

 
 
 
 Re: Координаты вершин прямоугольника
Сообщение27.05.2015, 23:15 
Аватара пользователя
Brukvalub в сообщении #1020559 писал(а):
Так и для второго рис. прямоугольник построить можно.

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


-- 27.05.2015, 22:20 --

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

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

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

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

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

 
 
 
 Re: Координаты вершин прямоугольника
Сообщение27.05.2015, 23:46 
Аватара пользователя
svv в сообщении #1020567 писал(а):
перенумеруйте вершины правильного пятиугольника, обходя по периметру, возьмите вершины 1 и 2 в качестве заданных

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

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

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

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

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

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

 
 
 
 Re: Координаты вершин прямоугольника
Сообщение28.05.2015, 00:38 
Аватара пользователя
т. е. мы таким образом доказываем, что существует прямая проходящая через данную точку, и при этом все остальные точки либо лежат на этой прямой, либо находятся по одну сторону от неё?

 
 
 
 Re: Координаты вершин прямоугольника
Сообщение28.05.2015, 00:39 
Аватара пользователя
Совершенно верно. Чувствую, что Вы так хорошо поняли меня, что мне и добавлять ничего не надо. :P

 
 
 
 Re: Координаты вершин прямоугольника
Сообщение28.05.2015, 00:49 
Аватара пользователя
да, только этого недостаточно для подтверждения существования, даже если проделать это и для второй точки, кроме того остаётся самое сложное - найти вершины этого прямоугольника.

 
 
 
 Re: Координаты вершин прямоугольника
Сообщение28.05.2015, 01:12 
Аватара пользователя
Ну да, я ж говорю, что остался ещё один простой тест.
Попробуйте догадаться по картинке, что надо делать дальше, если оба ответа — «да».
Изображение

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group