Считать точки в прямоугольнике

Ответ 1

Представьте точки как k-d tree.

Затем выполните запрос:

• Текущий node= корень

• Текущая область = область текущего node (можно отслеживать/рассчитывать по мере рекурсии вниз по дереву)

• Если текущая область полностью содержится внутри прямоугольника, добавьте количество точек, которые этот node имеет в качестве детей (+1 для текущего node).

• Если текущая область полностью находится внутри прямоугольника, ничего не делайте.

• Если текущая область частично содержится внутри прямоугольника:

  • Добавьте текущую точку node, если она содержится в прямоугольнике.
  • Повторите с 2. для обоих детей.

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

Ответ 2

Старый ответ (если вы не можете предварительно запрограммировать точки заранее):

• Вставьте прямоугольник в содержащий прямоугольник со сторонами/ребрами, ориентированными как ось xy
• Быстро исключить все точки за его пределами.
• Используйте описанный здесь принцип: Как определить, находится ли точка в двумерном треугольнике? с четырьмя сторонами/краями прямоугольника ( Примечание:, поскольку вы всегда используете один и тот же прямоугольник для проверки всех точек, вы можете предварительно вычислить некоторые из значений)

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

Новый ответ:

• rect - наш прямоугольник ввода
• Предположим, что у вас есть f1(point,rect), который проверяет, находится ли точка внутри прямоугольника. Вы можете использовать тот, который я упомянул выше.
• Предположим, что у вас есть f2(shape,rect), который может сказать, что форма полностью содержится в rect, или rect полностью содержится в форме, или что форма и прямоугольник пересекаются или вообще не пересекаются Форма
• будет многоугольником с определенным числом сторон (не высоким или пропорциональным n, так что мы можем предположить, что f2 является O(1)), или область в 2D плоскости, ограниченная двумя сторонами и расширяющаяся до бесконечности (например, область, ограниченная положительным сечением оси xy)
• Предположим, у вас есть много времени, чтобы предварительно обработать точки, но не бесконечно. Пусть говорят, что мы можем предоставить алгоритм O (n * log (n))

То, что мы хотим получить, - это алгоритм, который во время выполнения называет f1 и f2 минимальным количеством времени. Например, что-то пропорциональное (того же порядка) log(n)

Итак, мы хотим разделить нашу 2D-плоскость на формы m, каждая из которых содержит p точек. Во время выполнения мы проверяем каждую фигуру с помощью f2, и у нас может быть 4 случая:

• Прямоугольник полностью содержится в форме: используя f1, я считаю все точки, содержащиеся в этой форме, которые лежат в прямоугольнике (O(p) ), и я заканчиваю.
• Форма полностью содержится в прямоугольник: я добавляю в свой аккумулятор все количество точек содержащихся в форме. (O(1) )
• Прямоугольник и форма не пересекаются: я пропускаю эту форму.
• Прямоугольник и форма пересекаются: используя f1. Я подсчитываю все точки, содержащиеся в этой форме, которые лежат в прямоугольник (O(p) ), и я продолжаю.

Нам может повезти и быстро упасть в случае 1, но обычно нам нужно будет проверить все фигуры, и по крайней мере для одного из них нам нужно будет проверить все содержащиеся в нем пункты. Таким образом, этот алгоритм будет O(p) + O(m). Учитывая, что p * m = n, если мы выбрали p = m = sqrt(n), получим O(sqrt(n) ), что является лучшим, которое мы можем получить с помощью этого метода. ( Примечание: сколько раз мы выполняем f1? Это число фактически зависит от формы прямоугольника, поэтому, если, например, прямоугольник очень удлинен, он будет пересекаться со многими регионами, вызывая много вызовов f1. Однако я думаю, что мы можем предположить, что меры прямоугольника не находятся в одном порядке n, или sqrt(n) или даже log(n): n огромен.)

Мы могли бы улучшить здесь; мы могли бы, например, сказать, что у нас есть смежности между фигурами, и в первый раз, когда я нахожу перекрытие между формой и прямоугольником, я проверяю только непрерывные фигуры. Однако среднее число фигур, которые нам нужно будет проверять, будет в любом случае около p/2 и O(p/2) = (O(p) ). Так что нет эффективного выигрыша.

Реальный выигрыш заключается в том, что мы помещаем некоторую иерархию в фигуры.

Прежде всего, я проверю все свои очки и найду свои граничные значения max_x, max_y, min_x, min_y. (Предположим, что эти границы → n. Если бы мы могли иметь приоритеты в отношении точечного распределения, оптимизация, на которую мы могли бы нацелиться, была бы совершенно иной) Мы разделяем наше пространство по формам, каждый из которых содержит (вокруг) log (n) точек. Начнем с деления 2D-плоскости на 4 формы, используя ось xy (я мог бы также центрироваться в соответствии с моими связанными значениями). Это будет наш первый уровень нашей перевернутой пирамиды. Циклично: для каждой области, содержащей больше, чем log (n) точек, мы разбиваем область пополам, используя вертикальную или горизонтальную линию (мы чередуем). Если одна граница была установлена ​​бесконечной, то для разбиения пополам я использую соответствующее значение границы. Каждая из разделенных областей содержит указатель на регионы, в которых он разделен. Новые регионы - второй уровень пирамиды. Я продолжаю делиться, пока все мои регионы не содержат (около) log (n) точек. Когда регион разделен, он содержит указатель на "дочерние" регионы. Я построил свою пирамиду. Верхний уровень перевернутой пирамиды содержит n/log (n) фигуры, которые довольно большие, но это не имеет значения: все имеет в виду, что мы имеем уровни log (n) пирамиды. Примечание. Для каждой фигуры на каждом уровне мы знаем, сколько очков она содержит. Примечание2: эта предварительная разработка анализирует в среднем каждую точку за один раз за уровень пирамиды, поэтому ее сложность равна O (n * (log (n)).

Когда я получаю свой прямоугольник во входных данных, я использую f2 для проверки фигур на моем первом уровне.

• Прямоугольник полностью содержится в форме: я вводил формы детей этой области, если они есть, в противном случае я использую f1 для подсчета точек внутри прямоугольника (O(log(n))). Я отбрасываю любую другую фигуру.
• Форма полностью содержится в прямоугольнике: я добавляю к моему аккумулятору все количество точек, содержащихся в фигуре. Принимает O(1)
• Прямоугольник и форма не пересекаются: я пропускаю эту форму.
• Прямоугольник и форма пересекаются: я ввожу формы детей этой области, если они есть, в противном случае я использую f1 для подсчета точек внутри прямоугольника (O(log(n) ).

Теперь сложная часть: сколько форм мы посещаем? Опять же, это зависит от формы прямоугольника, от количества фигур, к которым он прикасается. Однако для каждого уровня мы будем посещать ряд фигур, не зависящих от n, поэтому количество посещенных форм пропорционально O(log(n) ).

Так как n очень велико, мы можем предположить, что число фигур, пересекаемых сторонами прямоугольника (которые вызывают дорогой вызов f1), намного меньше, чем O(log(n) ). Весь алгоритм должен быть O(log(n) ).

Есть еще один способ оптимизации, но что-то останется в среднем O(log(n) )

Заключительное примечание. То, как мы делим пространство, должно быть таким, чтобы контролировать количество сторон, которыми обладает многоугольник, потому что, если формы могут иметь большое количество сторон, как-то зависящее от количества точек (согласно функции что мы называем g), f2 будет O(g(n) ), и его сложность нужно будет снова умножить на что-то, зависящее от n, количество фигур, которые мы должны проверить, поэтому, вероятно, не хорошо.

Ответ 3

Что вам нужно - это какая-то структура данных разбиения двоичных пространств. Это даст вам список кандидатов, для которых вы можете выполнить настоящий тест "точка в полигоне".

Я бы посоветовал вам убедиться, что это то, что вы действительно должны кодировать самостоятельно. Например, у многих БД есть такая функциональность. Являются ли ваши данные на самом деле в БД? Не могли бы? (нет смысла изобретать колеса...)

Вы можете увидеть отличный ответ для проблемы Point in Polygon: Как определить, находится ли 2D-точка внутри многоугольника?

Ответ 4

Я бы предложил найти преобразование вращения + сдвиг, которое вы можете применить к своему пространству, так что один угол прямоугольника находится в (0,0), а два края идут по осям x и y.

Теперь вы просматриваете точки, применяете одно и то же преобразование и просто проверяете 0 < x < rectangle_max_x и 0 < y < rectangle_max_y.

Ответ 5

Сделайте треугольник. Предположим, abcd - это прямоугольник, а x - точка, тогда если area(abx)+area(bcx)+area(cdx)+area(dax) equals area(abcd), то точка внутри него.

Ответ 6

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

Это самый простой способ и не нужно использовать сложную структуру данных

Ответ 7

Если скорость является проблемой, а память/дисковое пространство - нет, подумайте о том, чтобы сделать следующее, что должно быть наиболее эффективным методом.

Таким образом, вы можете выполнить некоторые очень быстрые тесты до того, как когда-либо сделаете какую-либо значительную математику:

public class DataPoint
{
    double X, Y;
    ...
}
public bool IsInBoundingBox(Point p1, Point p2, Point p3, Point p4)
{
    // assume p1, p2, p3, p4 to be sorted
    return (X>p1.X && X<p3.X && Y>p4.Y && Y<p2.Y);
}

Тогда порядок выполнения работы должен быть таким...

// sort points of QueryRectangle: p1 is left-most, p2 is top-most, p3 is right-
// most, and p4 to be bottom-most; if there is a tie for left-most, p1 should
// be the bottom-left corner, p2 the top-left corner, p3 the top-right corner,
// and p4 the bottom-right corner

// See if the QueryRectangle in question is aligned with the grid; if it is,
// then the set of DataPoints that lie within the BoundingBox are within the
// QueryRectangle and no further calculation is needed

if (p1.X == p2.X || p1.X == p3.X || p1.X == p4.X) 
{
    // is orthogonal (aligned with axes)
    foreach(DataPoint dp in listDataPoints)
        if(dp.IsInBoundingBox())
        {
            // dp is in QueryRectangle; perform work
        }
}
else
{   
    foreach(DataPoint dp in listDataPoints)
        if(dp.IsInBoundingBox())
        {
            // perform further testing to see if dp is in QueryRectangle
        }
}

В качестве альтернативы, если вы хотите пойти с решением поворота/перевода, как предлагает viraptor...

// sort points of QueryRectangle: p1 is left-most, p2 is top-most, p3 is right-
// most, and p4 to be bottom-most; if there is a tie for left-most, p1 should
// be the bottom-left corner, p2 the top-left corner, p3 the top-right corner,
// and p4 the bottom-right corner

public class DataPointList : List<DataPoint>
{
    public List<DataPoint> GetPointsInRectangle(Point p1, Point p2, Point p3, Point p4)
    {
        List<DataPoint> tempListDataPoints = new List<DataPoint>();
        foreach(DataPoint dp in this)
            if(dp.IsInBoundingBox()) tempListDataPoints.Add(dp);

        if (!(p1.X == p2.X || p1.X == p3.X || p1.X == p4.X))
        {
            // needs transformation
            tempListDataPoints.TranslateAll(-1 * p1.X, -1 * p1.Y);
            tempListDataPoints.RotateAll(/* someAngle derived from the arctan of p1 and p2 */);
            // Note: you should be rotating counter-clockwise by some angle >0 but <90

            // the new p1 will be 0,0, but p2, p3, and p4 all need to undergo the same transformations
            // transP1 = new Point(0,0);
            // transP2 = new Point(p2.Translate(-1 * p1.X, -1 * p1.Y).Rotate(/* someAngle derived from the arctan of p1 and p2 */));
            // transP3 = ...; transP4 = ...;

            foreach(DataPoint dp in tempListDataPoints)
                if (!(dp.X>transP1.X && dp.X<transP3.X && dp.Y>transP1.Y && dp.Y<transP3.Y)) tempListDataPoints.Remove(dp);
        }
        else
        {
            // QueryRectangle is aligned with axes, all points in bounding box
            // lie within the QueryRectangle, no need for transformation or any
            // further calculation

            // no code needs to go here, but you may want to keep it around for notes
        }

        return tempListDataPoints;
    }
}

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

Отказ от ответственности: у меня было 2 часа сна прошлой ночью, поэтому я не буду исправлять. Возможно, вам придется выполнить некоторые незначительные исправления. Или крупные. Кто знает.:)

Ответ 8

Упрощение, которое вы можете решить для решения своей проблемы, - это найти минимальный прямоугольник (S), ориентированный по оси, содержащий один заданный (R). Используйте некоторую пространственную древовидную структуру в качестве дерева k-d, чтобы найти подмножество точек, содержащихся внутри S, и, наконец, выберите для этого подмножества точки, находящиеся внутри R.

Этот подход будет проще реализовать, чем тот, который предлагается @Dukelin, где поиск дерева k-d выполняется непосредственно с использованием R.

Ответ 9

Я бы начал с предварительного сортировки массива точек по любой оси (пусть это будет x). Затем бинарный поиск его для точек с x-проекцией в x-проекции прямоугольных прямоугольников. Это позволит уменьшить количество очков, чтобы проверить их резко.

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

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

Для прямой матрицы преобразования

A D a
B E b
C F c

решение будет:

d = 1/(AE − BD)

A' = Ed
B' = −Bd
C' = (BF − EC)d

D' = −Dd
E' = Ad
F' = (DC − AF)d

a' = b' = 0
c' = 1

Затем, применяя обратное преобразование к каждой точке, мы либо переведем его в особый куб, который равен (0, 1)x(0, 1), если он изначально лежит в прямоугольнике, либо нет, если он этого не делает.

UPD: Или вместо всего материала преобразования вы можете сделать следующее:

Пусть точки прямоугольника P1..P4 и точка для проверки A.

Для i = 1..4 вычислите PAi как Pi - A

Теперь кросс-произведение (Pi.x, Pi.y, 0)x(Pj.x, Pj.y, 0) будет измерять треугольник, созданный A и соответствующим краем прямоугольников. И, поскольку исходная точка находится на плоскости xy, результат будет похож на (0, 0, Sij), где Sij - это подписанный квадрат треугольника. Просто вычислите сумму:

|(P1.x, P1.y, 0)x(P2.x, P2.y, 0)[3]|+
|(P2.x, P2.y, 0)x(P3.x, P3.y, 0)[3]|+
|(P3.x, P3.y, 0)x(P4.x, P4.y, 0)[3]|+
|(P4.x, P4.y, 0)x(P1.x, P1.y, 0)[3]|

И сравните его с квадратом прямоугольников. Если оно более или менее равно, то точка находится в прямоугольнике. Будет небольшая вычислительная ошибка, поэтому точное равенство не может быть и речи.