Какой самый простой способ проверить на квадрат по 4рем заданным точкам?

[FasterHarder]

Всем хай! Сходу к делу!

Условие такое: даны координаты 4рех точек на плоскости. Узнать, образуют ли они квадрат.

Вроде(!) простая вещь, но тем не менее...
Точки задаются произвольно, т е не в порядке обхода вершин квадрата + они вещественные + стороны квадрата могут быть не || осям координат - это я дополнил условие.

В сети море обсуждений этой проверки + оч.много споров + казалось, бы на верный ответ (под 100 плюсов) находили опровержения и пр. пр.
Решают и через расстояния, и через скалярные произведения, и через повороты, и через вписанные/описанные окружности, через перпендикулярность сторон/диагоналей и через предварительную сортировку координат и еще как-то мутят, кто как может). Многие в алгоритмах избегают взятия квадратного корня, а зря(!) ), хотя это мат.операция являются тяжелой вроде как для вычислений ЦП

Мне бы хотелось понять самый простой и ПОЛНЫЙ алгоритм такой проверки, и главное БЕЗ поворотов отрезков (сторон) и очень желательно без проверки на выпуклость (т к это сложно!). В идеале хотелось бы обойтись лишь нахождением длин сторон...

Допустим, есть такое определение сущности "точка" в терминах языка С (С89):

typedef struct TPoint
{
    // берем double, т к все мат.функции из С89 заточены на этот тип данных (в С99 добавили и для float)
    double x;
    double y;
} Point;

Далее, ввели координаты 4рех точек: A, B, C, D.
1 этап (обязательный): проверить, что их координаты различны. Сравниваем координаты A-B, A-C, A-D, B-C, B-D, C-D - 6 проверок. При любом совпадении - это не четырехугольник.
При этом здесь не обращаем на выпуклость. Это не важно, просто проверка координат 4рех точек на не совпадение.
2 этап: можно взять ЛЮБУЮ точку (пусть А) и найти расстояние до всех остальных (расстояния гарантированно будут не нулевыми). 2 из 3 этих расстояний ОБЯЗАНО быть одинаковым, а 3е больше в корень(2) раз. Но это ведь НЕДОСТАТОЧНОЕ условие. Можно попробовать найти диагональную вершину для точки А. Допустим. После этого найти расстояние между двумя остальными.

Затем можно пробовать проверять перпендикулярность "диагоналей", но не уверен, что все этого достаточно для однозначной идентификации квадрата.

Вот каким образом ПРОЩЕ ВСЕГО сделать такую проверку? Подскажите как быть-то.
Спс за внимание.

p.s. оч.желательно БЕЗ поворотов и проверки на выпуклость - это сложнА)

Сообщение отредактировано: FasterHarder - 15.02.22, 02:19

[Akina]

Берёшь произвольную точку (обозначаем её A) и считаешь квадрат расстояния до каждой из трёх других (B,C,D). Проверяешь, что для двух из трёх он одинаков (обозначаем их B,D), а для третьей вдвое больше (соответственно C). Считаешь квадраты расстояний BC, BD и CD. Если итогово BC²=CD²=AB²=AD² и BD²=AC² - у нас квадрат.

По мере движения по алгоритму любое неравенство - это "не квадрат", и дальше можно не считать.

[MIF]

Измеряешь длины трех пар отрезков: АВ и СД, АС и ВД, АД и ВС. Каждая пара отрезков будет иметь одинаковые длины.

[AVA12]

Можно обойтись одними только сложениями и вычитаниями.

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

Возьмем одну из крайних точек, ее координаты (x; y). В любом квадрате координаты промежуточных точек будут (x+a; y+b) и (x+b; y-a), а координаты противоположной точки - (x+a+b; y-a+b)

Соответственно, берем крайнюю точку и одну из промежуточных, вычисляем коэффициенты a и b, проверяем, что оставшиеся точки имеют правильные координаты. Быстро, просто, без потери точности.

[OpenGL]

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

[Akina]

Цитата AVA12 @ 15.02.22, 07:34

Если на каком-то краю больше одной точки

... а на другом нет - то это стопудово не квадрат.

[FasterHarder]

Akina, спс за алгоритм, где нужно ТОЛЬКО вычислять расстояния - именно то, что я и хотел)

насчет этого условия понятно:

Цитата Akina @ 15.02.22, 04:12

BC2=CD2=AB2=AD2

по определению квадрата у него все стороны равны (значит, и квадраты сторон равны, т к сторона сама по себе - всегда положительное число)
но этого условия недостаточно, т к, например, у ромба ТОЖЕ все стороны равны

перпендикулярность диагоналей брать не стоит, т к опять-таки у ромба они перпендикулярны тоже, поэтому берем

Цитата Akina @ 15.02.22, 04:12

BD2=AC2

и остается ТОЛЬКО квадрат в итоге. Если брать только равенство диагоналей, то было бы также недостаточно, т к, например, у прямоугольника они тоже равны.

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

Если я все правильно понял в алгоритме Akina, то теперь нет нужды проверять сначала точки на совпадение по координатам, а достаточно просто, например, проверить квадрат любой стороны, например, АВ на равенство 0, если 0 - это не квадрат и все. Т е всего ОДНА проверка вместо 6.
---------------------------------------
Передо мной стоит задача более сложная, чем проверка на квадрат, просто там это обязательный этап, поэтому решил разобраться с ним и даже на этом (самом простом этапе) получил проблемы)

В целом, у меня есть коллекция точек (одномерный массив точек) points[N] из N штук, где N in [4; 2000]. И нужно получить все возможные квадраты, которые можно получить по заданным N точкам и среди них выбрать квадрат, внутри которого попадает больше всего точек из этой коллекции точек (точки, лежащие на границе в квадрат не попадают).

Чтобы получить все возможные квадраты придется запускать 4ре вложенных цикла FOR(!):

for i = 0; i < (N - 4); i++
   for j = i + 1; j < (N - 3); j++
        for k = j + 1; k < (N - 2); k++
              for l = k + 1; l < (N - 1); l++

Если я правильно понимаю, то получаем вычислительную сложность алгоритма O(N^4): (N - 4) * (N - 3) * (N - 2) * (N - 1) = N^4 -... самое "тяжелое" слагаемое в этом выражении в 4ой степени, значит, сложность алгоритма аналогичная, вроде так, но это неточно...Не уверен, что 2000 точек легко комп переберет по 4кам, хотя 2000 не 2млн, справится). Кроме перебора здесь ведь невозможно ничего другого в принципе.

В итоге текущий квадрат имеет координаты points[ i ], points[ j ], points[ k ], points[ l ]. Точка points[ i ] принимается по дефалту за вершину А.

Функции программы:
0. ввод количества точек множества точек
1. ввод исходных координат points = Получить_координаты_с_клавиатуры( количество точек ) (этот интерфейс легко расширяется до Получить_координаты_из_файла или Получить_координаты_случ_образом). Возможно, чуть удобнее иметь функцию ввода координат одной точки...
2. нахождение квадрата расстояние между 2 заданными точками: double Получить_квадрат_расстояния_между_заданными_2_точками( точка1, точка2 )
3. вывод координат квадрата на экран: Вывести_квадрат_на_экран( точка1, точка2, точка3, точка4 )
4. важнейшая функция Получить_диагональную_вершину_квадрата (points[ i ], points[ j ], points[ k ], points[ l ]). В качестве ответа она, думаю, что вернет № параметра, это либо число 2, 3 или 4 (параметр №1 это точка А - первая диагональная вершина). После получения номера этой вершины будет switch-case для построения отрезков AB, BC и т.д. и далее проверки, озвученные выше.
5. проверка 4гольника на квадрат bool Это_квадрат( A, B, C, D ). В этой функции зашиты проверки на равенство квадратов сторон и квадратов диагоналей.

Вот минимальный набор функций.
-----------------------------------------------
Затем еще потребуется функция, которая будет проверять попадание точки в область квадрата, эх, был бы круг с известным центром, было бы изи , а так вот сходу тоже непонятно , что да как, но над этим еще подумаю

всем спс. за участие, а особенно Akina за точную формулировку алгоритма, основанного ТОЛЬКО на расстояниях, без этих ужасных проверок на выпуклость и поворотов на 90%))

[AVA12]

Цитата

... а на другом нет - то это стопудово не квадрат

Это лишний if, а экономия копеечная, нафиг.

Цитата

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

Это уже задача уровня "собеседование в Гугл", а то и выше. Ключевой момент: координаты целочисленные? Если да, то на ютубе есть пример решения похожей задачи (нужно посчитать количество прямоугольников), кандидат придумал красивое решение для прямоугольников, выровненных по осям, но алгоритм можно адаптировать и для общего случая.

[FasterHarder]

Цитата AVA12 @ 15.02.22, 12:20

Это уже задача уровня "собеседование в Гугл"

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

Цитата AVA12 @ 15.02.22, 12:20

координаты целочисленные?

нет, конечно, в посте №1 спец. привел декларацию описания сущности "Точка" и там даблы {x; y}

Добавлено 15.02.22, 12:27
не, а в чем проблема-то? Если есть понимание того, как проверить 4ре координаты на квадратность, то можно проверить и 2000 точек
или здесь проблема с быстродействием всего этого дела...хм...надо попробовать протестить на разном кол-ве точек..

Добавлено 15.02.22, 12:35
ну, да, я понял, что здесь все упрется в производительность, т к ДЛЯ каждого квадрата нужно прогонять КАЖДУЮ точку на проверку для попадания в этот квадрат, итогда сложность возрастает до N^5 (или еще выше куда-то там), хм...

[Akina]

Цитата FasterHarder @ 15.02.22, 11:46

нужно получить все возможные квадраты, которые можно получить по заданным N точкам

Так это ты вообще не с той стороны заходишь! типичная XY-проблема.

Достаточно обрабатывать пары. Для каждой пары точек существует всего два варианта, когда эти точки есть вершины стороны. А если предварительно отсортировать по какой-то координате, брать так, что первая левее второй - остаётся проверить вообще один вариант (см. Какой самый простой способ проверить на квадрат по 4рем заданным точкам? (сообщение #3859145)), а если угол меньше +/- 45^о (dX>dY) - так и вовсе ничего не надо проверять, ибо эта пара уже проверена. То есть для каждой пары точек 1 и 2 получаем точки 3 и 4 и проверяем, есть ли точки с такими координатами в наборе. Это будет О(n^2*log), что явно лучше n^5...

Сообщение отредактировано: Akina - 15.02.22, 12:53

[FasterHarder]

Akina, ясно, попроще не получится), как и всегда в принципе...
но в любом случае крайне полезно мне было разобраться с проверкой на квадрат по 4рем точкам

ладно, пойду раскуривать эти подходы с сортировкой, поворотами и пр., все-таки никуда от них не деться, эх...

Добавлено 15.02.22, 12:56
но я в любом случае сделаю вариант с перебором, чтобы посмотреть на время выполнения и прогоню для набора из 10, 50, 100, 250, 500, 1000, 1500 и 2000 точек)

Добавлено 15.02.22, 12:57
координаты - случ.дробные числа из отрезка [-100; +100], вроде хватит им "пространства" там

[Akina]

Цитата FasterHarder @ 15.02.22, 12:54

пойду раскуривать эти подходы с сортировкой, поворотами и пр., все-таки никуда от них не деться

Повороты нафиг не нужны. AVA12 чётко показал, что достаточно вульгарной арифметики класса плюс-минус и больше-меньше.

Цитата FasterHarder @ 15.02.22, 12:54

координаты - случ.дробные числа из отрезка [-100; +100], вроде хватит им "пространства" там

Ню-ню... ты хотя бы прикинь вероятность, что там хоть один квадрат накопается - сразу поймёшь, что нужен ни фига не рандом.

Добавлено 15.02.22, 18:43
В общем, накидал быстренько программку в VBA (Excel 2010). Генерирует 1000 точек с целыми координатами в квадрате (0,0)-(100,100), а потом ищет четвёрки, образующие квадрат.

Type mypoint
    x As Integer
    y As Integer
End Type
 
Dim mypoints() As mypoint
 
Const amount As Integer = 1000
 
Sub test()
Dim i As Integer, j As Integer
Dim dX As Integer, dY As Integer
Dim tmp As mypoint
Dim t As Single
t = Timer
 
Call generate_points
For i = 1 To amount - 1
    For j = i + 1 To amount
        dX = mypoints(j).x - mypoints(i).x
        dY = mypoints(j).y - mypoints(i).y
        If Abs(dX) > Abs(dY) Or (Abs(dX) = Abs(dY) And dY > 0) Then
            Exit For
        End If
        mypoints(0).x = mypoints(i).x + Abs(dY)
        mypoints(0).y = mypoints(i).y - Abs(dX) * Sgn(dY)
        If Not check_presence(i) Then
            Exit For
        End If
        tmp = mypoints(0)
        mypoints(0).x = mypoints(i).x + Abs(dX) + Abs(dY)
        mypoints(0).y = mypoints(i).y + Abs(dY) - Abs(dX) * Sgn(dY)
        If Not check_presence(i) Then
            Exit For
        End If
        If mypoints(i).x <> mypoints(j).x Or mypoints(i).y <> mypoints(j).y Then
            Debug.Print mypoints(i).x; mypoints(i).y, mypoints(j).x; mypoints(j).y, tmp.x; tmp.y, mypoints(0).x; mypoints(0).y
        End If
    Next
Next
 
Debug.Print "Elapsed time: "; Timer - t
End Sub
 
Sub generate_points()
Dim i As Integer, j As Integer
ReDim mypoints(0 To amount)
For i = 1 To amount
    mypoints(i).x = 1 + 99 * Rnd
    mypoints(i).y = 1 + 99 * Rnd
Next
For i = 1 To amount - 1
    For j = i + 1 To amount
        If mypoints(i).x > mypoints(j).x Or (mypoints(i).x = mypoints(j).x And mypoints(i).y > mypoints(j).y) Then
            mypoints(0) = mypoints(i)
            mypoints(i) = mypoints(j)
            mypoints(j) = mypoints(0)
        End If
    Next
Next
End Sub
 
Function check_presence(n As Integer) As Boolean
Dim i As Integer
For i = n + 1 To amount
    If mypoints(0).x = mypoints(i).x And mypoints(0).y = mypoints(i).y Then
        check_presence = True
        Exit Function
    End If
Next
End Function

В среднем на запуск находит 3-8 квадратов (вырожденные находит, но не выводит), время работы 0,15-0,20 секунды (Intel® Core™2 Duo CPU E7500 @ 2.93GHz, 4Gb RAM, Windows 10 x64).

Сообщение отредактировано: Akina - 15.02.22, 18:48

[FasterHarder]

Цитата Akina @ 15.02.22, 17:59

Ню-ню... ты хотя бы прикинь вероятность, что там хоть один квадрат накопается - сразу поймёшь, что нужен ни фига не рандом.

я уже понял это) Вероятность того, что на таком огромном пространстве выпадут четко вершины квадрата вообще стремится к 0.
тоже написал программку, только на С++ (250 строк кода, 10 функций) и она ТОЛЬКО занимается полным перебором всех четверок, вот такие результаты получились
при генерации случ.чисел от -0.5 до +0.5 и точности сравнения вещественных до 0.005

Прикреплённая картинка

показатели генерации случ.чисел + точность сравнения колоссально влияет на кол-во поиска квадратов, конечно

еще пример с выводом координат точек

Прикреплённая картинка

Цитата Akina @ 15.02.22, 17:59

В среднем на запуск находит 3-8 квадратов (вырожденные находит, но не выводит), время работы 0,15-0,20 секунды

т е 1000 точек отрабатывает за 0.2 сек, хм, неплохо, конечно) моя прожка найдет за 0.2 * 10000, мда уж...но я хотел проверить как себя поведет полный перебор в таких задачах, в общем понятно, что до 100 точек еще терпимо, но потом кранты.

В БИГ ДАТА алгоритмы играю абсолютно решающую роль (разница может доходит до триллион раз и это без преувеличений).

----------------------------------------------------------------
А насчет проверки попадания точки в квадрат, есть такая идея: соединить эту точку со всеми вершинами квадрата, получив 4ре треугольника (триангуляция), и, если точка попадает в область квадрата, то сумма площадей 4рех треугольников = площади квадрата. Площадь треугольника считать по формуле Герона, а квадрата вроде (любая сторона)^2. Понятно, что время работы моей программы в случае, когда все вершины образуют квадраты ---> "вечность", а при среднем запуске просто минуты будет, т к реальных квадратов не так уж и много образуется.

Это ужасная идея или имеет право на жизнь?

Добавлено 15.02.22, 19:44

Цитата Akina @ 15.02.22, 17:59

время работы 0,15-0,20 секунды

я правильно понимаю, что время не учитывает сортировку координат, хотя, наверное, отсортировать 1000 точек - меньше 0.05 сек,ну,понятно

[Akina]

Цитата FasterHarder @ 15.02.22, 19:36

я правильно понимаю, что время не учитывает сортировку координат, хотя, наверное, отсортировать 1000 точек - меньше 0.05 сек,ну,понятно

Неправильно. В коде прекрасно видно, что за время считается - берётся полное время работы алгоритма (из которого чуть ли не половина - это на самом деле вывод на экран (Debug.Print - штука ни хрена не быстрая, порядка 0,01 секунды на один вывод), так что реально скорость обработки 1000 точек где-то 0,12 секунды).

Цитата FasterHarder @ 15.02.22, 19:36

А насчет проверки попадания точки в квадрат, есть такая идея

Самое быстрое, что я находил - это проверка, что для каждой из 4 сторон заданная точка и центр квадрата лежат по одну сторону от прямой, на которой лежит сторона.

[MIF]

Находим все отрезки, упорядочиваем их по длине (можно по длине проекции на ось)
Проходим по списку. Если количество отрезков одинаковой длины меньше 4, то они точно не принадлежат квадрату. Если >= 4, то используем идин из алгоритмов описанных выше.