62
\$\begingroup\$

Given an image that has only black and white pixels and an (x,y) location that's a white pixel, color the white pixels based on their minimal Manhattan distance from (x,y) in a path that only involves traversing other white pixels.

The hue of the colored pixels must be proportional to their distance from (x,y), so the pixel at (x,y) will have a hue of 0° (pure red) and the pixels farthest away from (x,y) will have a hue of 360° (also red), with the other hues blending seamlessly and linearly in between. The saturation and value must both be 100%.

If a white pixel is not connected to (x,y) through other white pixels then it must remain white.

Details

  • The input will consist of the file name of the image or the raw image data, plus the x and y integers.
  • The output image may be saved to a file or piped raw to stdout in any common image file format, or simply displayed.
  • The x value is 0 on the leftmost pixels, and increases going right. The y value is 0 in the topmost pixels and increases going down. (x,y) will always be in the image bounds.
  • Both full programs and functions are allowed.

The shortest code in bytes wins.

Examples

All these images have been downsized to save space. Click them to view at full size.

Input image:

example 1 input

(x,y) = (165,155) and (x,y) = (0,0)

example 1 output A example 1 output B


Input image and output with (x,y) = (0,0):

example 5 input example 5 input A


Input image and output with (x,y) = (600,350):

example 2 input example 2 output


Input image and output with (x,y) = (0,0):

example 3 input example 3 output


Input image and output with (x,y) = (0,0):

example 4 input example 4 output


Optional -30% bonus: use Euclidean distance. A suggestion for your algorithm is as follows (general outline):

  1. Have a start pixel.
  2. Flood-fill from that pixel.
  3. For every pixel reached in the flood fill,
  4. Move from the start pixel to that pixel in half-unit steps, in a straight line.
  5. At each step, apply int() to the x and y coordinates. If the pixel at these coordinates is black, stop. Otherwise, continue. (This is a line-of-sight method.)
  6. Any reached pixel that borders a white pixel and/or a pixel that was previously labeled with a significantly higher distance (i.e., +10) becomes a start pixel.

In a more meta sense, this algorithm spreads out to every pixel reachable in a straight line from start/already-colored pixels, then "inches" around edges. The "significantly higher distance" bit is intended to speed up the algorithm. Honestly, it doesn't really matter how you implement Euclidean distance, it just has to look pretty much like this.

This is what the first example looks like with Euclidean distance, using the algorithm above:

Input image and (x,y) = (165,155)

example 1 input enter image description here


Many thanks to Calvin'sHobbies and trichoplax for helping write this challenge! Have fun!

\$\endgroup\$
6
  • 7
    \$\begingroup\$ I don't plan on golfing it but I made a Javascript version where you can mouse-over the image and the colors update instantly. The test images here are too big for it to run fast so I'd advise trying smaller images like this or this. \$\endgroup\$ Nov 20, 2015 at 2:42
  • \$\begingroup\$ This is awesome! I suspect it is too efficient to be a good base for a golfed version=) \$\endgroup\$
    – flawr
    Nov 20, 2015 at 15:42
  • 2
    \$\begingroup\$ Mazes are so much easier to solve when they are colored like this! \$\endgroup\$
    – mbomb007
    Nov 20, 2015 at 18:12
  • \$\begingroup\$ The last example is really beautiful. Is the input image just noise? \$\endgroup\$
    – dylnan
    Dec 14, 2017 at 23:26
  • \$\begingroup\$ @dylnan: If you're talking about the example right before the bonus, that's actually a maze. You can click on it to see it at full size. \$\endgroup\$ Dec 15, 2017 at 0:07

6 Answers 6

34
\$\begingroup\$

Matlab, 255 245 231 bytes

This expects the image name first, then y and then x.

I=@input;i=imread(I('','s'));[r,c]=size(i);m=zeros(r,c);m(I(''),I(''))=1;M=m;d=m;K=[1,2,1];for k=1:r*c;d(m&~M)=k;M=m;m=~~conv2(m,K'*K>1,'s');m(~i)=0;end;z=max(d(:));v=[1,1,3];imshow(ind2rgb(d,hsv(z)).*repmat(m,v)+repmat(~d&i,v),[])

I implemented the flood filling (or 'dijkstra for 4-neighbourhoods' if you want) roughly by first creating a mask where the seed pixel is set to 1 and with a distance accumulator (both of the size of the image) and then repeating following steps:

  • convolute the mask with a 4 neighbourhood kernel (this is the very inefficient part)
  • set all nonzero pixels of the mask to 1
  • set all the black pixels of the image to zero
  • set all values in the accumulator where the mask has changed in this step to k
  • increase k
  • repeat until there are no more changes in the mask (I actually do not check this condition, but just use the number of pixels in the image as an upper bound, which is usually a very bad upper bound, but this is codegolf=)

This leaves us with the manhattan distances of every pixel to the seed pixel in the distance accumulator. Then we create a new image by going throu the given range of colours and map the "first" hue to the value zero and the "last" hue to the maximal distance.

Examples

enter image description here

enter image description here

enter image description here

enter image description here

As a bonus, here a pretty picture of how the distance gets calculated. brighter = farther away.

enter image description here

\$\endgroup\$
8
  • 3
    \$\begingroup\$ This is the kind of stuff I'd want to print out for my daughter to draw on. \$\endgroup\$
    – rayryeng
    Nov 19, 2015 at 19:54
  • \$\begingroup\$ @rayryeng The templates are El'endia Starman's work, not mine=) \$\endgroup\$
    – flawr
    Nov 19, 2015 at 20:04
  • \$\begingroup\$ You still put colour to the images :D. You did the last step. \$\endgroup\$
    – rayryeng
    Nov 19, 2015 at 20:06
  • 4
    \$\begingroup\$ I'm impressed. I could barely understand the challenge lol \$\endgroup\$
    – zfrisch
    Nov 19, 2015 at 20:30
  • \$\begingroup\$ Honestly, what I want to use it for is creating landscapes. \$\endgroup\$
    – corsiKa
    Nov 19, 2015 at 21:13
3
\$\begingroup\$

Blitz 2D/3D, 3068 * 0.7 = 2147.6

This is the reference implementation for the Euclidean algorithm, golfed.

image=LoadImage("HueEverywhere_example1.png")
Graphics ImageWidth(image),ImageHeight(image)
image=LoadImage("HueEverywhere_example1.png")
x=0
y=0
w=ImageWidth(image)
h=ImageHeight(image)
Type start
Field x,y
Field dis#
Field nex.start
End Type
Type cell
Field x,y
Field dis#
End Type
Type oldCell
Field x,y
Field dis#
End Type
initCell.start=New start
initCell\x=x
initCell\y=y
initCell\dis=1
Dim array#(w,h)
imgBuff=ImageBuffer(image)
LockBuffer(imgBuff)
s.start=First start
colr=col(0,0,0)
colg=col(0,0,1)
colb=col(0,0,2)
newcol=colr*256*256+colg*256+colb
WritePixelFast(s\x,s\y,newcol,imgBuff)
While s<>Null
c.cell=New cell
c\x=s\x
c\y=s\y
c\dis=s\dis
While c<>Null
For dy=-1To 1
For dx=-1To 1
If dx*dy=0And dx+dy<>0
nx=c\x+dx
ny=c\y+dy
ndis#=s\dis+Sqr#((nx-s\x)*(nx-s\x)+(ny-s\y)*(ny-s\y))
If nx >= 0And nx<w And ny >= 0And ny<h
If KeyHit(1)End
pixcol=ReadPixelFast(nx,ny,imgBuff)
If pixcol<>-16777216
If array(nx,ny)=0Or ndis<array(nx,ny)
check=1
steps=Ceil(dis)*2
For k=0 To steps
r#=k*1./steps
offx#=Int(s\x+(c\x-s\x)*r)
offy#=Int(s\y+(c\y-s\y)*r)
pixcol2=ReadPixelFast(offx,offy,imgBuff)
If pixcol2=-16777216
check=0
Exit
EndIf
Next
If check
array(nx,ny)=ndis
newCell.cell=New cell
newCell\x=nx
newCell\y=ny
newCell\dis=ndis
EndIf
EndIf
EndIf
EndIf
EndIf
Next
Next
o.oldCell=New oldCell
o\x=c\x
o\y=c\y
o\dis=c\dis
Delete c
c=First cell
Wend
For o.oldCell=Each oldCell
bordersWhite=0
For dy=-1To 1
For dx=-1To 1
If dx<>0Or dy<>0
nx=o\x+dx
ny=o\y+dy
If nx>=0And nx<w And ny>=0And ny<h
pixcol=ReadPixelFast(nx,ny,imgBuff)
If (pixcol=-1And array(nx,ny)=0)Or array(nx,ny)>o\dis+9
bordersWhite=1
Exit
EndIf
EndIf
EndIf
Next
If bordersWhite Exit
Next
If bordersWhite
ns.start=New start
ns\x=o\x
ns\y=o\y
ns\dis=o\dis
s2.start=First start
While s2\nex<>Null
If ns\dis<s2\nex\dis
Exit
EndIf
s2=s2\nex
Wend
ns\nex=s2\nex
s2\nex=ns
EndIf
Delete o
Next
EndIf
s2=s
s=s\nex
Delete s2
Wend
maxDis=0
For j=0To h
For i=0To w
If array(i,j)>maxDis maxDis=array(i,j)
Next
Next
For j=0To h
For i=0To w
dis2#=array(i,j)*360./maxDis
If array(i,j) <> 0
colr=col(dis2,0,0)
colg=col(dis2,0,1)
colb=col(dis2,0,2)
newcol=colr*256*256+colg*256+colb
WritePixelFast(i,j,newcol,imgBuff)
EndIf
Next
Next
UnlockBuffer(imgBuff)
DrawImage image,0,0
Function col(ang1#,ang2#,kind)
While ang1>360
ang1=ang1-360
Wend
While ang1<0 
ang1=ang1+360
Wend
While ang2>180
ang2=ang2-360
Wend
While ang2<-180
ang2=ang2+360
Wend
a3#=ang2/180.
If ang1>300
diff#=(ang1-300)/60.
r=255
g=0
b=255*(1-diff)
ElseIf ang1>240
diff#=(ang1-240)/60.
r=255*diff
g=0
b=255
ElseIf ang1>180
diff#=(ang1-180)/60.
r=0
g=255*(1-diff)
b=255
ElseIf ang1>120
diff#=(ang1-120)/60.
r=0
g=255
b=255*diff
ElseIf ang1>60
diff#=(ang1-60)/60.
r=255*(1-diff)
g=255
b=0
Else
diff#=(ang1-00)/60.
r=255
g=255*diff
b=0
EndIf
If a3>0
r2=r+a3*(255-r)
g2=g+a3*(255-g)
b2=b+a3*(255-b)
Else
r2=r+a3*r
g2=g+a3*g
b2=b+a3*b
EndIf
If r2>255
r2=255
ElseIf r2<0
r2=0
EndIf
If g2>255
g2=255
ElseIf g2<0
g2=0
EndIf
If b2>255
b2=255
ElseIf b2<0
b2=0
EndIf
If kind=0
Return r2
ElseIf kind=1
Return g2
ElseIf kind=2
Return b2
Else
Return 0
EndIf
End Function

Actually, I kinda hate how unreadable this is compared to the original. (Which is, incidentally, 5305 bytes.) Actually, I could lop off quite a few more bytes by using one-character variable names for everything, but this is kinda ridiculous enough already. And it's not winning any time soon. :P

\$\endgroup\$
2
\$\begingroup\$

C++ / SFML : 1271 1235 1226 bytes

-36 bytes thanks to user202729 -9 bytes thanks to Zacharý

#include<SFML\Graphics.hpp>
#include<iostream>
#define V std::vector
#define P e.push_back
#define G(d,a,b,c) case d:return C(a,b,c);
#define FI(r,s)(std::find_if(e.begin(),e.end(),[&a](const T&b){return b==T{a.x+(r),a.y+(s),0};})!=e.end())
using namespace sf;using C=Color;struct T{int x,y,c;bool operator==(const T&a)const{return x==a.x&&y==a.y;}};int max(V<V<int>>&v){int m=INT_MIN;for(auto&a:v)for(auto&b:a)m=b>m?b:m;return m;}C hsv2rgb(int t){int ti=t/60%6;float f=t/60.f-ti,m=(1.f-f)*255,n=f*255;switch(ti){G(0,255,n,0)G(1,m,255,0)G(2,0,255,n)G(3,0,m,255)G(4,n,0,255)G(5,255,0,m)default:throw std::exception();}}void r(Image&a,int x,int y){auto d=a.getSize();V<V<int>>m(d.x,V<int>(d.y));int i=0,j,c=0,t;for(;i<d.y;++i)for(j=0;j<d.x;++j)m[j][i]=a.getPixel(j,i)==C::Black?-1:0;V<T>e{{x,y,1}};while(e.size()){V<T>t=std::move(e);for(auto&a:t){m[a.x][a.y]=a.c;if(a.x>0&&m[a.x-1][a.y]==0&&!FI(-1,0))P({a.x-1,a.y,a.c+1});if(a.y>0&&m[a.x][a.y-1]==0&&!FI(0,-1))P({a.x,a.y-1,a.c+1});if(a.x<m.size()-1&&m[a.x+1][a.y]==0&&!FI(1,0))P({a.x+1,a.y,a.c+1});if(a.y<m[0].size()-1&&m[a.x][a.y+1]==0&&!FI(0,1))P({a.x,a.y+1,a.c+1});}}c=max(m)-1;for(i=0,j;i<d.y;++i)for(j=0;j<d.x;++j)if(m[j][i]>0)a.setPixel(j,i,hsv2rgb(360.f*(m[j][i]-1)/c));}

The sf::Image parameter is also the output ( will be modified ). You can use it like that :

sf::Image img;
if (!img.loadFromFile(image_filename))
    return -1;

r(img, 0, 0);

if (!img.saveToFile(a_new_image_filename))
    return -2;

The first parameter is the image input ( and output ), the second and third parameters are the x and y parameter where it needs to start

\$\endgroup\$
4
  • \$\begingroup\$ The switch case seems so wasteful that probably a macro definition would be useful... Also is the ` ` at setPixel(j, i,hsv2 and FI(xm,ym) (std::find_if really necessary? \$\endgroup\$
    – DELETE_ME
    Dec 16, 2017 at 5:04
  • \$\begingroup\$ You can remove the space between G(d,a,b,c) and case d:. Also, the space between case d: and return C(a,b,c) is unneeded as well. (b>m?b:m) doesn't require the parentheses, and (t/60)%6 => t/60%6 by order of operations. \$\endgroup\$
    – Adalynn
    Dec 17, 2017 at 16:00
  • \$\begingroup\$ You should probably also rename xm and ym to shorter variable names \$\endgroup\$
    – Adalynn
    Dec 18, 2017 at 13:08
  • \$\begingroup\$ I think it's possible to remove the space between G(d,a,b,c)and case, FI, ti, and hsv2rgb can each be replaced with a shorter name. \$\endgroup\$
    – Adalynn
    Dec 18, 2017 at 19:12
2
\$\begingroup\$

Matlab with DIPimage, 118 bytes - 30% = 82.6

function F(f,x,y),a=readim(f);m=a{1}>0;s=m|1;s(x,y)=0;h=gdt(s,[],m);n=~isinf(h);a(n)=lut(h(n),255*hsv(fix(max(h(n)))))

DIPimage has a function to compute Euclidean geodesic distance transform (gdt). It uses the Fast Marching algorithm, which produces a very reasonable approximation to Euclidean distances. See the docs.

DIPimage automatically displays the image

I'm using the idea from flawr's answer to create a colormap using hsv.

output of code above for one of the test images

\$\endgroup\$
1
\$\begingroup\$

C++, 979 969 898 859 848 bytes

#include<cstdio>
#include<cstdlib>
#define K 400
#define L 400
#define M (i*)malloc(sizeof(i))
#define a(C,X,Y)if(C&&b[Y][X].c){t->n=M;t=t->n;b[Y][X].d=d+1;t->n=0;t->c=X;t->d=Y;}
#define A(n,d)case n:d;break;
#define F fgetc(f)
#define W(A,B) for(A=0;A<B;A++){
struct i{int c;int d;int v;i*n;}b[L][K]={0},*h,*t;float m=0;int main(){FILE*f=fopen("d","r+b");int x,y,d=0;W(y,L)W(x,K)b[y][x].c=F<<16|F<<8|F;}}rewind(f);x=165,y=155;h=M;h->c=x;h->d=y;b[y][x].d=d;t=h;while(h){i*p=b[h->d]+h->c;if(p->v)h=h->n;else{p->v=1;x=h->c;y=h->d;d=p->d;m=d>m?d:m;a(x>0,x-1,y)a(x<K-1,x+1,y)a(y>0,x,y-1)a(y<L-1,x,y+1)}}W(y,L)W(x,K)i p=b[y][x];unsigned char n=-1,h=p.d/(m/n),R=h%43*6,Q=n*(n-(n*R>>8))>>8,t=n*(n-(n*(n-R)>>8))>>8,r,g,b;switch(h/43){A(0,n,t,0)A(1,Q,n,0)A(2,0,n,t)A(3,0,Q,n)A(4,t,0,n)A(5,n,0,Q)}d=h?r|g<<8|b<<16:p.c?-1:0;fwrite(&d,1,3,f);}}}
  • Input: RGB data file (contained in file: d)
  • Output: RGBA RGB data file (outputted in file: d)
  • Example: convert -depth 8 -size "400x400" test.png d.rgb && mv -f d.rgb d && g++ -o test main.c && ./test
  • NOTE: the image size and start are controlled at a source level, if this is an issue add 50 bytes or something -- I just didn't care to change it to be honest.

Not exactly a direct "ungolf" but this was a C prototype I mocked up first:

#include "stdio.h"
#include "stdlib.h"
 
struct i{
    unsigned int c;
    int d;
    int v;
}b[400][400]={0};

typedef struct q{
    int x;
    int y;
    struct q *n;
}q;
q *qu;
q *t;
float m=0;
int get_dist(int x, int y)
{
    int d = 0;
    
}

void flood(int x,int y,int d){
    qu=malloc(sizeof(q));
    qu->x=x;qu->y=y;b[y][x].d=d;
    t=qu;
    while(qu){
        struct i *p = &b[qu->y][qu->x];
        if(p->v){qu=qu->n; continue;}
        p->v=1;x=qu->x;y=qu->y;d=p->d;
        #define a(C,X,Y) if(C&&b[Y][X].c){t->n=malloc(sizeof(q));t=t->n;b[Y][X].d=d+1;t->n=0;t->x=X;t->y=Y;}
        a(x>0,x-1,y);
        a(x<399,x+1,y);
        a(y>0,x,y-1);
        a(y<399,x,y+1);
        m=p->d>m?p->d:m;
    }
}

unsigned int C(int h)
{
    int r=0,g=0,b=0;
    int s=255,v=255;
    unsigned char R, qq, t;

    R = h%43*6; 

    qq = (v * (255 - ((s * R) >> 8))) >> 8;
    t = (v * (255 - ((s * (255 - R)) >> 8))) >> 8;

    switch (h / 43){
        case 0: r = v; g = t; break;
        case 1: r = qq; g = v; break;
        case 2: g = v; b = t; break;
        case 3: g = qq; b = v; break;
        case 4: r = t; b = v; break;
        case 5: r = v; b = qq; break;
    }

    return r|(g<<8)|(b<<16)|255<<24;
}

#define F fgetc(f)
int main()
{
    FILE *f=fopen("d", "r+b");
    for(int y=0; y<400; y++){
        for(int x=0; x<400; x++){
            b[y][x].c = (F<<24)|(F<<16)|(F<<8);
        }
    }
    rewind(f);
    flood(165,155,1);
    m/=255.f;
    for(int y=0; y<400; y++){
        for(int x=0; x<400; x++){
            struct i p = b[y][x];
            unsigned int h = C(p.d/m);
            int o = p.c?-1:255<<24;
            if(p.d)fwrite(&h,4,1,f);
            else fwrite(&o,4,1,f);
        }
    }
}

Many concepts remain similar, but there are certainly a myriad of tiny changes. To compile that as C you do need to use C11 (C99 will probably work but I only strictly tested in C11).
I quite enjoyed this challenge, thanks for giving me the idea to try something new :).
Edit: Golf'd a bit better.
Edit2: Merged two structs so my pixel struct and queue are the same, bit more macro abuse, and reflowed uses of 255 such that it can be defined as -1 when defining a series of unsigned chars, and lastly removed a function call.
Edit3: Reused a few more variables, operator precedence tweaks, and output converted to RGB saving the alpha channel
Edit4: I think I am done with this now, some pointer arithmetic changes and slight control flow tweaks.

\$\endgroup\$
1
0
\$\begingroup\$

Python 3 and matplotlib, 251 227 bytes

from pylab import*
def f(i,p):
 h,w,_=i.shape;o=ones((h,w))/0;q=[p+[0]]
 while q:
  x,y,d=q.pop(0)
  if w>x>=0and h>y>=0and i[y,x,0]:o[y,x]=d;i[y,x]=0;d+=1;q+=[[x-1,y,d],[x+1,y,d],[x,y-1,d],[x,y+1,d]]
 imshow(i);imshow(o,'hsv')

The input is an MxNx3 numpy array as returned by matplotlib's imread() function. The input is modified by the function so it should be copied beforehand. It displays the image automatically if matplotlib is in "interactive" mode; otherwise a call to show() should be added for another 7 bytes.

The output is created by first displaying the original image and then displaying the rainbow image overtop of it. Matplotlib conveniently treats inf and nan as transparent so the black and white image shows through.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.