2017-12-11 124 views
5

Obecnie pracuję nad projektem hobby, aby automatycznie rozwiązać zagadkę z popularnej gry mobilnej I Love Hue. Gra jest dostępna pod numerem here.Jak sortować kolory w dwóch wymiarach?

Zasadniczo, cała przesłanka gry polega na tym, że dostajesz kilka kolorowych prostokątnych bloków zorganizowanych w siatce. Możesz zamienić większość bloków, z wyjątkiem kilku stałych bloków, które są oznaczone czarnymi kropkami. Celem gry jest zamiana bloków, aby uzyskać dwuwymiarowe spektrum kolorów. Kolory są sortowane w taki sposób, że kolor każdego bloku jest w przybliżeniu średnią z otaczających kolorów. (Niestety, nie znam żadnej teorii koloru, ale tam chyba słowo za to, co szukam.) Oto, co typowe puzzle wygląda następująco:

img

już w stanie wykonywać zrzuty ekranu poprzez adb, wyodrębnij macierz RGB z bloków i zaznacz, które bloki są "ustalone". Mam problem z rzeczywistą częścią algorytmu tego problemu.

Oto co zrobiłem do tej pory:

  1. Konwersja RGB do HSV i sortowanie kolorów poprzez barwę na liście jednowymiarowej. Daje mi to spektrum, ale nie wiem, jak przekonwertować ten wynik na dwa wymiary.
  2. Pozostawienie kolorów w RGB i próba pracy w pojedynczym kolorze. Prawdopodobnie jest tu jakiś rachunek wielowymiarowy, ale trudność polega na tym, że niektóre kolory mają jedną lub więcej wartości RGB. Konieczne byłoby rozważenie wszystkich trzech kolorów.
  3. Korzystanie z odległości euklidesowej w celu znalezienia odległości między każdą parą kolorów. Rozumiem, że ostatecznym celem jest, aby odległość ta była najmniejsza wśród sąsiednich kolorów, ale dwuwymiarowa siatka utrudnia to.
  4. Korzystając z odległości euklidesowej, opracowałem wskaźnik określający, jak idealna jest określona siatka, patrząc na odległość euklidesową kolorów sąsiednich bloków. Jednak nie mogę znaleźć skutecznego algorytmu, który mógłby wymyślić wymiany niezbędne do uzyskania idealnego stanu.
+0

ok Nie grałem w tę grę, ale z przedniej okładki gry wygląda to tak, że są 4 możliwe orientacje kolorów, które skutkowałyby gładkim wykończeniem ... tylko zastanawiasz się, czy gra akceptuje wszystkie 4 kombinacje. Czy zawsze są jakieś stałe bloki, aby zapewnić tylko jedno rozwiązanie? –

+0

@TheoWalton zawsze istnieją pewne stałe bloki, aby zapewnić tylko jedno rozwiązanie istnieje. –

+1

Obraz, do którego się odwołujesz, wygląda jak mieszanka zmiennej barwy i nasycenia. Nasycenie kolorów zwiększa się od środka promieniowo do krawędzi obrazu. Odcień zależy od kąta wokół środka obrazu. W ten sposób masz 2 wymiary we współrzędnych biegunowych. Czarne plamki barw deklarują teraz punkty kontrolne dla interpolacji na nieregularnej siatce. Jednakże, nie widząc żadnych innych przykładowych obrazów z tej gry, wciąż jest otwarty, niezależnie od tego, czy gradienty kolorów zawsze podążają za współrzędnymi biegunowymi, o których wspomniałem powyżej. –

Odpowiedz

4

Jeśli więcej solved obraz można utworzyć RGB Wykresy przedstawiają

tak wykreślić wykres 3D gdzie x,y jest położenie piksela i z jest kontrolowane kanał koloru (R, G i B). Z niego można określić niektóre właściwości gradientów. Jeśli wykres jest płaszczyzną, to wszystko, czego potrzebujesz, to normalne (wzięte z 3 znanych komórek). Jeśli jest to powierzchnia zakrzywiona w zależności od tego, ile punktów inflex dostała, możesz określić, w jaki sposób został użyty duży wielomian. Z tego wszystkiego możesz zacząć to rozwiązywać.

chciałbym zacząć od czegoś prostego (zakładając, że nie jest zbyt duży lub fantazyjne luki wielomiany):

Handle każdego kanału koloru oddzielnie. Używałbym tylko płytek statycznych i interpolowałem kolory siatki tylko od nich.Coś podobnego do:

nie widząc R, G, B wykresy nie mogę oszacować jaki rodzaj interpolacji trzeba. Jeśli wykresy są liniowe, użyj interpolacji liniowej lub liniowej. Jeśli nie, użyj wielomianów wyższego stopnia.

Wypełnij wszystkie komórki siatki, które możesz (ma sąsiadów o znanym kolorze). Następnie znajdź najbliższą ruchomą płytkę do obliczonego koloru (jeśli komórka ma wszystkie 3 kanały interpolowane) i umieść je (i ustaw jako statyczne).

Teraz wystarczy powtórzyć proces, aż wszystkie komórki zostaną obliczone.

[Edit1 14 grudnia 2017] Pewne dodatkowe informacje i rzeczy

był ciekawy i trochę czasu dzisiaj więc dałem mu strzał. Najpierw tworzę grę w C++/VCL, która zabrała twój obraz jako wejście (przycięte i zmienione). Następnie płytki klasyfikowane ręcznie i wykreślić wykres:

RGB plots

Białe kropki oznaczają płytka jest umieszczony prawidłowo (mecz interpolowaną koloru). Kolorowe kółka wokół kropek są interpolowanymi kolorami (dla porównania wizualnego musisz powiększyć, aby je zobaczyć).

Jak widać, wykresy R, G, B 3D wyglądają liniowo, więc (bi) liniowa interpolacja powinna wystarczyć.

Jeśli spróbowałem liniowej interpolacji tylko dla wierszy, solver natychmiast rozwiązuje zagadkę. Jednak gdy kodowałem to samo dla kolumn (bardziej nieznane komórki między znanymi), solver zaczął robić kilka niepoprawnych rozmieszczeń (unieważniając cały materiał, stąd błędne białe kropki).

column solver

Próbowałem też HSL ale po chwili wyrzucić z powodu trafienia ścianę bo Hue może przekroczyć 0 i 360 stopnia w dowolnym punkcie, który nie różni się od spraw, które czynił nie krzyżować się. W tym celu potrzebowałaby pewnej heurystyki lub korelacji krzyżowej z sąsiednimi rozwiązanymi obszarami, co byłoby zbyt dużym kodowaniem dla mojego gustu. Bez tego wyniki byłyby gorsze niż używanie RGB.

Więc teraz myślę o albo za pomocą interpolacji bilinear lub rozwiązać krótkie wstawki dystansowe najpierw, a dopiero potem rozwiązać resztę ...

[Edit2 14 grudnia 2017] interpolacja bilinear

Wygląda bilinear RGB interpolacja rozwiązuje wszystkie problemy. Więc jeśli twoja plansza jest zamknięta ze stałymi komórkami, powinna działać. Jeśli nie, musisz rozwiązać planszę iteracyjnie, a następnie użyć nowo rozwiązanych komórek jako nowych dla nierozwiązanych obszarów. Również zdałem sobie sprawę, że mam RGB odwróconą, więc też naprawiłem to :).

Tutaj C++/VCL źródło do gry (nie jest zoptymalizowany w ogóle):

//$$---- Form CPP ---- 
//--------------------------------------------------------------------------- 
#include <vcl.h> 
#include <math.h> 
#pragma hdrstop 
#include "Unit1.h" 
//--------------------------------------------------------------------------- 
#pragma package(smart_init) 
#pragma resource "*.dfm" 
//--------------------------------------------------------------------------- 
TForm1 *Form1; 
bool _update=false; 
//--------------------------------------------------------------------------- 
const _ILoveHue_state_fixed =255<<24; 
const _ILoveHue_state_unsolved= 0<<24; 
const _ILoveHue_state_solved = 1<<24; 
const _ILoveHue_render_board=0; 
const _ILoveHue_render_graph=1; 
//--------------------------------------------------------------------------- 
int rgbdist(DWORD c0,DWORD c1) // AABBGGRR 
    { 
    int r0,g0,b0,r1,g1,b1; 
    r0=(c0  &255); r1=(c1  &255); 
    g0=((c0>> 8)&255); g1=((c1>> 8)&255); 
    b0=((c0>>16)&255); b1=((c1>>16)&255); 
    r0-=r1; g0-=g1; b0-=b1; 
    return (r0*r0)+(g0*g0)+(b0*b0); 
    } 
//--------------------------------------------------------------------------- 
class ILoveHue 
    { 
public: 
    // variables 
    bool _redraw;    // redraw needed? 
    Graphics::TBitmap *bmp;  // screen buffer 
    int sxs,sys,mxs,mys,gxs,gys;// screen,map,grid cell resolution 
    DWORD **map,**imap;   // map[y][x] actual and interpolated 
    int mx,my,mx0,my0;   // mouse position state actual and last 
    TShiftState sh,sh0;   // mouse buttons and spec keys state actual and last 
    int render_mode; 
    // class constructors and destructors 
    ILoveHue() { bmp=new Graphics::TBitmap; bmp_resize(1,1); map=NULL; imap=NULL; mxs=0; mys=0; mx=-1; my=-1; mx0=-1; my0=-1; gxs=1; gys=1; render_mode=_ILoveHue_render_board; } 
    ~ILoveHue() { map_free(); if (bmp) delete bmp; } 
    ILoveHue(ILoveHue& a) { *this=a; } 
    ILoveHue* operator = (const ILoveHue *a) { *this=*a; return this; } 
    //ILoveHue* operator = (const ILoveHue &a) { ...copy... return this; } 

    // game/Window API and stuff 
    void map_free()        // relese map 
     { 
     if (map) { if (map[0]) delete[] map[0]; delete[] map; } map=NULL; mxs=0; mys=0; 
     if (imap) { if (imap[0]) delete[] imap[0]; delete[] imap; } imap=NULL; 
     } 
    void map_resize(int x,int y)    // resize/allocate map 
     { 
     _redraw=true; 
     if ((x==mxs)&&(y==mys)) return; map_free(); 
     map=new DWORD*[y]; if (map==NULL) return; map[0]=new DWORD[x*y]; if (map[0]==NULL) return; 
     imap=new DWORD*[y]; if (imap==NULL) return; imap[0]=new DWORD[x*y]; if (imap[0]==NULL) return; 
     mxs=x; mys=y; for (x=mxs,y=1;y<mys;y++,x+=mxs) { map[y]=map[0]+x; imap[y]=imap[0]+x; } 
     if (mxs) gxs=sxs/mxs; else gxs=1; 
     if (mys) gys=sys/mys; else gys=1; 
     } 
    void bmp_resize(int x=-1,int y=-1)   // resize bmp 
     { 
     _redraw=true; 
     if ((x>=0)&&(y>=0)) bmp->SetSize(x,y); 
     bmp->HandleType=bmDIB; 
     bmp->PixelFormat=pf32bit; 
     sxs=bmp->Width; 
     sys=bmp->Height; 
     if (mxs) gxs=sxs/mxs; else gxs=1; 
     if (mys) gys=sys/mys; else gys=1; 
     } 
    void bmp_load(AnsiString file)    // init game from image (map must be resized already) 
     { 
     _redraw=true; 
     // load file 
     bmp->LoadFromFile(file); 
     bmp_resize(); 
     // convert to map 
     int x,y; 
     DWORD *p,c; 
     for (y=0;y<mys;y++) 
     for (p=(DWORD*)bmp->ScanLine[(y*gys)+(gys>>1)],x=0;x<mxs;x++) 
      { 
      c=p[(x*gxs)+(gxs>>1)+4]&0x00FFFFFF;   // near mid point (0<<24 is unsolved state) 
      c=((c>>16)&0x000000FF)      // RGB -> BGR (file has reverse RGB order than bmp) 
      |((c<<16)&0x00FF0000) 
      |(c  &0x0000FF00); 
      map[y][x]=c; 
      c=p[(x*gxs)+(gxs>>1)]&0x00FFFFFF;   // mid point 
      if ((((c)|(c>>8)|(c>>16))&255)<64)   // ~max(R,G,B)<32 
      map[y][x]|=_ILoveHue_state_fixed; 
      } 
     } 
    void mouse(int x,int y,TShiftState s)  // handle mouse 
     { 
     _redraw=true; 
     mx=x/gxs; 
     my=y/gys; 
     sh0=sh; sh=s; 
     bool q0=sh0.Contains(ssLeft); 
     bool q1=sh .Contains(ssLeft); 
     if ((!q0)&&(q1)){ mx0=mx; my0=my; } // mouse left button down 
     if ((q0)&&(!q1))      // mouse left button up (swap) 
      { 
      // swap if valid coordinates 
      if ((mx0>=0)&&(mx0<mxs)&&(my0>=0)&&(my0<mys)) if (DWORD(map[my0][mx0]&0xFF000000)!=_ILoveHue_state_fixed) 
      if ((mx >=0)&&(mx <mxs)&&(my >=0)&&(my <mys)) if (DWORD(map[my ][mx ]&0xFF000000)!=_ILoveHue_state_fixed) 
       { 
       DWORD c=map[my0][mx0]; map[my0][mx0]=map[my][mx]; map[my][mx]=c; // swap cells 
       map[my0][mx0]&=0x00FFFFFF; map[my0][mx0]|=_ILoveHue_state_unsolved; // set them as unsolved 
       map[my ][mx ]&=0x00FFFFFF; map[my ][mx ]|=_ILoveHue_state_unsolved; 
       map_solve(false);             // check for solved state 
       } 
      // clear selection 
      mx0=-1; my0=-1; 
      } 
     } 
    void draw()         // render game 
     { 
     _redraw=false; 
     int x,y,z,x0,x1,x2,y0,y1,y2,r; 
     DWORD c; 
     if (render_mode==_ILoveHue_render_board) 
      { 
      for (y0=0,y1=gys,y2=gys>>1,y=0;y<mys;y++,y0+=gys,y1+=gys,y2+=gys) 
      for (x0=0,x1=gxs,x2=gxs>>1,x=0;x<mxs;x++,x0+=gxs,x1+=gxs,x2+=gxs) 
       { 
       c=map[y][x]; 
       bmp->Canvas->Pen->Color=TColor(c&0x00FFFFFF); 
       if ((x==mx)&&(y==my)) bmp->Canvas->Pen->Color=clYellow; 
       if ((x==mx0)&&(y==my0)) bmp->Canvas->Pen->Color=clGreen; 
       bmp->Canvas->Brush->Color=TColor(c&0x00FFFFFF); 
       bmp->Canvas->Rectangle(x0,y0,x1,y1); 

       if (DWORD(c&0xFF000000)!=_ILoveHue_state_fixed) 
        { 
        r=10; 
        bmp->Canvas->Pen->Color=imap[y][x]&0x00FFFFFF; 
        bmp->Canvas->Brush->Style=bsClear; 
        bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r); 
        bmp->Canvas->Brush->Style=bsSolid; 
        } 

       if (DWORD(c&0xFF000000)!=_ILoveHue_state_unsolved) 
        { 
        if (DWORD(c&0xFF000000)==_ILoveHue_state_fixed) c=clBlack; 
        if (DWORD(c&0xFF000000)==_ILoveHue_state_solved) c=clWhite; 
        r=4; 
        bmp->Canvas->Pen->Color=c; 
        bmp->Canvas->Brush->Color=c; 
        bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r); 
        } 
       } 
      } 
     if (render_mode==_ILoveHue_render_graph) 
      { 
      bmp->Canvas->Pen->Color=clBlack; 
      bmp->Canvas->Brush->Color=clBlack; 
      bmp->Canvas->Rectangle(0,0,sxs,sys); 
      r=13; x0=15; y0=sys-15; 
      int c=r*double(256.0*cos(55.0*M_PI/180.0)); 
      int s=r*double(256.0*sin(55.0*M_PI/180.0)); 
      bmp->Canvas->Pen->Color=clRed; 
      for (y=0;y<mys;y++) 
      for (x=0;x<mxs;x++) 
       { 
       z=(map[y][x])&255; 
       x1=x0+(x*r)+((y*c)>>8); 
       y1=y0  -((y*s)>>8); 
       bmp->Canvas->MoveTo(x1,y1); 
       bmp->Canvas->LineTo(x1,y1-z); 
       } x0=x1+5; 
      bmp->Canvas->Pen->Color=clGreen; 
      for (y=0;y<mys;y++) 
      for (x=0;x<mxs;x++) 
       { 
       z=(map[y][x]>>8)&255; 
       x1=x0+(x*r)+((y*c)>>8); 
       y1=y0  -((y*s)>>8); 
       bmp->Canvas->MoveTo(x1,y1); 
       bmp->Canvas->LineTo(x1,y1-z); 
       } x0=x1+5; 
      bmp->Canvas->Pen->Color=clBlue; 
      for (y=0;y<mys;y++) 
      for (x=0;x<mxs;x++) 
       { 
       z=(map[y][x]>>16)&255; 
       x1=x0+(x*r)+((y*c)>>8); 
       y1=y0  -((y*s)>>8); 
       bmp->Canvas->MoveTo(x1,y1); 
       bmp->Canvas->LineTo(x1,y1-z); 
       } 

      } 
     } 
    // Solver 
    void map_solve(bool _solve) // check for solved state and try to solve if _solve is true 
     { 
     _redraw=true; 
     const int _thr=10; // color comparison threshold 
     int x,y,x0,x1,y0,y1,xx,yy; 
     int r0,g0,b0,r,g,b; 
     int r1,g1,b1; 
     int r2,g2,b2; 
     int r3,g3,b3; 
     DWORD c; 

     // compute interpolated colors to imap (wanted solution) 
     for (x=0;x<mxs;x++) 
     for (y=0;y<mys;y++) 
      if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed) 
      { 
      for (x0=-1,xx=x;xx>= 0;xx--) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x0=xx; break; } 
      for (x1=-1,xx=x;xx<mxs;xx++) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x1=xx; break; } 
      for (y0=-1,yy=y;yy>= 0;yy--) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y0=yy; break; } 
      for (y1=-1,yy=y;yy<mys;yy++) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y1=yy; break; } 
      c=0; 
      if (int(x0|x1|y0|y1)>=0) 
       { 
       // bilinear interpolation 
       c=map[y0][x0]; r0=c&255; g0=(c>>8)&255; b0=(c>>16)&255; 
       c=map[y0][x1]; r1=c&255; g1=(c>>8)&255; b1=(c>>16)&255; 
       c=map[y1][x0]; r2=c&255; g2=(c>>8)&255; b2=(c>>16)&255; 
       c=map[y1][x1]; r3=c&255; g3=(c>>8)&255; b3=(c>>16)&255; 
       r0=r0+(r1-r0)*(x-x0)/(x1-x0); 
       g0=g0+(g1-g0)*(x-x0)/(x1-x0); 
       b0=b0+(b1-b0)*(x-x0)/(x1-x0); 
       r1=r2+(r3-r2)*(x-x0)/(x1-x0); 
       g1=g2+(g3-g2)*(x-x0)/(x1-x0); 
       b1=b2+(b3-b2)*(x-x0)/(x1-x0); 
       r =r0+(r1-r0)*(y-y0)/(y1-y0); 
       g =g0+(g1-g0)*(y-y0)/(y1-y0); 
       b =b0+(b1-b0)*(y-y0)/(y1-y0); 
       c=(r)+(g<<8)+(b<<16); 
       } 
      imap[y][x]=c; 
      } 

     // compute solved state 
     for (x=0;x<mxs;x++) 
     for (y=0;y<mys;y++) 
      if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed) 
      { 
      map[y][x]&=0x00FFFFFF; 
      if (rgbdist(map[y][x],imap[y][x])<_thr) map[y][x]|=_ILoveHue_state_solved; 
      else         map[y][x]|=_ILoveHue_state_unsolved; 
      } 

     // solver/checker 
     if (_solve) 
      { 
      // process all unsolved cells 
      for (x=0;x<mxs;x++) 
      for (y=0;y<mys;y++) 
       if (DWORD(map[y][x]&0xFF000000)==_ILoveHue_state_unsolved) 
       // find match in unsolved cells 
       for (xx=0;xx<mxs;xx++) 
       for (yy=0;yy<mys;yy++) 
       if (DWORD(map[yy][xx]&0xFF000000)==_ILoveHue_state_unsolved) 
        if (rgbdist(map[yy][xx],imap[y][x])<_thr) 
        { 
        // swap if found 
        c=map[yy][xx]; 
        map[yy][xx]=map[y][x]; 
        map[y][x]=(c&0x00FFFFFF)|_ILoveHue_state_solved; 
        } 
      } 
     } 
    } gam; 
//--------------------------------------------------------------------------- 
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner) 
    { 
    gam.map_resize(7,9); 
    gam.bmp_load("map.bmp"); 
    gam.map_solve(false); 
    _update=true; 
    ClientWidth=gam.sxs; 
    ClientHeight=gam.sys; 
    _update=false; 
    } 
//--------------------------------------------------------------------------- 
void __fastcall TForm1::FormDestroy(TObject *Sender) 
    { 
    gam.render_mode=_ILoveHue_render_board; 
    gam.draw(); 
    gam.bmp->SaveToFile("map.bmp"); 
    } 
//--------------------------------------------------------------------------- 
void __fastcall TForm1::FormPaint(TObject *Sender){ gam.draw(); Canvas->Draw(0,0,gam.bmp); } 
void __fastcall TForm1::FormResize(TObject *Sender){ if (_update) return; gam.bmp_resize(ClientWidth,ClientHeight); } 
void __fastcall TForm1::Timer1Timer(TObject *Sender){ if (gam._redraw) FormPaint(Sender); } 
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); } 
void __fastcall TForm1::FormMouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); } 
void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); } 
//--------------------------------------------------------------------------- 
void __fastcall TForm1::FormKeyDown(TObject *Sender, WORD &Key, TShiftState Shift) 
    { 
    if (Key=='S') gam.map_solve(true);      // try to solve 
    if (Key=='M') { gam.render_mode^=1; gam._redraw=true; } // swap render modes 
    if (Key==115) gam.bmp->SaveToFile("screenshot.bmp"); // [F4] screenshot 
    } 
//--------------------------------------------------------------------------- 

Jest to pojedyncza postać App w BDS2006 z pojedynczym 40ms czasowy na nim. Więc dodaj wydarzenia ... Możesz zignorować rendering VCL i zawartość okna. Ważną rzeczą jest klasa i funkcja solve(). Jest używany zarówno do prawidłowego sprawdzania położenia, jak i do rozwiązywania (w zależności od bool'a _solve). To jest obraz wejściowy map.bmp

map.bmp

nie kodować odpowiednie zapisać/funkcje państwowe obciążenia zamiast Zdecydowałem się użyć samego bezpośrednio (strata przestrzeni, ale prawie bez wysiłku code) bitmapy.

sama mapa jest 2D 32-bitowy DWORD tablicę z postaci SSBBGGRR hex gdzie SS jest flaga komórki (stała/rozwiązany/rozwiązany).

Tutaj skompilowany demo z kodem źródłowym

Przeczytaj readme.txt aby uzyskać więcej informacji. Oto wynik po rozwiązaniu (naciskając klawisz [S]):

solved state

Jak można (nie) zobaczyć kręgi znikają jak dopasowuje bilinearly interpolowane kolor dokładniej swój wkład.

Program oczekuje siatki o rozmiarze 7x9, rozdzielczość obrazu nie jest ważna. Kolor jest próbą od połowy punktu komórce (czarna kropka) i lekko w prawo (kolor dachówka)

Aby uczynić to wydajny można zrobić 2 rzeczy:

  1. add/lista użycie zawierającego nierozwiązane komórki

    zamiast itearting na całej mapie iterują tylko po liście nierozwiązanych komórek.

  2. nawrócony T(N^2) wyszukiwania do T((N^2)/2) przez poszukiwaniu trójkąta

    To jednak wciąż O(N^2) ale stała czasowa jest mniejsza.

  3. użycie RGB 3D LUT tabeli

    dla dużych sieci można utworzyć 32k wpisów 3D LUT tabeli można odnaleźć szukane dopasowanie komórkę O(1).Wystarczy przekonwertować RGB do 15 bitowego koloru i używać

    DWORD LUT[32][32][32]; 
    

    gdzie LUT[r][g][b]=row+(column<<16); Tis sposób będziesz wiedział, gdzie każdy kolor jest umieszczony. Wszystkie niewykorzystane kolory ustawione na 0xFFFFFFFF. Oto przykład użycia tej techniki do podobnych celów:

    Look dla recolor[32][32][32] w kodzie ... Z grubej koloru 15bit może być nie tyle do tego celu może być tak, że trzeba więcej bitów, takich jak 18-bit, co daje 256-krotne wpisy, które wciąż można zarządzać.

    Utworzenie tego LUT zajmie O(N) czas, ale używanie i utrzymywanie jest tylko O(1) czasu.

0

Nie mam pojęcia, czy to zadziała, czy nie. Napisałem to dla zabawy i nie mogłem zastosować prawdziwego testu. Byłoby to docenić, jeśli uprzejmie spróbować i komentarz na ten temat.

 struct pixel 
     { 
      public int R; 
      public int G; 
      public int B; 
      public bool Fixed; 
      public pixel(int r, int g, int b, bool _fixed) 
      { 
       this.R = r; this.G = g; this.B = b; this.Fixed = _fixed; 
      } 
      public int DistanceSQ(pixel px) 
      { 
       int r = this.R - px.R; 
       int g = this.G - px.G; 
       int b = this.B - px.B; 
       return r * r + g * g + b * b; 
      } 
      public override string ToString() 
      { 
       return string.Format("{0} {1} {2} {3}", this.R, this.G, this.B, this.Fixed); 
      } 
      public override int GetHashCode() 
      { 
       return this.R.GetHashCode()^this.G.GetHashCode()^this.B.GetHashCode(); 
      } 
      public override bool Equals(object obj) 
      { 
       pixel px = (pixel)obj; 
       return this.R == px.R && this.G == px.G && this.B == px.B; 
      } 
     } 
     static void sort(pixel[,] img) 
     {    
      List<pixel> lst = new List<pixel>(); 
      foreach (pixel px in img) 
       if (!px.Fixed) 
        lst.Add(px); 

      int rows = img.GetLength(0); 
      int cols = img.GetLength(1); 
      while (lst.Count > 0) 
       for (int row = 0; row < rows; row++) 
        for (int col = 0; col < cols; col++) 
         if (!img[row, col].Fixed) 
         { 
          pixel[] neighbors = getFixedNeighbors(img, row, col, rows, cols).ToArray(); 
          int min = int.MaxValue; 
          pixel nearest = new pixel(); 
          foreach (pixel n in lst) 
          { 
           int dist = neighbors.Select((a) => a.DistanceSQ(n)).Sum(); 
           if (dist < min) 
           { 
            min = dist; 
            nearest = n; 
           } 
          } 
          nearest.Fixed = true; 
          img[row, col] = nearest; 
          lst.Remove(nearest); 
          if (lst.Count == 0) 
           return; 
         } 
     } 
     private static IEnumerable<pixel> getFixedNeighbors(pixel[,] img, int row, int col, int rows, int cols) 
     { 
      for (int r = Math.Max(0, row - 1); r < Math.Min(row + 2, rows); r++) 
       for (int c = Math.Max(0, col - 1); c < Math.Min(col + 2, cols); c++) 
        if (img[r, c].Fixed) 
         yield return img[r, c]; 

     } 



     //test 
     { 
      bool b0 = false; bool b1 = true;//for easy editing 
      { 
       pixel[,] img = new pixel[3, 4]; 
       img[0, 0] = new pixel(0, 0, 0, b1); img[1, 0] = new pixel(0, 1, 0, b0); img[2, 0] = new pixel(0, 2, 0, b1); 
       img[0, 1] = new pixel(1, 0, 0, b0); img[1, 1] = new pixel(1, 1, 0, b0); img[2, 1] = new pixel(1, 2, 0, b0); 
       img[0, 2] = new pixel(2, 0, 0, b0); img[1, 2] = new pixel(2, 1, 0, b0); img[2, 2] = new pixel(2, 2, 0, b0); 
       img[0, 3] = new pixel(3, 0, 0, b1); img[1, 3] = new pixel(3, 1, 0, b0); img[2, 3] = new pixel(3, 2, 0, b1); 
       sort(img); 
      } 
      { 
       pixel[,] img = new pixel[3, 4]; 
       img[0, 0] = new pixel(0, 0, 0, b1); img[1, 0] = new pixel(0, 1, 0, b0); img[2, 0] = new pixel(0, 2, 0, b1); 
       img[0, 1] = new pixel(2, 0, 0, b0); img[1, 2] = new pixel(2, 1, 0, b0); img[2, 2] = new pixel(2, 2, 0, b0); 
       img[0, 2] = new pixel(1, 0, 0, b0); img[1, 1] = new pixel(1, 1, 0, b0); img[2, 1] = new pixel(1, 2, 0, b0); 
       img[0, 3] = new pixel(3, 0, 0, b1); img[1, 3] = new pixel(3, 1, 0, b0); img[2, 3] = new pixel(3, 2, 0, b1); 
       sort(img); 
      } 
     } 

Kod jest prosty. Zachowuje niedowartościowane pozycje na liście i usuwa je, gdy zostanie znaleziona. Aby zdecydować, który kolor powinien być wybrany dla lokalizacji, wybierany jest kolor o minimalnej sumie odległości kwadratowej. Sqrt nie jest wymagany, ponieważ potrzebujemy go jedynie do porównania.

"sort" to główna funkcja, która zmienia położenie nieskalowanych pikseli. Dane wejściowe dla tej funkcji to tablica pikseli pików wiersza. Funkcja "sort" wprowadza zmiany w tej tablicy.

+0

dodaj kilka słów o tym, jak to działa. Czysty, nie komentowany kod jest trudny do uchwycenia dla kogokolwiek innego niż jego autora, nawet jeśli wygląda na prosty ... – Spektre

+0

@Spektre Dodałem kilka wyjaśnień na ten temat. Mam nadzieję, że wystarczy. Kod wyjaśnia się lepiej. Nie sądzę, abyśmy mieli do czynienia z interpolacją tego problemu; ale nie jestem do końca pewien. Dzięki. – Koray

+1

co jest nieco lepsze, ale wydaje mi się, że jest to użyteczne dla innych Powinieneś przynajmniej dodać, jakie są główne zmienne i sposoby oraz w jaki sposób dane wejściowe i wyjściowe układanki są przechowywane (format). – Spektre