Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859403 Sat, 19 Feb 2022 13:24:39 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859403 FasterHarder, поворот вектора на 90° – это умножение на i. Просто напомнил.]]> Qraizer Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859253 Wed, 16 Feb 2022 10:13:11 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859253 Цитата Akina @ 15.02.22, 20:17

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

ясно, буду разбираться
Akina, спс за помощь и за код на Basic, тоже буду разбираться)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859243 Wed, 16 Feb 2022 08:33:56 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859243 Цитата MIF @ 16.02.22, 08:07

можно по длине проекции на ось

?? У произвольно расположенного квадрата длины проекций на ось смежных сторон не равны. Равны длины проекций на разные оси, перекрёстно.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859233 Wed, 16 Feb 2022 08:07:52 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859233 Проходим по списку. Если количество отрезков одинаковой длины меньше 4, то они точно не принадлежат квадрату. Если >= 4, то используем идин из алгоритмов описанных выше.]]> MIF Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859216 Tue, 15 Feb 2022 20:17:38 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859216 Цитата FasterHarder @ 15.02.22, 19:36

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

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

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

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

Самое быстрое, что я находил - это проверка, что для каждой из 4 сторон заданная точка и центр квадрата лежат по одну сторону от прямой, на которой лежит сторона.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859215 Tue, 15 Feb 2022 19:36:19 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859215 Цитата Akina @ 15.02.22, 17:59

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

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

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

еще пример с выводом координат точек
test_1.png (, : 1329)

Цитата 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 сек,ну,понятно]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859209 Tue, 15 Feb 2022 17:59:38 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859209 Цитата 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 Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859190 Tue, 15 Feb 2022 12:54:53 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859190 Akina, ясно, попроще не получится), как и всегда в принципе...
но в любом случае крайне полезно мне было разобраться с проверкой на квадрат по 4рем точкам

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

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

Добавлено 15.02.22, 12:57
координаты - случ.дробные числа из отрезка [-100; +100], вроде хватит им "пространства" там]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859189 Tue, 15 Feb 2022 12:46:27 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859189 Цитата FasterHarder @ 15.02.22, 11:46

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

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

Достаточно обрабатывать пары. Для каждой пары точек существует всего два варианта, когда эти точки есть вершины стороны. А если предварительно отсортировать по какой-то координате, брать так, что первая левее второй - остаётся проверить вообще один вариант (см. Какой самый простой способ проверить на квадрат по 4рем заданным точкам? (сообщение #3859145)), а если угол меньше +/- 45^о (dX>dY) - так и вовсе ничего не надо проверять, ибо эта пара уже проверена. То есть для каждой пары точек 1 и 2 получаем точки 3 и 4 и проверяем, есть ли точки с такими координатами в наборе. Это будет О(n^2*log), что явно лучше n^5...]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859187 Tue, 15 Feb 2022 12:24:45 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859187 Цитата 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 (или еще выше куда-то там), хм...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859185 Tue, 15 Feb 2022 12:20:05 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859185 Цитата

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

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

Цитата

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

Это уже задача уровня "собеседование в Гугл", а то и выше. Ключевой момент: координаты целочисленные? Если да, то на ютубе есть пример решения похожей задачи (нужно посчитать количество прямоугольников), кандидат придумал красивое решение для прямоугольников, выровненных по осям, но алгоритм можно адаптировать и для общего случая.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859178 Tue, 15 Feb 2022 11:46:47 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859178 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 ). В этой функции зашиты проверки на равенство квадратов сторон и квадратов диагоналей.

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

всем спс. за участие, а особенно Akina за точную формулировку алгоритма, основанного ТОЛЬКО на расстояниях, без этих ужасных проверок на выпуклость и поворотов на 90%))]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859172 Tue, 15 Feb 2022 11:00:04 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859172 Цитата AVA12 @ 15.02.22, 07:34

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

... а на другом нет - то это стопудово не квадрат.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859164 Tue, 15 Feb 2022 09:37:47 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859164 Пусть одна из точек (любая) после такого вычитания имеет координаты (A, B). Тогда остальные должны иметь координаты (-B, A), (-A, -B), (B, -A).]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859145 Tue, 15 Feb 2022 07:34:41 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859145
Сортируем точки по какой-нибудь координате (например, по x). Получаем две крайние точки (например, самая левая и самая правая) и две промежуточные. Если на каком-то краю больше одной точки, то дополнительно сортируем по другой координате (например, крайними будут самая верхняя из самых левых и самая нижняя из самых правых).

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

Соответственно, берем крайнюю точку и одну из промежуточных, вычисляем коэффициенты a и b, проверяем, что оставшиеся точки имеют правильные координаты. Быстро, просто, без потери точности.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859143 Tue, 15 Feb 2022 06:36:56 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859143 MIF Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859141 Tue, 15 Feb 2022 04:12:20 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859141 2=CD²=AB²=AD² и BD²=AC² - у нас квадрат.

По мере движения по алгоритму любое неравенство - это "не квадрат", и дальше можно не считать.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859140 Tue, 15 Feb 2022 02:18:53 +0000 Какой самый простой способ проверить на квадрат по 4рем заданным точкам? https://forum.sources.ru/index.php?showtopic=425660&view=findpost&p=3859140
Условие такое: даны координаты 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 Алгоритмы