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

@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++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//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

Новые блоги и статьи Все статьи Все блоги /
std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .	Метод с двумя буферами (или double buffering) или ping-pong buffering Hrethgir 02.04.2025 Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .	На любовном киберфронте Alexander-7 01.04.2025 Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .	Как работает Node.js изнутри run.dev 29.03.2025 Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .
Моки в Python: Mock Object Library py-thonny 29.03.2025 Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .	JavaScript: Управление памятью и улучшение производительности run.dev 29.03.2025 В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .	Мультитенантная архитектура со SpringBoot и PostgreSQL ArchitectMsa 29.03.2025 SaaS-приложения редко обслуживают одного клиента и обычно они должны поддерживать множество организаций, каждая из которых работает в своём изолированном пространстве. Мультитенантная архитектура. . .	std::span в C++: Производительность и лучшие практики NullReferenced 28.03.2025 std::span — одно из самых недооценённых нововведений стандарта C++20, которое радикально меняет подход к работе с непрерывными последовательностями данных. По сути, это невладеющее представление. . .	Многопоточность в C#: Threadpool UnmanagedCoder 28.03.2025 Пул потоков в C# — это коллекция заранее созданных и готовых к использованию потоков, которые находятся в распоряжении приложения. Вместо того чтобы создавать и уничтожать потоки для каждой небольшой. . .

@Wladius 12 / 7 / 3 Регистрация: 06.01.2013 Сообщений: 127

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

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

Байт Диссидент 27710 / 17328 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	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) 3

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

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

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

@Wladius 12 / 7 / 3 Регистрация: 06.01.2013 Сообщений: 127
	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) Такие курсовые дают в ЛЭТИ на первом курсе Но это еще не все задание, нужно еще найти все точки пересечения получившихся прямоугольников, вывести их по часовой стрелке (это уже придумал как сделать при помощи перевода из декартовой в радиальную) и найти наибольшую площадь пересечения прямоугольников. 0

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

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

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

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

Решение