Координаты вершин прямоугольника

[urusai_na]

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

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


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

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

[Brukvalub]

Так и для второго рис. прямоугольник построить можно.

[svv]

А так можно?

[urusai_na]

Brukvalub в сообщении #1020559 писал(а):

Так и для второго рис. прямоугольник построить можно.

нельзя! не выполняется условие:

Цитата:

...чтобы две заданные точки лежали на противоположных сторонах...

-- 27.05.2015, 22:20 --

svv в сообщении #1020560 писал(а):

А так можно?

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

[svv]

Так Brukvalub примерно о таком варианте и говорил.

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

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

[urusai_na]

svv в сообщении #1020567 писал(а):

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

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

[svv]

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

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


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

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

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

[urusai_na]

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

[svv]

Совершенно верно. Чувствую, что Вы так хорошо поняли меня, что мне и добавлять ничего не надо.

[urusai_na]

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

[svv]

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