Как проверить, эффективно ли прямоугольные образуют декартовы координаты?

Ситуация выглядит следующим образом:

  • Есть N массивов.
  • В каждом массиве (0..N-1) хранятся (x,y) кортежи (декартовы координаты)
  • Длина каждого массива может быть разной

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

Пример:

findRectangles({
    {*(1,1), (3,5), (6,9)}, 
    {(9,4), *(2,2), (5,5)}, 
    {(5,1)},
    {*(1,2), (3,6)}, 
    {*(2,1), (3,3)}
})

дает следующее:

[(1,1),(1,2),(2,1),(2,2)],
..., 
...(other solutions)...

Никакие две точки не могут прийти из одного набора.

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

Источник

2 ответа

Решение

Пусть XY будет вашим набором массивов. Создайте два новых набора X и Y, где X равен XY со всеми массивами, отсортированными по x-координате, а Y равен XY со всеми массивами, отсортированными по y-координате.

  • Для каждой точки (x0,y0) в любом из массивов в X: найдите каждую точку (x0,y1) с той же x-координатой и другой y-координатой в остальных массивах из X
  • Для каждой такой пары точек (если она существует): найдите Y для точек (x1,y0) и (x1,y1)

Пусть C будет размером самого большого массива. Тогда сортировка всех наборов занимает время O(N*C*log(C)). На шаге 1 для поиска единственной точки совпадения требуется время O(N*log(C)), поскольку все массивы в X отсортированы. Поиск всех таких точек находится в O(C*N), так как в целом существует не более C * N баллов. Шаг 2 занимает время O(N*log(C)), так как Y отсортирован.

Следовательно, общее асимптотическое время выполнения находится в O(C * N^2 * log(C)^2).

Для C==10 и N==18 вы получите примерно 10.000 операций. Умножьте это на 2, так как я опустил этот коэффициент из-за обозначения Big-O.

Решение имеет еще одно преимущество: оно чрезвычайно просто в реализации. Все, что вам нужно, это массивы, сортировка и бинарный поиск, первые два из которых, скорее всего, уже встроены в язык, а бинарный поиск чрезвычайно прост.

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

Источник

Вы можете использовать хеширование с большим эффектом:

hash each point (keeping track of which list it is in)
for each pair of points (a,b) and (c,d):
    if (a,d) exists in another list, and (c,b) exists in yet another list:
        yield rectangle(...)

Когда я сказал existsЯ имею в виду сделать что-то вроде:

hashesToPoints = {}
for p in points:
    hashesToPoints.setdefault(hash(p),set()).add(p)
for p1 in points:
    for p2 in points:
        p3,p4 = mixCoordinates(p1,p2)
        if p3 in hashesToPoints[hash(p3)] and {{p3 doesn't share a bin with p1,p2}}:
            if p4 in hashesToPoints[hash(p4)] and {{p4 doesn't share a bin with p1,p2,p3}}:
                yield Rectangle(p1,p2)

Это O(#bins^2 * items_per_bin^2)~30000, что очень быстро в вашем случае с 18 массивами и 10 items_per_bin - намного лучше, чем внешний подход к продукту, который... намного хуже с O(items_per_bin^#bins)~3trillion. знак равно

второстепенный знак:

Вы можете уменьшить как основание, так и показатель степени в своих вычислениях, сделав несколько проходов "сокращения". например

remove each point that is not corectilinear with another point in the X or Y direction
then maybe remove each point that is not corectilinear with 2 other points, in both X and Y direction

Вы можете сделать это, отсортировав по X-координате, повторите для Y-координаты, в O(P log(P)) время с точки зрения количества очков. Вы можете сделать это одновременно с хешированием. Если плохой парень организует ваш вклад, он может заставить эту оптимизацию вообще не работать. Но в зависимости от вашего дистрибутива вы можете увидеть значительное ускорение.

Источник
Другие вопросы по тегам