如何在二维中对颜色进行排序？

本文介绍了如何在二维中对颜色进行排序？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 我目前正在从事一项爱好项目，以自动解决流行的手机游戏《我爱色相》中的难题。 没有看到 R，G，B 图我无法估计您需要哪种插值。如果图形是线性的，请使用双线性或线性插值。如果不使用更高阶的多项式。 因此，请填写所有可能的网格单元（具有已知颜色的邻居）。之后，找到最接近计算出的颜色的活动图块（如果单元格已对所有3个通道进行插值）并将其放置（并设置为静态）。 现在，只需重复此过程，直到 [Edit1 Dec 14 2017]一些附加的注释和内容 很好奇，今天有一些时间，所以我试了一下。首先，我用C ++ / VCL创建游戏，该游戏将您的图像作为输入（裁剪和调整大小）。然后，我手动对图块进行排序并绘制图形： 白色点表示正确放置了图块（匹配插值的颜色）。点周围的彩色圆圈是插值的颜色（为了进行视觉比较，您需要缩放以查看它们）。 您可以看到 R，G， B 3D 图看起来是线性的，所以（bi）线性插值就足够了。 如果我仅对行尝试线性插值，则只有求解器会立即解决难题。但是，当我为列（在已知的列之间有更多未知的单元格）编写相同的代码时，求解器开始进行少量不正确的放置（使全部内容无效，因此出现了错误的白点）。 我也尝试过 HSL ，但过了一会儿，由于撞墙，我把它扔了因为色调可以在任何无法区别于 0 和 360 的学位上通过没有交叉的案件。为此，它需要来自邻近解决区域的一些启发式或互相关性，而这对于我的品味来说将是太多的编码。如果没有它，结果将变得更糟，然后使用 RGB 。 所以现在我正在考虑使用双线性插值法或首先解决短距离插值法然后才解决其余问题... [Edit2 Dec 14 2017]双线性插值 看起来像双线性 RGB 插值解决了所有问题。因此，如果您的电路板装有固定的单元格，则可以正常工作。如果不是，则需要迭代求解电路板，然后将新求解的单元格用作未求解区域的新边界。我也意识到我 RGB 反转了，所以我也修复了它：）。 这里是 C ++ / VCL 的源代码对于游戏（根本没有优化）： // $$- -表格CPP ---- // ------------------------------------- -------------------------------------- #include< vcl.h> #include< math.h> #pragma hdrstop #include Unit1.h // -------------------------- ------------------------------------------------- #pragma软件包（smart_init） #pragma资源 * .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）; } // --------------------------------------- ------------------------------------ 类ILoveHue { public： //变量 bool _redraw; //需要重绘吗？ Graphics :: TBitmap * bmp; //屏幕缓冲区 int sxs，sys，mxs，mys，gxs，gys; //屏幕，地图，网格单元分辨率 DWORD ** map，** imap; // map [y] [x]实际和内插的 int mx，my，mx0，my0; //鼠标位置状态实际值和最后一个 TShiftState sh，sh0; //鼠标按钮和spec键说明实际的和最后的 int render_mode; //类的构造函数和析构函数 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（）;如果（bmp）删除bmp； } ILoveHue（ILoveHue& a）{* this = a; } ILoveHue *运算子=（const ILoveHue * a）{* this = * a;返回这个} // ILoveHue *运算子=（const ILoveHue& a）{... copy ... return this; } //游戏/窗口API和东西 void map_free（）//相对地图 { if（map）{if（map [0]） delete []地图[0]; delete []地图； } 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）//调整地图大小/分配 { _redraw = true; if（（（x == mxs）&&（y == mys））return; map_free（）; map = new DWORD * [y];如果（map == NULL）返回; map [0] =新的DWORD [x * y]; if（map [0] == NULL）返回； imap =新DWORD * [y];如果（imap == NULL）返回; imap [0] = new DWORD [x * y];如果（imap [0] == NULL）返回； mxs = x; mys = y;对于（x = mxs，y = 1; y if（mxs）gxs = sxs / mxs;否则gxs = 1; 如果（mys）gys = sys / mys;否则gys = 1; } void bmp_resize（int x = -1，int y = -1）//调整bmp的大小 { _redraw = true; if（（（x> = 0）&&（y> = 0））bmp-> SetSize（x，y）; bmp-> HandleType = bmDIB; bmp-> PixelFormat = pf32bit; sxs = bmp->宽度; sys = bmp->高度; 如果（mxs）gxs = sxs / mxs;否则gxs = 1; 如果（mys）gys = sys / mys;否则gys = 1; } void bmp_load（AnsiString file）//从图像初始化游戏（必须已调整地图大小） { _redraw = true; //加载文件 bmp-> LoadFromFile（file）; bmp_resize（）; //转换为地图 int x，y; DWORD * p，c; 代表（y = 0; y< mys; y ++）代表（p =（DWORD *）bmp-> ScanLine [（y * gys）+（gys> 1）]，x ＝ 0； x ＝ mxs； x ++） {c = p [（x * gxs）+（gxs> 1）+4]& 0x00FFFFFF; //在中点附近（0 c =（（c>> 16）& 0x000000FF）// RGB-> BGR（文件具有比bmp更高的RGB顺序） |（（c< 16）& 0x00FF0000） |（c& 0x0000FF00）; map [y] [x] = c; c = p [（x * gxs）+（gxs> 1）]& 0x00FFFFFF; //中点 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）//处理鼠标 { _redraw = true; mx = x / gxs; my = y / gys; sh0 = sh; sh = s; bool q0 = sh0.Contains（ssLeft）; bool q1 = sh。包含（ssLeft）; if（（！q0）&（q1））{mx0 = mx; my0 = my; } //鼠标左键按下 if（（q0）&&（！q1））//鼠标左键按下（交换） { //如果有效坐标为 if（（（mx0> = 0）&&（mx0< mxs）&&（my0> = 0）&&（my0< mys））if（DWORD（map [my [] 0] [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; //交换储存格 map [my0] [mx0]& = 0x00FFFFFF; map [my0] [mx0] | = _ILoveHue_state_unsolved; //将它们设置为未解决的 map [my] [mx]& = 0x00FFFFFF; map [my] [mx] | = _ILoveHue_state_unsolved; map_solve（false）; //检查解决状态} //清除选择 mx0 = -1; my0 = -1; } } void draw（）//渲染游戏 { _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）对于（x0 = 0，x1 = gxs，x2 = gxs> 1，x = 0; x {c = map [y] [x]; bmp->画布->笔-> 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->画布->画笔-> Color = TColor（c& 0x00FFFFFF）; bmp-> Canvas-> Rectangle（x0，y0，x1，y1）; if（DWORD（c& 0xFF000000）！= _ ILoveHue_state_fixed） { r = 10; bmp->画布->笔-> Color = imap [y] [x]& 0x00FFFFFF; bmp->画布->画笔-> Style = bsClear; bmp-> Canvas-> Ellipse（x2-r，y2-r，x2 + r，y2 + r）; bmp->画布->画笔-> 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->画布->笔-> Color = c; bmp->画布->画笔->颜色= c; bmp-> Canvas-> Ellipse（x2-r，y2-r，x2 + r，y2 + r）; } } } if（render_mode == __ ILoveHue_render_graph） { bmp-> Canvas-> Pen-> Color = clBlack ; bmp->画布->画笔-> Color = clBlack; bmp->画布->矩形（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->画布->笔-> Color = clRed; （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->画布->笔-> Color = clGreen; （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->画布->笔-> Color = clBlue; （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）; } } } //求解器 void map_solve（bool _solve）//检查已求解状态，并尝试确定_solve为真 { _redraw = true; const int _thr = 10; //颜色比较阈值 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; //计算插值后的颜色到imap（所需的解） 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;打破; } （x1 = -1，xx = x; xx< mxs; xx ++）如果（DWORD（map [y] [xx]& 0xFF000000）== __ ILoveHue_state_fixed）{x1 = xx;打破; } for（y0 = -1，yy = y; yy> = 0; yy--）如果（DWORD（map [yy] [x]& 0xFF000000）== __ ILoveHue_state_fixed）{y0 = yy;打破; } 表示（y1 = -1，yy = y; yy< mys; yy ++）如果（DWORD（map [yy] [x]& 0xFF000000）== __ ILoveHue_state_fixed）{y1 = yy;打破; } c = 0; if（int（x0 | x1 | y0 | y1）> = 0） { //双线性插值 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; } //计算（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; } //求解器/检查器 if（_solve） { //处理所有未求解的像元（x = 0 ; x< mxs; x ++） for（y = 0; y< mys; y ++） if（DWORD（map [y] [x]& 0xFF000000）== _ ILoveHue_state_unsolved） //在（xx = 0; xx< mxs; xx ++）的未解决单元格中找到匹配项（yy = 0; yy< mys; yy ++） if（DWORD（map [yy ] [xx]& 0xFF000000）== __ ILoveHue_state_unsolved） if（rgbdist（map [yy] [xx]，imap [y] [x]） { / /交换（如果找到）c = map [yy] [xx]; map [yy] [xx] = map [y] [x]; map [y] [x] =（c& 0x00FFFFFF）| _ILoveHue_state_solved; } } } }赌博； // -------------------------------------------- ------------------------------- __fastcall TForm1 :: TForm1（TComponent *所有者）：TForm（所有者） { 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（）;画布-> Draw（0,0，gam.bmp）; } void __fastcall TForm1 :: FormResize（TObject * Sender）{如果（_update）返回； 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）; //如果（Key =='M'）{gam.render_mode ^ = 1; gam._redraw = true; } //交换渲染模式如果（Key == 115）gam.bmp-> SaveToFile（ screenshot.bmp）; // [F4]屏幕截图} // --------------------------------- ------------------------------------------ 它是BDS2006中的单个Form App，带有40ms计时器。因此，只需添加事件...即可忽略VCL渲染和窗口内容。重要的是类和其中的 solve（）函数。它用于正确的放置检查和求解（取决于 _solve bool）。这是输入图像 map.bmp 我没有编写适当的保存/加载状态函数，而是选择直接使用位图本身（浪费空间，但几乎无需编写代码）。 地图本身为 2D 32位 DWORD 数组，格式为 SSBBGGRR hex ，其中 SS 是单元格的标志（固定/已解决/未解决）。 此处是带有源代码的编译演示 如您所能（看不到），随着双线性插值的颜色与您的输入更加匹配，圆消失了。 程序期望的是7x9尺寸的网格，而图像的分辨率不是重要。颜色是从单元的中点（黑点）到稍微向右（图块的颜色）采样的。 要提高效率，您可以做两件事： 添加/使用包含未解决单元格的列表 而不是遍历整个地图，仅通过未解决的单元格列表进行迭代。 转换 T（N ^ 2） 通过三角形搜索搜索到 T（（N ^ 2）/ 2） 这仍然是 O（N ^ 2），但是恒定时间更短。 使用3D RGB LUT表 对于大型网格，您可以创建32K条目 3D LUT 表以查找在 O（1）中搜索匹配的单元格。只需将RGB转换为15位颜色并使用 DWORD LUT [32] [32] [32]; 其中 LUT [r] [g] [b] = row +（column< ;< 16）; 这样您就可以知道每种颜色的放置位置。所有未使用的颜色均设置为 0xFFFFFFFF 。下面是使用此技术实现类似目的的示例： 有效的gif /图像颜色量化？ 寻找变色[32] [代码中的[32] [32] ...粗略的15位颜色可能不足以实现此目的，因此可能需要更多的位（例如18位），导致256K条目仍可管理。 创建此 LUT 将花费 O（N）时间，但仅使用和维护它 O（1）时间。 I am currently working on a hobby project to automatically solve a puzzle from the popular mobile game I Love Hue. The game is available here.Basically, the whole premise of the game is that you're given a bunch of colored rectangular blocks organized in a grid. You can swap most of the blocks except for a few fixed blocks, which are marked by black dots. The object of the game is to swap the blocks around so you get a two-dimensional spectrum of color. The colors are sorted such that the color of each block is approximately the average of the colors around it. (Sorry, I don't know any color theory but there's probably a word for what I'm looking for.) Here's what a typical puzzle looks like:I have already been able to take screenshots through adb, extract the RGB matrix from the blocks and mark which blocks are "fixed". I'm having trouble with the actual algorithmic part of this problem.Here's what I've done so far:Converting the RGB to HSV and sorting the colors by hue in a one-dimensional list. This gives me a spectrum, but I do not know how to convert this result into two dimensions.Leaving the colors in RGB and attempting to work with a singular color. There's probably some multivariable calculus I could do here, but the difficulty lies in the fact that some colors share one or more of their RGB values. It would be necessary to consider all three colors.Using Euclidean distance to find the distance between each pair of colors. I understand that the final goal is to have this distance to be the smallest among adjacent colors, but the two-dimensional grid is making this more difficult.Using Euclidean distance, I have developed a metric for how ideal a certain grid is by looking at the Euclidean distance of the colors of adjacent blocks. However, I cannot find an efficient algorithm that can figure out the swaps necessary to get to an ideal state. 解决方案 If you have more solved images you could create RGB graphs plotso plot the 3D graph where x,y is pixel position and z is inspected color channel (R,G or B). From it you can determine some properties of the gradients. If the plot is a plane than all you need is just the normal (taken from 3 known cells). If it is curved surface depending on how many inflex points it got you can determine how big polynomial was used for it. From all this you can start solving this.I would start with something simple (assuming not too big gaps or fancy polynomials):Handle each color channel separately. I would use just the static tiles and interpolate the grid colors only from them. Something similar to:Interpolating 3D Coordinates between known missing time intervalsWithout seeing the R,G,B graphs I can not estimate which kind of interpolation you need. If the graphs are linear use bi-linear or linear interpolation. If not use higher degree polynomials.So fill in any grid cells that you can (has neighbors with known color). After this find the closest movable tile to computed color (if cell has all 3 channels interpolated) and place them (and set as static).Now just repeat the process until all the cells are computed.[Edit1 Dec 14 2017] some additional notes and stuffWas curious and got some time today so I gave it a shot. First I create the game in C++/VCL which took your image as input (cropped and resized). Then I sorted the tiles manually and plot the graphs:The White dots means tile is placed correctly (match the interpolated color). The colored circles around the dots are the interpolated colors (for visual comparison you need to zoom to see them).As you can see the R,G,B 3D plots looks linear so (bi)linear interpolation should be enough.If I tried just linear interpolation for rows only the solver solves the puzzle immediately. However When I coded the same for columns (more unknown cells between known ones) the solver started to make few incorrect placings (invalidating the whole stuff hence the wrong white dots).I Also tried HSL but after a while I throw it away due to hitting a wall because Hue can cross the 0 and 360 degree at any point which is not distinguishable from cases that did not cross. For that it would need some heuristics or cross correlation from neighboring solved areas and that would be too much coding for my taste. Without it the results where even worse then using RGB.So now I am thinking about either using bilinear interpolation or solve the short distance interpolations first and only then solve the rest ...[Edit2 Dec 14 2017] bilinear interpolationLooks like bilinear RGB interpolation solves all the issues. So if your board is enclosed with fixed cells it should work. If not you need to solve the board iteratively and then use the newly solved cells as new bound for the unsolved areas. Also I realized I got RGB reversed so I also repaired that :).Here the C++/VCL source for the game (It is not optimized at all)://$$---- 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 }//---------------------------------------------------------------------------It is a single Form App in BDS2006 with single 40ms Timer on it. So just add the events ... You can ignore the VCL rendering and window stuff. The important thing is the class and the solve() function in it. It is used for both correct placing check and for solving (depending on the _solve bool). This is the input image map.bmpI did not code appropriate save/load state functions instead I chose to use the bitmap itself directly (waste of space but almost no code effort).The map itself is 2D 32bit DWORD array with form of SSBBGGRR hex where SS is the flag of the cell (fixed/solved/unsolved).Here compiled demo with the source codeWin32 demoRead the readme.txt for more info. Here result after solving (pressing [S]):As you can (not) see the circles vanish as the bilinearly interpolated color matches more closely your input.Program is expecting grid of size 7x9 the resolution of image is not important. The color is sampled from mid point of cell (black dot) and slightly to the right (the tile color)To make this efficient you can make 2 things:add/use list containing unsolved cellsinstead of itearting over whole map iterate only through list of unsolved cells.convert T(N^2) searches to T((N^2)/2) by triangle searchThis is still O(N^2) however but the constant time is smaller.use 3D RGB LUT tablefor large grids you can create 32K entries 3D LUT table to find the searched matching cell in O(1). Simply convert RGB to 15 bit color and useDWORD LUT[32][32][32];where LUT[r][g][b]=row+(column<<16); Tis way you will know where each color is placed. All the unused colors set to 0xFFFFFFFF. Here an example of using this technique for similar purpose:Effective gif/image color quantization?Look for recolor[32][32][32] in the code... Of coarse 15bit color may be not enough for this purpose so may be you would need more bits like 18bit resulting in 256K entries which is still manageable.Creating this LUT will take O(N) time but using and maintaining it is only O(1) time. 这篇关于如何在二维中对颜色进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！