Бинарный поиск в координатной сетке?

Question

[Egorian]

У меня есть поле состоящее из квадратов. И есть массив этих квадратов. Мне надо быстро находить нужный квадрат по его координатам.
Простой поиск является медленным и поэтому решил искать через бинарный.
Так выглядит функция поиска:

function binarsearchZones(array,position){
var high=array.length-1;
var low=0;
var allx=[];
var ally=[]; 
//находим все совпадающие х координаты с точкой
 while (low<=high){
    let  mid=Math.floor((low+high)/2);
    let guess=array[mid];
    if(guess.x==position.x) allx.push(guess.x)
   
    if(guess.x>position.x) high=mid-1
    else low=mid+1
  } 
//находим все совпадающие у координаты с точкой
var high=array.length-1;
var low=0;
while (low<=high){
    let  mid=Math.floor((low+high)/2);
    let guess=array[mid];
    if(guess.y==position.y) ally.push(guess.y)
    if(guess.y>position.y) high=mid-1
    else low=mid+1
  }
//костыльное сопоставление координат и нахождение этой точки
  var xindex=0;
  var yindex=0;
  while(true){
    if(allx[xindex]==position.x && ally[yindex]==position.y)return([allx[xindex],ally[yindex]])
    if(ally[yindex]!=position.y) if(ally[yindex+1]!=undefined) yindex+=1;
    if(allx[xindex]!=position.x) if(allx[xindex+1]!=undefined) xindex+=1;

  }
}

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

Answer 1

[dollar]

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

Если по заданным координатам может быть только 1 квадрат, то решение вообще элементарное и можно было самому догадаться.

P.S. Если координатная сетка большая, то всё то же самое, только используется промежуточная координатная сетка с более крупными ячейками.

Answer 2

[Сергей Соколов]

По координатам вычисляйте индекс квадрата. Что-то типа dlina_stroki * position.y + position.x
Это точно быстрее поиска, пусть и бинарного )

Если там действительно квадраты через единый шаг, то так должно получиться. Квадраты в массиве ведь упорядочены по колонкам, столбцам? Пример с реальными данными помог бы.

Допустим, там целочисленные координаты от 0 до 1800 с шагом 200. Поле 10x10 — массив длиной 100.

0,0      200,0    400,0    ... 1800,0
0,200    200,200  400,200  ... 1800,200
0,400    200,400  400,400  ... 1800,400
...
0,1800   200,1800 400,1800 ... 1800,1800

Интересует индекс элемента (400,200)

i = storona * y / shag + x / shag

Шаг у нас shag = 200 значит, искомый индекс 10 * 200 / 200 + 400 / 200 = 12