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

@Wladius · Регистрация: 06.01.2013

Author24 — интернет-сервис помощи студентам

Возможно не совсем понятно назвал тему - мне для курсовой работы по программированию нужно среди множества случайных точек (x1 y1) и тд найти все прямоугольники, желательно, одним уравнением, у меня была идея сделать это через площади - (x2-x1)(y2-y1)=(формула площади произвольного многоугольника) - если совпадают, то это прямоугольник.
Но такой вариант по-моему несколько не рационален, может быть сможете подсказать?

vetvet · 07.01.2013, 17:39

Одним уравнением вряд ли возможно.

Байт · 07.01.2013, 23:42

Скалярные произведения = 0
(x2-x1)(x3-x2) + (y2-y1)(y3-y2) = (x3-x2)(x4-x3) + (y3-y2)(y4-y3) = (x4-x3)(x1-x4) + (y4-y3)(y1-y4) =
(x1-x4)(x2-x1) + (y1-y4)(y2-y1) = 0
Уравнений, правда, получилось 4, но думаю, для опытного программиста это не проблема.
И еще, кажется, одно из уравнений лишнее, т.к. следует из остальных трех, но это еще надо проверять...

Добавлено через 9 минут
Хмм... Чуток репу почесал и понял что все не так просто. Трех уравнений не достаточно
Пример (0,0 (1,0) (1,1) ) (2,1)

@prokuratdm · 08.01.2013, 12:53

а если такой вариант:
берем 3 точки, вычисляем координату 4-ой и ищем ее среди имеющихся.
тоесть 3 точки: о(x0,y0), а(x1,y1), б(x2,y2)// получаем 2 вектора: оа и об и проверить перепендикулярность (оа*об=0)
оа+об=ос;//зная координаты вектора и точку найдем вторую точку а потом ищем ее в списке имееющихся

Байт · 08.01.2013, 13:16

Сообщение от prokuratdm

а если такой вариант:

Очень даже. У вас и направление перебора видно.
Но я просто пытался сформулировать условие прямоугольности.
Но если точки лежат в узлах клетчатой бумаги (о чем у ТС - ни звука), там еще более простые могут быть возможности.

@prokuratdm · 08.01.2013, 13:43

угумс). перебрать вашим способом будет быстрее.
p/s/ и где такие курсовые дают????

@Wladius · 08.01.2013, 13:59 **[ТС]**

Нет, точки лежат не в узлах клетчатой бумаги,
еще так вот думаю может сделать:
(((x[2]-x[1])*(x[0]-x[1]) + (y[2]-y[1])*(y[0]-y[1]))==0)&(((x[2]-x[3])*(x[0]-x[3]) + (y[2]-y[3])*(y[0]-y[3])==0)

Такие курсовые дают в ЛЭТИ на первом курсе

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

@prokuratdm · 08.01.2013, 14:25

хм.. если таким образом хотите то проще теоремой фалеса воспользоваться:
проверить противополжные стороны на параллелность(для каждой пары) и показать что один угол прямой
p/s/ ну хоть задание адекватное, а то стало страшно)

@Odzen · 11.09.2023, 19:21

Можно добавить проверку на равенство диагоналей.

C++

//conditions
        bool con_1, con_2;
        con_1 = ((x1 - x4) * (x2 - x1) + (y1 - y4) * (y2 - y1) == 0);
        double D1, D2;
        D1 = sqrt(pow(x1 - x3, 2) + pow(y1 - y3, 2));
        D2 = sqrt(pow(x2 - x4, 2) + pow(y2 - y4, 2));
        con_2 = (D1 == D2);
        if (con_1 && con_2)
            existence = true;
        else
        {
            existence = false;
            cout << "A rectangle with such coordinates cannot exist.\n";
        }

iifat · 12.09.2023, 12:47

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

@Igor3D · 12.09.2023, 13:24

Сообщение от Wladius

среди множества случайных точек (x1 y1) и тд найти все прямоугольники, желательно, одним уравнением,

Наверно найти все подмножества из 4 точек что образуют прямоугольник

Если так, то какие тут уравнения и геометрия вообще? Это алгоритм оптимизации, скорее даже техника программирования. Делаем 2 сортированных массива, один по xy, другой по yx чтобы быстро перебрать все точки. Короче lower_bound

iifat 2769 / 1817 / 200 Регистрация: 05.06.2011 Сообщений: 5,263
	12.09.2023, 12:47	10
	Может, стоит рассмотреть для каждой пары точек середину отрезка и длину? Если для двух пар точек эти данные совпадают, то эти четыре точки образуют прямоугольник. Если попробовать как-то отсортировать эти центры и радиусы, то такой алгоритм будет заметно быстрее перебора всех четвёрок точек для большого их количества. 0

Новые блоги и статьи
Как программировать под HCL Notes и создавать свои продукты на ее основе InfoMaster 11.01.2025 HCL Notes (ранее известный как IBM Notes и Lotus Notes) представляет собой мощную платформу для разработки корпоративных приложений, которая сочетает в себе функции электронной почты, календаря,. . .	Как работать с SVN (Subversion) InfoMaster 11.01.2025 Введение Система контроля версий является неотъемлемой частью современного процесса разработки программного обеспечения. Она обеспечивает управление изменениями в коде, позволяет отслеживать. . .	Использование GraphQL в JavaScript InfoMaster 11.01.2025 Введение в GraphQL и его преимущества В современной разработке веб-приложений эффективный обмен данными между клиентом и сервером играет ключевую роль. GraphQL представляет собой язык запросов и. . .	Администрирование Git, продвинутые техники работы с Git InfoMaster 11.01.2025 Основы управления репозиторием Эффективное управление Git-репозиторием требует глубокого понимания механизмов контроля доступа и инструментов администрирования. Рассмотрим ключевые аспекты. . .	Что такое HCL Notes и как с ним работать InfoMaster 10.01.2025 HCL Notes (ранее известный как IBM Notes и Lotus Notes) представляет собой комплексную платформу для совместной работы и обмена информацией в корпоративной среде. Это многофункциональное решение,. . .	Как работать с Git из Windows и Visual Studio InfoMaster 10.01.2025 Работа с Git в Windows Работа с Git в операционной системе Windows может быть осуществлена с помощью различных инструментов, каждый из которых обладает своими уникальными возможностями и. . .
Аналог оператора switch case в Python InfoMaster 10.01.2025 Оператор switch case используется в программировании для выбора одного из нескольких вариантов исполнения кода. Однако в языке Python этот оператор отсутствует. Понимание аналогов switch case в. . .	Отличия абстрактного класса от интерфейса InfoMaster 10.01.2025 В современной разработке программного обеспечения существуют два основных механизма реализации абстракции: абстрактные классы и интерфейсы. Эти инструменты, хотя и схожи в своей основной цели -. . .	Как работать в Git InfoMaster 10.01.2025 Git — это одна из наиболее популярных систем контроля версий, которая активно используется разработчиками по всему миру. Она позволяет эффективно управлять изменениями в коде, координировать работу. . .	Реализация передвижения персонажа в Unity3d на C# InfoMaster 10.01.2025 Реализация передвижения персонажа в Unity3D начинается с правильной настройки проекта. Этот этап критически важен для создания отзывчивого и плавного управления. Рассмотрим основные шаги для создания. . .	Docker: руководство для начинающих InfoMaster 10.01.2025 В современном мире разработки программного обеспечения контейнеризация стала неотъемлемой частью процесса создания и развертывания приложений. Docker, как ведущая платформа контейнеризации, произвела. . .	Книги и учебные ресурсы по C# InfoMaster 08.01.2025 Базовые учебники и руководства Одной из лучших книг для начинающих является "C# 10 и . NET 6 для начинающих" Эндрю Троелсена и Филиппа Джепикса . Книга последовательно раскрывает основные концепции. . .

@Wladius 12 / 7 / 3 Регистрация: 06.01.2013 Сообщений: 127
		1
	Как однозначно определить прямоугольник по координатам вершин 07.01.2013, 17:35. Показов 8680. Ответов 10 Метки нет (Все метки) Возможно не совсем понятно назвал тему - мне для курсовой работы по программированию нужно среди множества случайных точек (x1 y1) и тд найти все прямоугольники, желательно, одним уравнением, у меня была идея сделать это через площади - (x2-x1)(y2-y1)=(формула площади произвольного многоугольника) - если совпадают, то это прямоугольник. Но такой вариант по-моему несколько не рационален, может быть сможете подсказать? 0

vetvet Змеюка одышечная 9864 / 4595 / 178 Регистрация: 04.01.2011 Сообщений: 8,557
	07.01.2013, 17:39	2
	Одним уравнением вряд ли возможно. 0

Байт Диссидент 27707 / 17325 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	07.01.2013, 23:42	3
	Сообщение было отмечено как решение Решение Скалярные произведения = 0 (x2-x1)(x3-x2) + (y2-y1)(y3-y2) = (x3-x2)(x4-x3) + (y3-y2)(y4-y3) = (x4-x3)(x1-x4) + (y4-y3)(y1-y4) = (x1-x4)(x2-x1) + (y1-y4)(y2-y1) = 0 Уравнений, правда, получилось 4, но думаю, для опытного программиста это не проблема. И еще, кажется, одно из уравнений лишнее, т.к. следует из остальных трех, но это еще надо проверять... Добавлено через 9 минут Хмм... Чуток репу почесал и понял что все не так просто. Трех уравнений не достаточно Пример (0,0 (1,0) (1,1) ) (2,1) 3

@prokuratdm 12 / 12 / 0 Регистрация: 19.04.2012 Сообщений: 37
	08.01.2013, 12:53	4
	а если такой вариант: берем 3 точки, вычисляем координату 4-ой и ищем ее среди имеющихся. тоесть 3 точки: о(x0,y0), а(x1,y1), б(x2,y2)// получаем 2 вектора: оа и об и проверить перепендикулярность (оа*об=0) оа+об=ос;//зная координаты вектора и точку найдем вторую точку а потом ищем ее в списке имееющихся 2

Байт Диссидент 27707 / 17325 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	08.01.2013, 13:16	5
	Сообщение от prokuratdm а если такой вариант: Очень даже. У вас и направление перебора видно. Но я просто пытался сформулировать условие прямоугольности. Но если точки лежат в узлах клетчатой бумаги (о чем у ТС - ни звука), там еще более простые могут быть возможности. 0

@prokuratdm 12 / 12 / 0 Регистрация: 19.04.2012 Сообщений: 37
	08.01.2013, 13:43	6
	угумс). перебрать вашим способом будет быстрее. p/s/ и где такие курсовые дают???? 0

@Wladius 12 / 7 / 3 Регистрация: 06.01.2013 Сообщений: 127
	08.01.2013, 13:59 [ТС]	7
	Нет, точки лежат не в узлах клетчатой бумаги, еще так вот думаю может сделать: (((x[2]-x[1])(x[0]-x[1]) + (y[2]-y[1])(y[0]-y[1]))==0)&(((x[2]-x[3])(x[0]-x[3]) + (y[2]-y[3])(y[0]-y[3])==0) Такие курсовые дают в ЛЭТИ на первом курсе Но это еще не все задание, нужно еще найти все точки пересечения получившихся прямоугольников, вывести их по часовой стрелке (это уже придумал как сделать при помощи перевода из декартовой в радиальную) и найти наибольшую площадь пересечения прямоугольников. 0

@prokuratdm 12 / 12 / 0 Регистрация: 19.04.2012 Сообщений: 37
	08.01.2013, 14:25	8
	хм.. если таким образом хотите то проще теоремой фалеса воспользоваться: проверить противополжные стороны на параллелность(для каждой пары) и показать что один угол прямой p/s/ ну хоть задание адекватное, а то стало страшно) 0

@Igor3D 1911 / 773 / 108 Регистрация: 01.10.2012 Сообщений: 4,206
	12.09.2023, 13:24	11
	Сообщение от Wladius среди множества случайных точек (x1 y1) и тд найти все прямоугольники, желательно, одним уравнением, Наверно найти все подмножества из 4 точек что образуют прямоугольник Если так, то какие тут уравнения и геометрия вообще? Это алгоритм оптимизации, скорее даже техника программирования. Делаем 2 сортированных массива, один по xy, другой по yx чтобы быстро перебрать все точки. Короче lower_bound 0

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

Решение