Just brainstorm with diagrams and hack it out

trandoductin · **Posted:** Sat Dec 09, 2023 10:09 am **(#1)**

I needed to fit some text inside a circle.

After cropping to content, I needed to know the maximum distance (furthest non-transparent pixel) from center of content.
Knowing this distance, I can scale it such that the result fits inside the circle (centered) with the furthest pixel from center at a certain inner radius.

For example if I want the furthest pixel from center of text to be 10% of circle's radius from border.

So, after drawing the above diagram(s), I wrote a function that
sweeps through possible say for example 16 rays from minimum which is half the height of text to maximum which is distance from center to a corner of text.
if it finds a larger distance from center where pixel isn't transparent it sets maximum distance to this value.
At the end, i get maximum distance of pixel furthest from center.

Code: Select all

def getmax_nontransparent(layer,jump):
    #this function sweeps around the circle starting from center of layer to find
    #furthest distance from center that isn't transparent
    #meant to be used for scaling logics that requires this max distance from center
    sweep_sections = 16.0 #16 lines sweep should be good enough
    offsetx,offsety = pdb.gimp_drawable_offsets(layer) #take offsets into account
    cx = offsetx + layer.width/2 #center
    cy = offsety + layer.height/2
    sweep_radius = ((layer.width/2)**2 + (layer.height/2)**2)**0.5 #to corner distance is the max radius that we sweep
    start_sweep = min(layer.width,layer.height)/2 #sweep from smaller dimension/2
    maxdist = -1
    for s in range(0,int(sweep_sections)): #section
        angle = 1.0*s/sweep_sections*2.0*math.pi
        for r in range(int(start_sweep),int(sweep_radius)): #radius
            r += max(jump,1)
            px = int(cx + math.cos(angle)*r)
            py = int(cy + math.sin(angle)*r)
            if px >=0 and px < layer.width and py >=0 and py < layer.height:
                num_channels,pixel = pdb.gimp_drawable_get_pixel(layer,px,py)
                if pixel[3]>0: #non transparent
                    if r > maxdist:
                        maxdist = r
    return maxdist        

this function takes a layer of content and a jump value (jump will tell it to jump by how many pixels while it's sweeping so that we can make the function faster by setting a jump value greater than 0 but it'll also be less accurate).

The above is a version that was used when I first wrote it.
The below is revised version which is about 10 times faster than previous version.
What could take previous version 3.137 seconds now takes 0.368 of a second with the below version.

Code: Select all

def getmax_nontransparent(layer,jump):
    #this function sweeps around the circle starting from center of layer to find
    #furthest distance from center that isn't transparent
    #meant to be used for scaling logics that requires this max distance from center
    sweep_sections = 16.0 #16 lines sweep should be good enough
    offsetx,offsety = pdb.gimp_drawable_offsets(layer) #take offsets into account
    cx = offsetx + layer.width/2 #center
    cy = offsety + layer.height/2
    sweep_radius = ((layer.width/2)**2 + (layer.height/2)**2)**0.5 #to corner distance is the max radius that we sweep
    start_sweep = min(layer.width,layer.height)/2 #sweep from smaller dimension/2
    maxdist = -1
    angle = 0
    incangle = math.pi*2.0/sweep_sections #use to to add for speed
    layerwidth = layer.width
    layerheight = layer.height
    for s in range(0,int(sweep_sections)): #section
        #angle += 1.0*s/sweep_sections*2.0*math.pi
        angle += incangle
        cos_angle = math.cos(angle) #for speed do this once outside of loop
        sin_angle = math.sin(angle)
        for r in range(int(start_sweep),int(sweep_radius)): #radius
            r += max(jump,0)
            px = int(cx + cos_angle*r)
            py = int(cy + sin_angle*r)
            if px >=0 and px < layerwidth and py >=0 and py < layerheight:
                #num_channels,pixel = pdb.gimp_drawable_get_pixel(layer,px,py)
                pixel = layer.get_pixel(px,py)
                if pixel[3]>0: #non transparent
                    if r > maxdist:
                        maxdist = r
    return maxdist

ofnuts · **Joined:** Oct 25, 2010 **Posts:** 4756

trandoductin wrote:

I needed to fit some text inside a circle.
[ Image ]

After cropping to content, I needed to know the maximum distance (furthest non-transparent pixel) from center of content.
Knowing this distance, I can scale it such that the result fits inside the circle (centered) with the furthest pixel from center at a certain inner radius.

For example if I want the furthest pixel from center of text to be 10% of circle's radius from border.

So, after drawing the above diagram(s), I wrote a function that
sweeps through possible say for example 16 rays from minimum which is half the height of text to maximum which is distance from center to a corner of text.
if it finds a larger distance from center where pixel isn't transparent it sets maximum distance to this value.
At the end, i get maximum distance of pixel furthest from center.

Code: Select all

def getmax_nontransparent(layer,jump):
    #this function sweeps around the circle starting from center of layer to find
    #furthest distance from center that isn't transparent
    #meant to be used for scaling logics that requires this max distance from center
    sweep_sections = 16.0 #16 lines sweep should be good enough
    offsetx,offsety = pdb.gimp_drawable_offsets(layer) #take offsets into account
    cx = offsetx + layer.width/2 #center
    cy = offsety + layer.height/2
    sweep_radius = ((layer.width/2)**2 + (layer.height/2)**2)**0.5 #to corner distance is the max radius that we sweep
    start_sweep = min(layer.width,layer.height)/2 #sweep from smaller dimension/2
    maxdist = -1
    for s in range(0,int(sweep_sections)): #section
        angle = 1.0*s/sweep_sections*2.0*math.pi
        for r in range(int(start_sweep),int(sweep_radius)): #radius
            r += max(jump,1)
            px = int(cx + math.cos(angle)*r)
            py = int(cy + math.sin(angle)*r)
            if px >=0 and px < layer.width and py >=0 and py < layer.height:
                num_channels,pixel = pdb.gimp_drawable_get_pixel(layer,px,py)
                if pixel[3]>0: #non transparent
                    if r > maxdist:
                        maxdist = r
    return maxdist        

this function takes a layer of content and a jump value (jump will tell it to jump by how many pixels while it's sweeping so that we can make the function faster by setting a jump value greater than 0 but it'll also be less accurate).

The above is a version that was used when I first wrote it.
The below is revised version which is about 10 times faster than previous version.
What could take previous version 3.137 seconds now takes 0.368 of a second with the below version.

Code: Select all

def getmax_nontransparent(layer,jump):
    #this function sweeps around the circle starting from center of layer to find
    #furthest distance from center that isn't transparent
    #meant to be used for scaling logics that requires this max distance from center
    sweep_sections = 16.0 #16 lines sweep should be good enough
    offsetx,offsety = pdb.gimp_drawable_offsets(layer) #take offsets into account
    cx = offsetx + layer.width/2 #center
    cy = offsety + layer.height/2
    sweep_radius = ((layer.width/2)**2 + (layer.height/2)**2)**0.5 #to corner distance is the max radius that we sweep
    start_sweep = min(layer.width,layer.height)/2 #sweep from smaller dimension/2
    maxdist = -1
    angle = 0
    incangle = math.pi*2.0/sweep_sections #use to to add for speed
    layerwidth = layer.width
    layerheight = layer.height
    for s in range(0,int(sweep_sections)): #section
        #angle += 1.0*s/sweep_sections*2.0*math.pi
        angle += incangle
        cos_angle = math.cos(angle) #for speed do this once outside of loop
        sin_angle = math.sin(angle)
        for r in range(int(start_sweep),int(sweep_radius)): #radius
            r += max(jump,0)
            px = int(cx + cos_angle*r)
            py = int(cy + sin_angle*r)
            if px >=0 and px < layerwidth and py >=0 and py < layerheight:
                #num_channels,pixel = pdb.gimp_drawable_get_pixel(layer,px,py)
                pixel = layer.get_pixel(px,py)
                if pixel[3]>0: #non transparent
                    if r > maxdist:
                        maxdist = r
    return maxdist

Looking at individual pixels is very slow. May I suggest a different technique, using a dichotomic search:

So you start with a max radius (this assumes a maximum distance is known in advance, but this will be at best half the size of the layer...) and a min radius (0).

* Compute the new radius, (min+max)/2
* Make a circle selection around the center, with this radius
* Call the histogram API to count the relevant pixels
* Depending on result, set min radius or max radius to the current radius
* Loop until min>=max

Worst case is calling the histogram log2(N) time, where N is the maximum radius (so even in a 2000px image, with an initial max radius of 1000px, you call the API only 10 times...)

trandoductin · **Posted:** Sat Dec 09, 2023 11:05 am **(#3)**

What you describe sounds like binary or is binary search.
I'll try to implement this as soon as I get back from shopping from Walmart.
Thanks a million ofnuts.

ofnuts · **Joined:** Oct 25, 2010 **Posts:** 4756

Binary searches are a subset of the dichotomic ones (a binary search is a dichotomic search on a sorted array).

ofnuts · **Joined:** Oct 25, 2010 **Posts:** 4756

Btw, if you want the smallest circle that includes all your pixels, there is also an algorithm for this, using the path from the selection (so you discover your true center...)

trandoductin · **Posted:** Sat Dec 09, 2023 12:48 pm **(#6)**

after ofnuts suggestion, I did this

Code: Select all

def getmax_nontransparent2(layer):
    offsetx,offsety = pdb.gimp_drawable_offsets(layer) #take offsets into account
    cx = offsetx + layer.width/2.0 #center
    cy = offsety + layer.height/2.0
    max_radius = ((layer.width/2.0)**2 + (layer.height/2.0)**2)**0.5 #corner distance (right triangle distance)
    min_radius = min(layer.width,layer.height)/2.0

    #do histogram once before loop so we have something to compare to
    pdb.gimp_ellipse_select(layer.image,cx-max_radius,cy-max_radius,max_radius*2.0,max_radius*2.0,CHANNEL_OP_REPLACE,TRUE,FALSE,0)
    mean,std_dev,median,pixels,count_previous_max,percentile = pdb.gimp_drawable_histogram(layer,HISTOGRAM_ALPHA,0.5,1.0)
    last_new_radius = 0
    while min_radius < max_radius:
        new_radius = int((min_radius+1+max_radius)/2)
        if new_radius == last_new_radius: #no improvement then break out of loop
            break
        pdb.gimp_ellipse_select(layer.image,cx-new_radius,cy-new_radius,new_radius*2.0,new_radius*2.0,CHANNEL_OP_REPLACE,TRUE,FALSE,0)
        mean,std_dev,median,pixels,count_current,percentile = pdb.gimp_drawable_histogram(layer,HISTOGRAM_ALPHA,0.5,1.0)
        if count_current < count_previous_max:
            min_radius = new_radius
        else:
            max_radius = new_radius
            count_previous_max = count_current #set it because we're setting max_radius (shrinking in our range check)
        last_new_radius = new_radius    
    pdb.gimp_selection_none(layer.image)    
    return new_radius

It takes about 1.841 sec on like a 5000px image/font but I like this one better because it's exhaustive and not estimated like my previous version.

Previous version has some hacks and didn't do binary logic properly so I copied some some logic from binary search and now it's cleaner

Code: Select all

def getmax_nontransparent2(layer):
    offsetx,offsety = pdb.gimp_drawable_offsets(layer) #take offsets into account
    cx = offsetx + layer.width/2.0 #center
    cy = offsety + layer.height/2.0
    max_radius = ((layer.width/2.0)**2 + (layer.height/2.0)**2)**0.5 #corner distance (right triangle distance)
    min_radius = min(layer.width,layer.height)/2.0

    #do histogram once before loop so we have something to compare to
    pdb.gimp_ellipse_select(layer.image,cx-max_radius,cy-max_radius,max_radius*2.0,max_radius*2.0,CHANNEL_OP_REPLACE,TRUE,FALSE,0)
    mean,std_dev,median,pixels,count_previous_max,percentile = pdb.gimp_drawable_histogram(layer,HISTOGRAM_ALPHA,0.5,1.0)
    last_new_radius = 0
    while min_radius < max_radius:
        new_radius = (min_radius+max_radius) // 2
        pdb.gimp_ellipse_select(layer.image,cx-new_radius,cy-new_radius,new_radius*2.0,new_radius*2.0,CHANNEL_OP_REPLACE,TRUE,FALSE,0)
        mean,std_dev,median,pixels,count_current,percentile = pdb.gimp_drawable_histogram(layer,HISTOGRAM_ALPHA,0.5,1.0)
        if count_current < count_previous_max:
            min_radius = new_radius+1
        else:
            max_radius = new_radius-1
            count_previous_max = count_current #set it because we're setting max_radius (shrinking in our range check)
    pdb.gimp_selection_none(layer.image)    
    return new_radius