Проверка числа на принадлежность диапазону

Приветствую.



Дано:

- координаты ячейки (или точки) X,Y;

- массив диапазонов в виде (X1,X2,Y1,Y2);



Нужно определить, принадлежит ли ячейка одному из них, то есть (X1 <= X <= X2) and (Y1 <= Y <= Y2).



X,Y занимают по 2 байта, соответственно элемент массива — 8.



Вопрос 1й: можно ли как-то определить, верно ли равенство X1 <= X <= X2, если есть R = (X1 << 16) + X2?



Вопрос 2й: как оптимизировать то, что вышло с нахрапа:

Код (Text):

1.  
2.     mov     edx,X
3.     mov     eax,Y
4.    
5.     push    ecx ; количество элементов массива
6.     xor     edi,edi
7.     dec     edi
8. @@:
9.     inc     edi
10.     cmp     edi,[esp]
11.     jе     @F
12.     mov     ecx,[esi+edi*8]     ; ecx = |х1,х2|
13.     ; compare х >= х1
14.     cmp     dx,cx
15.     jb      @В
16.     shr     ecx,16
17.     ; compare х <= х2
18.     cmp     edx,ecx
19.     ja      @В
20.     mov     ecx,[esi+edi*8+4]   ; ecx = |у1,у2|
21.     ; compare у >= у1
22.     cmp     ax,cx
23.     jb      @В
24.     shr     ecx,16
25.     ; compare у <= у2
26.     cmp     eax,ecx
27.     ja      @В
28. @@:
29.     pop     eax
30.     sub     eax,edi
31.     ; еах - 0, если не найдено
32.  

 

Для положительных чисел можно обойтись без сдвига:

edx=(X+1)<<16+X

ecx=(X1<<16)+X2



cmp ecx,edx



если X1<=X<=X2, тогда X+1>X1 и в результате сравнения будет установлен флаг переноса(переноса из младших 16 разрядов нет)

если X<X1<=X2, тогда флаг переноса установлен не будет

если X>X2, то этот вариант отсекается второй проверкой (сравнением X и X2)



Данный метод не работает когда X=0FFFFh

 

Спасибо!



Значит, не зря диапазоны так выстроены. 0хFFFF вряд ли будет, слишком уж большое число, хотя теоретически возможно.

 

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

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



Если прямоугольников много, и они сильно пересекаются, то возможно, что более быстрым методом будет нахождение контура(контуров) покрываемой ими области(областей), и обход его с вычислением угла, который мы опишем вокруг точки: 0 - точка снаружи, 2Pi - точка внутри (алгоритм не помню).



Ну и вот метод который может ускорить вычисления при большом количестве прямоугольников, за счёт дополнительного расхода памяти:



Заводим 4 массива со структурами, содержащими значения одной из границ (X1, X2, Y1 или Y2) и идентификатор прямоугольника которому принадлежит эта граница. Массивы должны быть упорядоченны по значению границы. Получив (X,Y), двоичным поиском находим в каждом массиве, где начинаются прямоугольники в которые может попасть данная точка. Затем выбираем массив, в котором меньше всего таких прямоугольников и просто проверяем для каждого из них три оставшиеся границы.

 

Вообще, ячейки — это ячейки таблицы, диапазоны ячеек — объединённые ячейки. Соответственно, диапазоны пересекаться не могут.



Практически, объединённых ячеек не много. Ячейки обрабатываются последовательно, думаю, логично будет сдвигать указатель на диапазоны по мере нахождения соответствий (когда X > Ranges[0].X1).

 

IceStudent

> "0хFFFF вряд ли будет, слишком уж большое число, хотя теоретически возможно"

Нехилая табличка

Если числа не более 0х7FFF (тоже не маленькое число то можно без лишних переходов обойтись - использовать 16-й и 32-й биты как индикаторы переноса (правда предварительная подготовка XY усложняется, зато сравнение с Ranges быстро делается). Для X,Y < 0хFFFF можно без переходов сделать на MMX

 

Условие типа
if (X>=X1)and(Y>=Y1)and(X<=X2)and(Y<=Y2) then
можно и так проверить

Код (Text):

1. mask dd 00000000h,00000000h,80000000h,80000000h
2. .........
3. cvtpi2ps   xmm0,[XY]
4. shufps      xmm0,xmm0,01000100b
5. xorps       xmm0,dqword[mask]
6. cmpnltps   xmm0,[X1Y1X2Y2] ; X1,Y1,-X2,-Y2
7. movmskps eax,xmm0
8. cmp         al,15
9. je @true

а если без SSE, то так

Код (Text):

1. mov eax,[X]
2. mov edx,eax
3. sub  eax,[X1]
4. sub  edx,[X2]
5. xor  eax,edx
6. mov ecx,[Y]
7. mov edx,ecx
8. sub  ecx,[Y1]
9. sub  edx,[Y2]
10. xor  ecx,edx
11. test ecx,eax
12. jl @true

 

murder

Поправочка: при использовании sub\sub\xor нужно, чтобы одна из границ не принадлежала диапазону, поэтому для проверки X1 <= X <= X2 перед вычитанием нужно добавить inc eax или dec edx