Перебор тайлов методом короеда :)

[vdemidov]

Желающим помочь в разработке. Нужно написать класс итератор тайлов, который будет перебирать тайлы в заданном прямоугольнике по расширяющейся спирали от заданного начального тайла.
Пример.
Задан прямоугольник ((0,0),(2,2)) и начальный тайл (1,1).
Итератор должен выдать примерно такую последовательность:
(1,1);(1,0);(2,0);(2,1);(2,2);(1,2);(0,2);(0,1);(0,0);
Класс должен быть наследником класса
TTileIteratorAbstract = class
protected
FTilesTotal: Int64;
FTilesRect: TRect;
public
function Next(out ATile: TPoint): Boolean; virtual; abstract;
procedure Reset; virtual; abstract;
property TilesTotal: Int64 read FTilesTotal;
property TilesRect: TRect read FTilesRect;
end;

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

[DJ VK]

может иметь место несовпадения центра области перебора и начальной точки (например область (0-0 3-3) и центр (1-1) ?
просто тогда спираль получается с разрывами на последнем витке.
А если точка вообще с краю, то там еще сложнее искать.

[vdemidov]

может иметь место несовпадения центра области перебора и начальной точки (например область (0-0 3-3) и центр (1-1) ?

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

[DJ VK]

Итак. код. Переделать на дельфи (хотя дельфи и Cpp классы умеет читать) и воткнуть в класс (в данном примере все лежит в классе формы).

Объявление переменных и методов

Код: Выделить всё

  int CurrentRadius;
  bool Ended;
  int MaxRadius;
  int DPhase;
  TRect FTilesRect;
  TPoint P,P0,Psum;
  __int64 FTilesTotal;

  void __fastcall CreateNew(TPoint* PP,TRect* Rec);
  void __fastcall Reset(void);
  bool __fastcall CheckPoint(TPoint* P0,TPoint* PP,TRect* Rec);
  int __fastcall GetMaxRad(TPoint* PP,TRect* Rec);
  bool __fastcall Next(TPoint* P);


Создание нового задания

Код: Выделить всё

//---------------------------------------------------------------------------
void __fastcall TForm1::CreateNew(TPoint* PP,TRect* Rec)
{
  //вызывать в конструкторе
  P=Point(PP->x,PP->y);
  P0=Point(0,0);
  FTilesRect=Rect(Rec->Left,Rec->Top,Rec->Right,Rec->Bottom);
  MaxRadius=GetMaxRad(&P,&FTilesRect);
  Ended=false;
  DPhase=0;
  CurrentRadius=1;
  FTilesTotal=0;
}

Сброс

Код: Выделить всё

//---------------------------------------------------------------------------
void __fastcall TForm1::Reset(void)
{
  P0=Point(0,0);
  Ended=false;
  DPhase=0;
  CurrentRadius=1;
  FTilesTotal=0;
}

Получение максимального радиуса спирали

Код: Выделить всё

//---------------------------------------------------------------------------
int __fastcall TForm1::GetMaxRad(TPoint* PP,TRect* Rec)
{
  int Rad=Rec->Right-PP->x;
  if((PP->x-Rec->Left)>Rad) Rad=PP->x-Rec->Left;
  if((Rec->Top-PP->y)>Rad) Rad=Rec->Top-PP->y;
  if((PP->y-Rec->Bottom)>Rad) Rad=PP->y-Rec->Bottom;
  return Rad;
}

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

Код: Выделить всё

//---------------------------------------------------------------------------
bool __fastcall TForm1::CheckPoint(TPoint* P0,TPoint* PP,TRect* Rec)
{
  bool Res=false;
  Psum.x=PP->x+P0->x;
  Psum.y=PP->y+P0->y;
  if((Psum.x>=Rec->Left)&&(Psum.x<=Rec->Right))
    if((Psum.y>=Rec->Bottom)&&(Psum.y<=Rec->Top))
      Res=true;
  return Res;
}

Выдача точки с одновременным поиском следующей.

Код: Выделить всё

//---------------------------------------------------------------------------
bool __fastcall TForm1::Next(TPoint* PP)
{
  if(Ended) return false;
  PP->x=P0.x+P.x;
  PP->y=P0.y+P.y;
  bool Found=false;
  FTilesTotal++;
  while(CurrentRadius<=MaxRadius && !Found)
  {
    if(DPhase==0 && !Found)
    {
      if(P0.y==CurrentRadius)
      {
        DPhase=1;
      }
      if(P0.y<CurrentRadius)
      {
        P0.y++;
        Found=CheckPoint(&P0,&P,&FTilesRect);
        if(Found) return true;
      }
    }
    if(DPhase==1)
    {
      if(P0.x==CurrentRadius)
      {
        DPhase=2;
      }
      if(P0.x<CurrentRadius)
      {
        P0.x++;
        Found=CheckPoint(&P0,&P,&FTilesRect);
        if(Found) return true;
      }
    }
    if(DPhase==2)
    {
      if(P0.y==-CurrentRadius) DPhase=3;
      if(P0.y>-CurrentRadius)
      {
        P0.y--;
        Found=CheckPoint(&P0,&P,&FTilesRect);
        if(Found) return true;
      }
    }
    if(DPhase==3 && !Found)
    {
      if(P0.x==-CurrentRadius)
      {
          DPhase=0;
          CurrentRadius++;
          if(CurrentRadius>MaxRadius) Ended=true;
      }
      else
      if(P0.x>-CurrentRadius)
      {
        P0.x--;
        Found=CheckPoint(&P0,&P,&FTilesRect);
        if(Found) return true;
      }
    }
  }
  return true;
}

Пример вызова

Код: Выделить всё

void __fastcall TForm1::Button1Click(TObject *Sender)
{
  Memo1->Lines->Clear();

  TPoint GetPoint=Point(Edit5->Text.ToInt(),Edit6->Text.ToInt()); //X,Y
  TRect GetRect=Rect(Edit3->Text.ToInt(),Edit1->Text.ToInt(),Edit4->Text.ToInt(),Edit2->Text.ToInt()); //L,T,R,B
  CreateNew(&GetPoint,&GetRect);

  TPoint CurrentP;
  bool Res=true;
  while(Res)
  {
    Res=Next(&CurrentP);
    if(Res)
    Memo1->Lines->Add(IntToStr(CurrentP.x)+","+IntToStr(CurrentP.y));
  }
}

[DJ VK]

Не решена 1 задача - когда начальная точка за пределами прямоугольника.
Можно сделать например вот такую проверку при инициализации

Код: Выделить всё

//---------------------------------------------------------------------------
bool __fastcall TForm1::CreateNew(TPoint* PP,TRect* Rec)
{
  P=Point(PP->x,PP->y);
  P0=Point(0,0);
  FTilesRect=Rect(Rec->Left,Rec->Top,Rec->Right,Rec->Bottom);

  if(!CheckPoint(&P0,&P,&FTilesRect)) return false;

  MaxRadius=GetMaxRad(&P,&FTilesRect);
  Ended=false;
  DPhase=0;
  CurrentRadius=1;
  FTilesTotal=0;
  return true;
}

и в случае false выдавать ошибку. или например сбрасывать начальную точку в угол или середину.

[vdemidov]

Порядок вызова неправильный. Должен быть такой:

Код: Выделить всё

  while(Next(&CurrentP))
  {
    Memo1->Lines->Add(IntToStr(CurrentP.x)+","+IntToStr(CurrentP.y));
  }


Тоесть даже для получения первой точки вызывается Next.

Не решена 1 задача - когда начальная точка за пределами прямоугольника.

Желательно бы поправить.
И желательно бы сделать таки отдельным классом даже на C, что бы не смешивать код формы и код класса, а мне не думать что делать с результатом функции CreateNew, которая вызывается в конструкторе, который не желательно завершать ексепшеном.

[DJ VK]

Щас делов много. так что как со временем будет, так и понемногу класс создам....

Тоесть даже для получения первой точки вызывается Next.

.
Так у меня он так и вызывается. Просто конструкция другая.... на 2 строки кода длиннее..

[vdemidov]

Щас делов много. так что как со временем будет, так и понемногу класс создам....

Так а я никуда не спешу.

Так у меня он так и вызывается. Просто конструкция другая.... на 2 строки кода длиннее..

А ну да. Перемудрили. Но проблема с начальной точкой все еще остается.

[DJ VK]

Уфф. Решил добить класс. готово.
оптимизировал алгоритм, чтобы свернуть фазу (направление движения) в единый цикл. думаю лишнее умножение на +\-1 ресурсов не ест.
Сделал перепоиск первой точки если она за диапазоном.

примерно это вот так выглядит

Код: Выделить всё

//---------------------------------------------------------------------------
bool __fastcall TTileIteratorAbstract::Iterator(void)
{
  int* Param;
  int Mult=1;
  switch(DPhase)
  {
    case 0:case 2: Param=(int*)&P0.y;break;
    case 1:case 3: Param=(int*)&P0.x;break;
  }
  int Value=*Param;
  if(DPhase>1) Mult=-1;
  bool Res=false;
  if(Mult*Value==CurrentRadius) DPhase++;
  if(Mult*Value<CurrentRadius)
  {
    (*Param)+=Mult;
    Res=CheckPoint(&P0,&P,&FTilesRect);
  }
  return Res;
}
//---------------------------------------------------------------------------
bool __fastcall TTileIteratorAbstract::PointFound(void)
{
  bool Found=false;
  while(CurrentRadius<=MaxRadius && !Found)
  {
    Found=Iterator();
    if(DPhase==4)
    {
      DPhase=0;
      CurrentRadius++;
      if(CurrentRadius>MaxRadius) Ended=true;
    }
    if(Found) break;
  }
  return Found;
}
//---------------------------------------------------------------------------
bool __fastcall TTileIteratorAbstract::Next(TPoint* PP)
{
  if(Ended) return false;
  bool Found=false;
  if(FTilesTotal==0)
  {
    Found=CheckPoint(&P0,&P,&FTilesRect);
    if(!Found) Found=PointFound();
    if(!Found) return false;
  }
  PP->x=P0.x+P.x;
  PP->y=P0.y+P.y;
  PointFound();
  FTilesTotal++;
  return true;
}

сразу после первого же false перепоиск будет работать только после резета. в теории.

[vdemidov]

Нашлася бага.
Берем прямоугольник ((0,0),(3,0)) тоесть 4 тайла. При выборе в качестве начальной (2,0) или (3,0) в выдачу не попадает тайл (0,0)