как эффективно найти прямоугольник @ некоторая точка х, у с iphone SDK

Question

Я ищу эффективный способ обработки изображений / кадров с помощью сенсорных методов. Допустим, я создаю клавиатуру или что-то подобное. У меня есть 'n' количество изображений, помещенных в пользовательский интерфейс. Когда кто-то касается алфавита (который является изображением), я могу сделать следующее, чтобы обнаружить соответствующую букву

1) CGRectIntersectsRect (.., ..): если я использую это, то мне нужно проверить каждую и каждую букву, чтобы выяснить, какая буква существует в этой точке касания (скажем, 100 100). Это становится O (n). Если я проведу пальцем по экрану, то получу m очков, и все соответствующее обнаружение изображения станет O (n * m), что нехорошо.

2) Другим способом является построение хеша для каждой & каждой позиции x, y, чтобы поиск был просто O (1). Но опять же это будет ограничение памяти, так как мне нужно хранить 300 * 300 (при условии, что я использую размер экрана 300 * 300). если я перетасовываю свои письма, то все нужно вычислять заново. Так что это не хорошо

Другими словами, мне нужна какая-то вещь, например, учитывая точку (x, y), мне нужен какой-то способ найти, какой прямоугольник эффективно покрывает эту точку.

Извините за длинный пост и любая помощь была бы благодарна.

Спасибо

Answer 1

Полезно, чтобы желаемые риты в качестве конечных целей были настроены как подпредставления в виде большего UIView (или подкласса), где вы ожидаете, что все эти связанные попадания произойдут. Например, если вы создаете свою собственную клавиатуру, вы можете добавить группу UIButton объектов в качестве подпредставлений и выполнить их проверку.

Итак, простой и традиционный способ тестирования множества подпредставлений - просто запустить код, когда кто-то нажимает на эти кнопки. Например, вы можете добавить подпредставления как UIControl объекты (которые являются подклассом UIView, который добавляет некоторые полезные методы для перехвата пользовательских событий касания) и вызвать addTarget:action:forControlEvents:, чтобы указать какой-либо метод, который должен запускаться, когда пользователь делает что-то в прямоугольнике этого UIControl. Например, вы можете поймать такие вещи, как UIControlEventTouchDown или UIControlEventTouchDragEnter. Вы можете прочитать полный список в справочнике по классу UIControl .

Теперь, звучит так, как будто вы идете к чему-то еще более индивидуальному. Если вы действительно хотите начать со случайной (x, y) координаты и знать, в каком именно прямоугольнике она находится, вы также можете использовать hitTest:withEvent: метод UIView. Этот метод берет точку в представлении и находит самое подробное (самое низкое в иерархии) подпредставление, которое содержит эту точку.

Если вы хотите использовать эти подпредставления исключительно для тестирования попаданий, а не для отображения, вы можете установить их цвет фона на [UIColor clearColor], но не скрывать их (т. Е. Установить свойство hidden на YES) , отключите взаимодействие с пользователем (через свойство userInteractionEnabled BOOL) или установите альфа ниже 0,1, поскольку любая из этих вещей заставит метод hitTest:withEvent: пропустить это подпредставление. Но вы все равно можете использовать невидимое подпредставление с этим вызовом метода, если оно соответствует этим критериям.

Answer 2

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

Answer 3

Посмотрите на свойство тега UIView. Если ваши изображения находятся в UIViews или подпредставлениях UIView, то вы можете установить каждый тег и использовать этот тег для поиска в массиве.

Если нет, то вы можете улучшить скорость, разделив массив прямоугольников на наборы, которые вписываются в большие прямоугольники. Сначала проверьте внешние прямоугольники, а затем внутренние прямоугольники. Для 25 прямоугольников понадобится всего 10 тестов, в худшем случае - 5 комплектов по 5 *. 1003 *

Answer 4

Спасибо Питу Киркхему и Тайлеру за ваши ответы, которые действительно полезны. Допустим, я не хочу использовать кнопки, так как я в основном отображаю изображения в виде маленьких прямоугольников. Чтобы проверить прямоугольник @ (x, y), я могу легко вызвать это, сделав мою сетку квадратом и найдя

gridcolumn = Math.floor (pos.x / cellwidth); gridrow = Math.floor (pos.y / cellheight);

Но моя проблема с касаниями. Допустим, я начал @ grid-1 и перетаскивал до grid-9 (в матрице 3 * 3), в этом случае я предполагаю, что получу 100-300 (x, y) позиций, поэтому каждый раз, когда мне нужно бежать выше формула для определения соответствующей сетки. Это приводит к 300 вычислениям, которые могут повлиять на производительность.

Итак, когда я отображаю изображение в виде прямоугольника, могу ли я связать некоторый идентификатор для этого изображения? так что я могу просто сохранить идентификаторы в списке (от сетки-1 до сетки-9), чтобы я мог избежать вышеуказанного расчета.

Спасибо за вашу помощь