C/C++

В системе координат заданы 4 точки. Выяснить, в каких случаях они могут образовать квадрат.

Имеются координаты четырёх точек. Точки могут быть в произвольном порядке. Квадрат, если он есть, может быть вовсе не параллелен осям координат, то беж произвольный. Как определить, образуют ли они квадрат, и если да - то в какой последовательности.
Алексей Адаменко
Алексей Адаменко
2 306
Взять одну точку и проверить расстояния от неё до 3 остальных. Если 2 расстояния одинаковые, а 3е - больше их в (корень из 2) раз и расстояние между 2 и 3 - тоже больше в кор2 и проверить на одинаковость стороны
Музафар Мухтаров
Музафар Мухтаров
26 850
Лучший ответ
Алиби Сакенов Вот только расстояния 2-4 и 3-4 тоже нужно проверять, иначе 4 может оказаться где угодно.
Найти расстояния между каждой парой точек (всего 6 пар). Отсортировать эти расстояния. Если 4 самых малых расстояния (стороны) равны между собой и 2 самых больших расстояния (диагонали) равны между собой - у нас квадрат.

Существует всего 3 варианта последовательности точек, образующих квадрат: A-B-C-D, A-B-D-C, A-C-B-D (от изменения направления движения или смены начальной точки обхода квадрат не меняется). Таким образом, зная, какие точки образовали диагонали, можно сразу же найти последовательность точек, образующих квадрат.

Проще проделать всё это не с расстояниями, а квадратами расстояний - результат будет тем же, но не надо будет извлекать квадратные корни.
PP
Par Par
69 434
Александр Шатов ИСЧЕРПЫВАЮЩЕ
Квадрат получится однозначно, если обе его диагонали равны между собой. Диагональ определяется как корень квадратный из суммы катетов.
ИМ
Илияс Максатов
69 959
Алексей Адаменко а если ввести координаты двух точек, которые будут находится в одном месте?
Сергей Мереха Только сначала определить, где сторона, а где диагональ. Ведь так?
Par Par Нет, этого совершенно недостаточно. Кроме равенства диагоналей необходимо ещё:
1. точка пересечения диагоналей лежит в центрах обеих диагоналей.
2. диагонали образуют прямой угол.
сам сделаешь?
IB
Igor Bolotin
21 700
　 Альтернативный метод решения — через угловые коэффициенты. Рассматриваются: каждый угол при вершине фигуры и один угол на пересечении диагоналей (любой), итого — 5.

　 Каждый угловой коэффициент лучше не вычислять до единственного числа (деление имеет довольно высокую погрешность), а оставить в виде пары чисел: числитель и знаменатель. В дальнейшем для проверки угла угловые коэффициенты смежных сторон следует перемножить, то есть отдельно перемножить числители (они же — проекции на OY), отдельно перемножить знаменатели (а это — проекции на OX). Если оба произведения равны, то угол между смежными сторонами прямой.

　 Если все 5 углов оказались прямыми, то четырёхугольник является квадратом.

　 Отдельно необходимо отметить единственный случай исключения: если все 4 заданные точки совпадают, то получается т. н. вырожденный квадрат, который, строго говоря, квадратом не признаётся!

　 Если более двух точек окажется на одной прямой, то произведение угловых коэффициентов это учитывает!
T?mur Welnazarow
T?mur Welnazarow
16 172
T?mur Welnazarow 　 Как известно, если в произвольном прямоугольнике углы при всех вершинах прямые; в произвольном ромбе диагонали пересекаются под прямым углом. Ну а квадрат — это ромб-прямоугольник.

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

Sic
T?mur Welnazarow 　 Кстати, если сторона квадрата строго вертикальна, то её горизонтальная проекция равна 0, и угловой коэффициент вычислить невозможно вследствие деления на 0. Так!!!

　 Вот причина оставить угловой коэффициент в виде пары проекций.

Похожие вопросы