Тест, если точка находится в некотором прямоугольнике
Это не может быть тем, что Вы ищете, но в интересах прибытия в проблему от другого угла....
эти два процесса Java, которые могли бы хотеть получить доступ к тому же файлу в том же приложении? Возможно, можно ли просто отфильтровать весь доступ к файлу через единственный, синхронизированный метод (или, еще лучше, с помощью JSR-166)? Тем путем можно управлять доступом к файлу, и возможно даже запросами доступа очереди.
5 ответов
Эта ветка Reddit решает вашу проблему:
Если ваша вселенная является целочисленной или если уровень точности хорошо известен и не слишком высок, вы можете использовать abelsson предложение из потока, используя поиск O (1) с использованием раскраски:
Как обычно, вы можете обменять место на время .. вот поиск O (1) с очень низкая константа. init: создать растровое изображение достаточно большой, чтобы охватить все прямоугольники с достаточной точностью инициализировать это к черному. Раскрашиваем все пиксели содержащий любой прямоугольник белого цвета. О (1) поиск: точка (x, y) белая? Если Итак, был поражен прямоугольник.
Я рекомендую вам перейти к этому сообщению и полностью прочитать ответ ModernRonin , который является наиболее принятым. Я вставил сюда:
Во-первых, микропроблема. У вас есть произвольно повернутый прямоугольник, а точка. Это точка внутри прямоугольник?
Есть много способов сделать это. Но я думаю, что лучше всего использовать 2d векторное произведение. Сначала убедитесь точки прямоугольника сохраняются по часовой стрелке. Затем сделайте вектор скрестное произведение с 1) вектором образованный двумя точками стороны и 2) вектор из первой точки стороны к контрольной точке. Проверьте знак результата - положительный внутри (справа) стороны, отрицательный снаружи. Если это внутри все четыре стороны, это внутри прямоугольник. Или, что то же самое, если это вне любой из сторон, это снаружи прямоугольник. Подробнее здесь .
Этот метод требует 3 вычитания на вектор * умножить на 2 вектора на сторону, плюс одно поперечное произведение с каждой стороны, это три умножения и два прибавления. 11 флопов на сторону, 44 флопа на прямоугольник.
Если вам не нравится векторное произведение, тогда вы можете сделать что-то вроде: выяснить вписанное и описанные круги для каждого прямоугольник, проверьте, есть ли точка внутри вписанный. Если да, то это в прямоугольник. Если нет, проверьте это за пределами ограниченного прямоугольник. Если да, то это за пределами прямоугольник. Если он попадает между два круга, ты трахаешься, а ты придется проверить это на собственном опыте.
Определение, находится ли точка внутри круга в 2d требуется два вычитания и два квадраты (= умножаются), а затем вы сравнить квадрат расстояния, чтобы избежать нужно делать квадратный корень. Это 4 флоп, умножить на два круга - 8 флоп - но иногда ты все равно не знаешь. Также предполагается, что вы не платите любое процессорное время для вычисления описанные или вписанные круги, что может или не может быть правдой в зависимости от от того, сколько предварительных вычислений вы готовы сделать с вашим прямоугольником.
В любом случае, это, вероятно, не отличная идея проверить точку против каждый прямоугольник, особенно если вы есть сто миллионов из них.
Что подводит нас к макро-проблеме. Как избежать проверки точки против каждый прямоугольник в наборе? В 2D, вероятно, это квад-дерево проблема. В 3D, что generic_handle сказал - октодерево. Сверху моего голову, я бы, вероятно, реализовал это как a B + дерево . Заманчиво использовать d = 5, так что каждый узел может иметь до 4 дети, раз уж это так красиво на абстракцию четырехугольного дерева. Но если набор прямоугольников слишком велик для помещается в основную память (маловероятно в наши дни), тогда имея узлы того же размера, что и дисковые блоки, вероятно путь.
Остерегайтесь надоедливых дегенератов случаев, как некоторый набор данных с десятью тысяча почти одинаковых прямоугольников с центрами в одной и той же точке. : P
Почему эта проблема важна? Это полезно в компьютерной графике, чтобы проверить если луч пересекает многоугольник. Т.е., Эта снайперская винтовка стреляла в тебя только что ударил человека, в которого стреляли в? Он также используется на карте в реальном времени. софт, вроде говорят GPS-устройства. GPS сообщает вам координаты, в которых вы находитесь, но программное обеспечение карты должно найти, где эта точка находится на огромном количестве карты данных, и сделайте это несколько раз за второй.
Опять же, кредит ModernRonin ...
Я предлагаю вам взглянуть на BSP-деревья (и возможные квадродеревья или октодеревья, ссылки также доступны на этой странице). Они используются для рекурсивного разбиения всего пространства и позволяют вам быстро проверить, какие прямоугольники вам нужно проверить вообще.
Как минимум, у вас есть только один огромный раздел, и вам нужно проверить все прямоугольники, максимум ваши разделы получат настолько малы, что достигают размеров отдельных прямоугольников. Конечно, чем более детализировано разделение, тем дольше вам нужно идти вниз по дереву, чтобы найти прямоугольники, которые вы хотите проверить.
Однако вы можете свободно решать, сколько прямоугольников подходит для проверки на точку а затем создайте соответствующую структуру.
Однако обратите внимание на перекрывающиеся прямоугольники. Поскольку дерево BSP в любом случае необходимо предварительно вычислить,
Для прямоугольников, которые выровнены по осям, вам нужны только две точки (четыре числа) для идентификации прямоугольника - обычно нижний левый и верхний правый углы. Чтобы установить, перекрывается ли данная точка (X тест , Y тест ) с прямоугольником (X BL , Y BL , X TR , Y TR ) путем тестирования обоих:
- X test > = X BL && X test <= X TR
- Y тест > = Y BL && Y тест <= Y TR
Очевидно, для достаточно большой набор точек для тестирования, это может занять довольно много времени. Тогда возникает вопрос, как оптимизировать тестирование.
Ясно, что одна оптимизация состоит в том, чтобы установить минимальные и максимальные значения X и Y для прямоугольника, окружающего все прямоугольники (ограничивающий прямоугольник): быстрый тест показывает, есть ли необходимость в дальнейшем поиске.
- X test > = X min && X test <= X max
- Y test > = Y min && Y тест <= Y max
В зависимости от того, какая часть общей площади покрыта прямоугольниками, вы можете найти неперекрывающиеся подобласти, содержащие прямоугольники, и вы затем можно избежать поиска в тех подобластях, которые не могут содержать прямоугольник, перекрывающий точку, снова сохраняя сравнения во время поиска за счет предварительного вычисления подходящих структур данных. Если набор прямоугольников достаточно разрежен, перекрытия может не быть, и в этом случае это перерастает в поиск методом грубой силы. Точно так же, если набор прямоугольников настолько плотный, что в ограничивающей рамке нет поддиапазонов, которые можно разделить без разрыва прямоугольников.
Однако вы также можете произвольно разбить ограничивающую область, скажем, на четверти ( по половине в каждую сторону). Затем вы должны использовать список блоков, который будет включать больше блоков, чем в исходном наборе (два или четыре блока для каждого блока, который перекрывает одну из произвольных границ). Преимущество этого состоит в том, что вы затем можете исключить три из четырех четвертей из поиска, уменьшая общий объем поиска, который должен быть выполнен в целом - за счет вспомогательного хранилища.
Итак, есть пространственно-временные компромиссы. , как всегда. И предварительные вычисления по сравнению с поиском компромиссов. Если тебе не повезло, предварительное вычисление ничего не дает (например, есть только два блока, и они не перекрываются ни по одной из осей). С другой стороны, это может значительно сократить время поиска.
Почему бы не попробовать это. Это кажется довольно легким как для вычислений, так и для памяти.
Рассмотрите проекции всех прямоугольников на базовую линию вашего пространства. Обозначьте этот набор межстрочных интервалов как
{[Rl1, Rr1], [Rl2, Rr2],..., [Rln, Rrn]}, ordered by increasing left coordinates.
. Теперь предположим, что ваша точка - это (x, y), начните поиск слева от этого набора, пока не дойдете до интервала строки, который содержит точку x.
Если нет, то ваша точка (x, y) находится вне всех прямоугольников.
Если есть, скажем [Rlk, Rrk], ..., [Rlh, Rrh], (k <= h), тогда просто проверьте, находится ли y в пределах вертикального размера любого из этих прямоугольников.
Готово.
Удачи.
Джон Донер
Ваш подход с R-деревом - лучший из известных мне подходов (это подход, который я бы предпочел квадродеревьям, деревьям B + или деревьям BSP, поскольку R-деревья кажутся удобными для построения в вашем случае. ). Предостережение: я не эксперт, хотя я помню кое-что из своего студенческого курса алгоритмики!