रंगों को दो आयामों में कैसे क्रमबद्ध करें?

Question

मैं वर्तमान में लोकप्रिय मोबाइल गेम आई लव ह्यू से एक पहेली को स्वचालित रूप से हल करने के लिए एक शौक परियोजना पर काम कर रहा हूं। खेल here उपलब्ध है।

असल में, खेल का पूरा आधार यह है कि आपको ग्रिड में व्यवस्थित रंगीन आयताकार ब्लॉक का एक गुच्छा दिया जाता है। आप ब्लैक डॉट्स द्वारा चिह्नित कुछ निश्चित ब्लॉक को छोड़कर अधिकांश ब्लॉकों को स्वैप कर सकते हैं। खेल का उद्देश्य चारों ओर ब्लॉक को स्वैप करना है ताकि आपको रंग का दो-आयामी स्पेक्ट्रम मिल सके। रंगों को क्रमबद्ध किया जाता है कि प्रत्येक ब्लॉक का रंग लगभग इसके आसपास के रंगों का औसत होता है। (क्षमा करें, मैं किसी भी रंग सिद्धांत पता नहीं लेकिन वहाँ शायद मैं के लिए क्या देख रहा हूँ के लिए एक शब्द है।) यहाँ एक ठेठ पहेली लग रहा है की तरह है:

मैं पहले से ही स्क्रीनशॉट लेने के लिए सक्षम किया गया है एडीबी के माध्यम से, ब्लॉक से आरजीबी मैट्रिक्स निकालें और चिह्नित करें कि कौन से ब्लॉक "निश्चित" हैं। मुझे इस समस्या के वास्तविक एल्गोरिदमिक हिस्से में परेशानी हो रही है।

यहाँ मैं अब तक क्या किया है है:

1. एक आयामी सूची में रंग द्वारा एचएसवी के लिए आरजीबी परिवर्तित और रंग छँटाई। यह मुझे एक स्पेक्ट्रम देता है, लेकिन मुझे नहीं पता कि इस परिणाम को दो आयामों में कैसे परिवर्तित किया जाए।
2. आरजीबी में रंग छोड़ना और एकवचन रंग के साथ काम करने का प्रयास करना। शायद कुछ बहुविकल्पीय कैलकुस मैं यहां कर सकता हूं, लेकिन कठिनाई इस तथ्य में निहित है कि कुछ रंग उनके आरजीबी मूल्यों में से एक या अधिक साझा करते हैं। सभी तीन रंगों पर विचार करना आवश्यक होगा।
3. रंगों की प्रत्येक जोड़ी के बीच की दूरी खोजने के लिए यूक्लिडियन दूरी का उपयोग करना। मैं समझता हूं कि अंतिम लक्ष्य इस दूरी को आसन्न रंगों में सबसे छोटा होना है, लेकिन द्वि-आयामी ग्रिड इसे और अधिक कठिन बना रहा है।
4. यूक्लिडियन दूरी का उपयोग करके, मैंने एक मीट्रिक विकसित किया है कि आस-पास के ब्लॉक के रंगों की यूक्लिडियन दूरी को देखकर एक निश्चित ग्रिड कितना आदर्श है। हालांकि, मुझे एक कुशल एल्गोरिदम नहीं मिल रहा है जो आदर्श स्थिति में जाने के लिए आवश्यक स्वैप को समझ सकता है।

Answer 1

आप अधिक solved छवियों है, तो आप आरजीबी रेखांकन साजिश

बना सकते हैं तो 3 डी ग्राफ जहां x,y पिक्सेल स्थिति है और z निरीक्षण किया जाता रंग चैनल साजिश (आर, जी या बी)। इससे आप ग्रेडियेंट के कुछ गुण निर्धारित कर सकते हैं। यदि साजिश आपको आवश्यकतानुसार एक विमान है तो केवल सामान्य (3 ज्ञात कोशिकाओं से लिया गया) है। यदि यह घुमावदार सतह है, तो इस पर निर्भर करता है कि कितने इन्फ्लेक्स बिंदु प्राप्त हुए हैं, आप यह निर्धारित कर सकते हैं कि इसके लिए बहुपद बहुपद का उपयोग किया गया था। इन सब से आप इसे हल करना शुरू कर सकते हैं।

मैं कुछ सरल (यह मानते हुए नहीं बहुत बड़ा अंतराल या फैंसी बहुआयामी पद) के साथ शुरू होगा:

अलग से प्रत्येक रंग चैनल संभाल। मैं सिर्फ स्थिर टाइल्स का उपयोग करता हूं और केवल उनसे ग्रिड रंगों को अलग करता हूं।कुछ के समान:

• Interpolating 3D Coordinates between known missing time intervals

आर, जी, बी रेखांकन मैं अनुमान नहीं कर सकते प्रक्षेप आप किस प्रकार की जरूरत को देखने के बिना। यदि ग्राफ रैखिक उपयोग द्वि-रैखिक या रैखिक इंटरपोलेशन हैं। यदि उच्च डिग्री बहुपदों का उपयोग नहीं करते हैं।

तो आप जो भी ग्रिड कोशिकाएं कर सकते हैं उसे भरें (ज्ञात रंग वाले पड़ोसी हैं)। इसके बाद गणना वाले रंग के निकटतम चलने योग्य टाइल ढूंढें (यदि सेल में सभी 3 चैनल इंटरपोलेटेड हैं) और उन्हें रखें (और स्थैतिक के रूप में सेट करें)।

अब सभी कोशिकाओं की गणना होने तक प्रक्रिया को दोहराएं।

[Edit1 दिसंबर 14 2017] कुछ अतिरिक्त नोट्स और सामान

उत्सुक था और आज कुछ समय मिल गया तो मैं इसे एक शॉट दे दी है। सबसे पहले मैं सी ++/वीसीएल में गेम बना देता हूं जिसने आपकी छवि इनपुट (फसल और आकार बदल दी) के रूप में ली। तब मैं टाइल्स मैन्युअल छाँटे गए और साजिश रेखांकन:

व्हाइट डॉट्स का मतलब टाइल सही ढंग से रखा जाता है (अंतर्वेशित रंग से मेल खाते हैं)। बिंदुओं के चारों ओर रंगीन मंडल इंटरपोलेटेड रंग होते हैं (दृश्य तुलना के लिए आपको उन्हें देखने के लिए ज़ूम करने की आवश्यकता होती है)।

जैसा कि आप आर, जी, बी 3 डी प्लॉट्स रैखिक दिखते हैं तो (द्वि) रैखिक इंटरपोलेशन पर्याप्त होना चाहिए।

यदि मैंने पंक्तियों के लिए केवल रैखिक इंटरपोलेशन की कोशिश की तो सॉल्वर तुरंत पहेली को हल करता है। हालांकि जब मैंने स्तंभों (ज्ञात लोगों के बीच अधिक अज्ञात कोशिकाओं) के लिए कोड किया, तो सॉल्वर ने कुछ गलत प्लेकिंग शुरू कर दीं (पूरी सामग्री को गलत सफेद बिंदुओं को अमान्य कर दिया)।

मैं भी एचएसएल कोशिश की, लेकिन कुछ समय के बाद मैं वजह से एक दीवार से टकराने क्योंकि ह्यू किसी भी बिंदु जो मामले हैं, जिनके किया से अलग पहचाना नहीं है पर 0 और 360 डिग्री पार कर सकते हैं करने के लिए दूर फेंक पार नहीं इसके लिए पड़ोसी हल किए गए क्षेत्रों से कुछ ह्युरिस्टिक्स या क्रॉस सहसंबंध की आवश्यकता होगी और यह मेरे स्वाद के लिए बहुत अधिक कोडिंग होगा। इसके बिना परिणाम आरजीबी का उपयोग करते हुए भी बदतर।

तो अब मैं द्विरेखीय प्रक्षेप का उपयोग कर या पहले थोड़ी दूरी पर छेड़छाड़ का समाधान और उसके बाद ही बाकी का समाधान द्विरेखीय प्रक्षेप

ऐसा लगता है कि या तो के बारे में सोच रहा हूँ ...

[EDIT2 दिसंबर 14 2017] बिलीनेर आरजीबी इंटरपोलेशन सभी मुद्दों को हल करता है। तो यदि आपका बोर्ड निश्चित कोशिकाओं से घिरा हुआ है तो इसे काम करना चाहिए। यदि आपको बोर्ड को क्रमशः हल करने की आवश्यकता नहीं है और फिर नए हल किए गए कोशिकाओं का उपयोग अनसुलझे क्षेत्रों के लिए नई बाध्यता के रूप में करें। इसके अलावा मुझे एहसास हुआ कि मुझे आरजीबी उलट दिया गया है इसलिए मैंने इसे भी मरम्मत की :) :)।

यहाँ

सी ++/VCL खेल के लिए स्रोत (यह सब पर अनुकूल नहीं है):

//$$---- 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 
    } 
//--------------------------------------------------------------------------- 

यह BDS2006 में एक भी पर्चा अनुप्रयोग इस पर एकल 40ms टाइमर के साथ है। तो बस घटनाओं को जोड़ें ... आप वीसीएल प्रतिपादन और खिड़की की सामग्री को अनदेखा कर सकते हैं। महत्वपूर्ण बात यह है कि वर्ग और solve() इसमें फ़ंक्शन है। इसका उपयोग सही रखने की जांच और हल करने के लिए किया जाता है (_solve बूल के आधार पर)। यह इनपुट छवि map.bmp

मैं उचित कोड नहीं किया सहेजें/लोड राज्य कार्यों के बजाय मैं बिटमैप ही सीधे (अंतरिक्ष की बर्बादी लेकिन लगभग कोई कोड प्रयास) का उपयोग करने के लिए चुना है।

स्वयं मानचित्र SSBBGGRR hex के फार्म के साथ 2 डी 32 बिट DWORD सरणी जहां SS सेल (फिक्स्ड/हल/अनसुलझी) का झंडा है।

स्रोत कोड

• Win32 demo

साथ यहाँ संकलित डेमो अधिक जानकारी के लिए readme.txt पढ़ें। यहाँ सुलझाने के बाद परिणाम (दबाने [एस]):

के रूप में आप (नहीं) देख सकते हैं हलकों गायब हो के रूप में bilinearly अंतर्वेशित रंग और अधिक बारीकी से अपने इनपुट मेल खाता है।

प्रोग्राम आकार 7x 9 के ग्रिड की अपेक्षा कर रहा है छवि का संकल्प महत्वपूर्ण नहीं है। रंग सेल (काले डॉट) और थोड़ा के मध्य बिंदु से सही (टाइल रंग)

इस कुशल बनाने के लिए करने के लिए नमूना आप 2 बातें कर सकते हैं:

1. जोड़ें/उपयोग सूची से युक्त अनसुलझा कोशिकाएं

   पूरे नक्शा पर शुरू होने के बजाय केवल अनसुलझा कोशिकाओं की सूची के माध्यम से। त्रिकोण खोज

   द्वारा T((N^2)/2) को

2. परिवर्तित T(N^2) खोजें यह अभी भी O(N^2) तथापि है लेकिन लगातार समय छोटा होता है।

3. उपयोग 3 डी आरजीबी LUT तालिका

   बड़ी ग्रिड के लिए आप 32K प्रविष्टियों 3 डी lut तालिका बना सकते हैं O(1) में खोजा गया मिलान सेल खोजने के लिए।सीधे शब्दों में 15 बिट रंग के लिए आरजीबी बदलने और का उपयोग

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

   जहां LUT[r][g][b]=row+(column<<16); Tis तरह से जहां प्रत्येक रंग रख दिया गया है आप पता चल जाएगा। सभी अप्रयुक्त रंग 0xFFFFFFFF पर सेट हैं। यहाँ समान उद्देश्य के लिए इस तकनीक का उपयोग का एक उदाहरण: कोड में recolor[32][32][32] के लिए

   • Effective gif/image color quantization?

   देखो ... मोटे 15bit रंग के इस उद्देश्य के लिए पर्याप्त नहीं हो सकता है तो आप की आवश्यकता होगी हो सकता है 18 बिट की तरह अधिक बिट्स जिसके परिणामस्वरूप 256 के प्रविष्टियां हैं जो अभी भी प्रबंधनीय हैं।

   इस LUT बनाना O(N) समय लगेगा लेकिन का उपयोग करने और बनाए रखने के यह केवल O(1) समय है।

Answer 2

मुझे कोई विचार नहीं है कि यह काम करेगा या नहीं। मैंने इसे मजेदार के लिए लिखा है और इस पर एक वास्तविक परीक्षण लागू नहीं कर सका। यदि आप कृपया इसे इसके बारे में कोशिश करें और इसके बारे में टिप्पणी दें तो इसकी सराहना की जाएगी।

 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); 
      } 
     } 

कोड सरल है। यह किसी श्रेणी में रेटेड वाले लोगों को नहीं रखता है और जब स्थान इसके लिए मिलता है तो प्रत्येक को हटा दें। यह तय करने के लिए कि किसी स्थान के लिए कौन सा रंग चुना जाना चाहिए, रंग जिसमें न्यूनतम दूरी का वर्ग दूरी चुना गया है। Sqrt की आवश्यकता नहीं है क्योंकि हमें इसकी तुलना केवल इसकी आवश्यकता है।

"सॉर्ट" मुख्य फ़ंक्शन है जो निश्चित पिक्सल के स्थानों को बदलता है। इस फ़ंक्शन के लिए इनपुट पिक्सल की पंक्ति-कर्नल सरणी है। "सॉर्ट" फ़ंक्शन इस सरणी में परिवर्तन करता है।