Нахождение квадратов на плоскости по заданным n точкам

Question

Учитывая n точек на плоскости, сколько квадратов можно сформировать ... ??

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

Но это похоже на подход с очень высокой сложностью.Любые другие идеи ... ??

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

Любойлучшие идеи ???

PS: квадраты могут быть любыми.Они могут накладываться друг на друга, иметь общую сторону, один квадрат внутри другого ...

Любые ссылки, которые помогают мне лучше понять проблему, являются заметными ... Если возможно, пожалуйста, дайте пример кода для выполнения вышеуказанного ...

Answer 1

Эта проблема может быть решена за O(n^1.5) время с помощью O(n) пробела.

Основная идея - сгруппировать точки по координатам X или Y, стараясь не создавать слишком большие группы.Подробности в документе Поиск квадратов и прямоугольников в наборах точек .В статье также рассматривается множество других случаев (допускается вращение квадратов, прямоугольников и работа в более высоких измерениях).

Я перефразировал их алгоритм поиска квадратов с выравниванием по 2-й оси ниже.Обратите внимание, что я изменил их древовидный набор на хеш-набор, поэтому указанная мною временная граница не равна O(n^1.5 log(n)):

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

2. Сгруппируйте точки по их координате X.Разбейте все группы с более чем sqrt(n) точками и перегруппируйте эти свободные сейчас точки по их координате Y.Это гарантирует, что группы имеют не более sqrt(n) точек , а гарантирует, что для каждого квадрата есть группа, имеющая две угловые точки квадрата.

3. для каждой группыg, для каждой пары точек p,q в g проверьте наличие двух других точек из двух возможных квадратов, содержащих p и q.Следите за тем, сколько вы найдете.Остерегайтесь дубликатов (две противоположные точки также в группе?).

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

Answer 2

У меня есть O (N ^ 2) время, O (N) пространственное решение:

Предположим, что данные точки являются массивом объектов Point, каждая точка имеет x, y.

1. Сначала выполните итерацию по массиву и добавьте каждый элемент в HashSet: это действие устраняет дублирование и дает нам время доступа O (1).Весь процесс занимает O (N) времени
2. С помощью Math, Say вершины A, B, C, D могут образовывать квадрат, AC известен и это диагональная линия, тогда соответствующие B, D уникальны.Мы могли бы написать функцию для вычисления этого.Этот процесс O (1) время
3. Теперь давайте вернемся к нашей вещи.написать цикл for-i и цикл for-j-inner.Скажите, что input [i] и input [j] образуют диагональную линию, найдите ее антидиагональную линию в наборе или нет: если существует, counter ++;Этот процесс занимает O (N ^ 2) времени.

Мой код на C #:

    public int SquareCount(Point[] input)
    {
        int count = 0;

        HashSet<Point> set = new HashSet<Point>();
        foreach (var point in input)
            set.Add(point);

        for (int i = 0; i < input.Length; i++)
        {
            for (int j = 0; j < input.Length; j++)
            {
                if (i == j)
                    continue;
                //For each Point i, Point j, check if b&d exist in set.
                Point[] DiagVertex = GetRestPints(input[i], input[j]);
                if (set.Contains(DiagVertex[0]) && set.Contains(DiagVertex[1]))
                {
                    count++;
                }
            }
        }
        return count;

    }

    public Point[] GetRestPints(Point a, Point c)
    {
        Point[] res = new Point[2];

        int midX = (a.x + c.y) / 2;
        int midY = (a.y + c.y) / 2;

        int Ax = a.x - midX;
        int Ay = a.y - midY;
        int bX = midX - Ay;
        int bY = midY + Ax;
        Point b = new Point(bX,bY);

        int cX =  (c.x - midX);
        int cY =  (c.y - midY);
        int dX = midX - cY;
        int dY = midY + cX;
        Point d = new Point(dX,dY);

        res[0] = b;
        res[1] = d;
        return res;
    }

Answer 3

Этот PDF содержит подробный алгоритм для того же.

Answer 4

Пусть d[i][j] = distances between points i and j.Нас интересует функция count(i, j), которая максимально быстро возвращает количество квадратов, которые мы можем нарисовать, используя точки i и j.

По сути, count(i, j) придется найти две точки x и y, такие что d[i][j] = d[x][y], и проверить, действительно ли эти 4 точки определяют квадрат.

Вы можете использовать хеш-таблица для решения проблемы в O(n^2) в среднем.Пусть H[x] = list of all points (p, q) that have d[p][q] = x.

Теперь для каждой пары точек (i, j), count(i, j) придется итерировать H[ d[i][j] ] и считать точки в этом списке, которые образуют квадрат с точками i и j.

На практике это должно работать очень быстро, и я не думаю, что когда-либо может быть хуже, чем O(n^3) (я даже не уверен, что это когда-нибудь может быть так плохо).

Answer 5

Для меня это выглядит как O (n ^ 3).Простой алгоритм может быть что-то вроде:

for each pair of points
    for each of 3 possible squares which might be formed from these two points
        test remaining points to see if they coincide with the other two vertices

Answer 6

Просто мысль: если вершина A является одним углом квадрата, то в других углах должны быть вершины B, C, D с AB = AD и AC = sqrt (2) AB и AC должны разделять BD. Предполагая, что каждая вершина имеет уникальные координаты, я думаю, что вы можете решить эту проблему в O (n ^ 2), включив хеш-таблицу (расстояние, угол).