Word wrap text to fit an rectangle of certain ratio (not size)

Anyone know of an algorithm that can break text at word boundaries to f开发者_StackOverflowit a rectangle of a certain approximate ratio - e.g. 60:40 (width:height)?

Note this is not just width (e.g. 80 chars or 600px etc) and an arbitrary height which rules out every word-wrapping algorithms I can find.

Bonus points for javascript but this is more about the algorithm than the implementation.

This could do it:

int lineHeight := getHeightOfTextLine()
int lines := 0
do {
  lines += 1
  int width = lines * lineHeight * ratio
  String wrappedText := break(input, width)
} while(getNumberOfLines(wrappedText) != lines)

Starting with one line I simply test for each height (multiples of lineHeight) if I have a rectangle with a given ration that can hold the text. If breaking the text at the calculated width leads to a String with more lines than allowed (for the run) continue, otherwise I have a solution.

Well, if you start with an array of height & width for each word then you'd need to run through several possibilities until you find the minimum waste (space between words and) for given width:height

Normally you would start with

ratio := 6 / 4
noOfLines := totalWidth / ( ratio * lineHeight )
targetLineWidth := totalWidth / noOfLines

and then try to determine after which words you'd put line breaks to minimize space between words.

If you try to minimize space in each line you might end up with extra space on the last line. If you first make sure that even the last line is evenly spread out then you should be fine examining just a few variations.

EDIT
If you want to mess with exact font metrics, this q&a looks useful.

Here's a Python implementation, using textwrap and Pillow, that also keeps existing linebreaks:

from PIL import Image, ImageDraw
import textwrap

def get_text_with_linebreaks_to_fit_ratio(input_text, target_ratio):
    width_in_nchar = 1 
    placeholder_img = Image.new('RGB', (1, 1), (255, 255, 255))
    placeholder_img_D = ImageDraw.Draw(placeholder_img)
    intermediary_text = input_text.split("\n")   # splits on newlines

    while True:
        intermediary_text2 = [textwrap.wrap(element, width_in_nchar) for element in intermediary_text] # for each paragraph, cut it with a width of width_in_nchar
        wrapped_text = [item for sublist in intermediary_text2 for item in sublist]   # flattening the output list
        wrapped_text_as_string = "".join([el+"\n" for el in wrapped_text])

        a, b = placeholder_img.multiline_textsize(wrapped_text_as_string)
        if a/b > target_ratio:
            newest_ratio = a/b
            break
        old_ratio = a/b
        width_in_nchar +=1

    if newest_ratio - target_ratio> old_ratio - target_ratio: # if the last ratio we got is farther from target ratio than the previous ratio
        width_in_nchar -=1 # then we go one step back
        intermediary_text2 = [textwrap.wrap(element, width_in_nchar) for element in intermediary_text] 
        wrapped_text = [item for sublist in intermediary_text2 for item in sublist]  
        wrapped_text_as_string = "".join([el+"\n" for el in wrapped_text])

    return {"as_string" : wrapped_text_as_string, "as_list" : wrapped_text}

And then to see the output:

input_text = """Lorem ipsum dolor sit amet, consectetur adipiscing elit. In pellentesque pharetra ex, at varius sem suscipit ac. Suspendisse luctus condimentum velit a laoreet. Donec dolor urna, tempus sed nulla vitae, dignissim varius neque. Etiam non vulputate diam. Nullam luctus nisi mauris, sit amet feugiat nisi dapibus in. Fusce in interdum nisi. Nullam mattis a odio non interdum.

Sed accumsan laoreet pretium. Nulla facilisi. Morbi in eros suscipit, commodo turpis id, dignissim lorem. Maecenas quis urna auctor, rutrum velit vel, efficitur sem. Donec vulputate viverra justo a accumsan. Phasellus posuere est consectetur, tincidunt lorem volutpat, porttitor erat. Sed at ipsum euismod eros blandit vestibulum.

Integer a auctor quam. Mauris scelerisque sapien quis elementum euismod. Curabitur sed est tortor. Nullam eget tristique purus, eget venenatis enim. Etiam sem quam, lacinia at quam sed, laoreet ultrices mauris. Nunc aliquam dui iaculis pretium fringilla. Maecenas in ante vel libero eleifend condimentum. Vivamus at venenatis libero. Pellentesque sagittis tristique risus a molestie. Fusce vitae leo sed mauris ultricies tincidunt venenatis in lacus. Integer finibus arcu porttitor, viverra massa in, bibendum lacus.

Donec gravida nisi in facilisis sollicitudin. In aliquam vulputate velit. Pellentesque semper vitae justo efficitur tincidunt. Maecenas sit amet arcu eget arcu congue lobortis quis quis massa. Sed fringilla iaculis augue sit amet sodales. Ut at diam id lorem dapibus dignissim non eu tellus. Morbi accumsan, massa cursus eleifend facilisis, sapien ligula fringilla augue, quis bibendum neque lorem tristique est. Aenean sed augue at elit condimentum lacinia quis eu lacus. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas.

Nullam quis nisl lacinia nulla congue eleifend vitae id neque. Quisque lacinia nulla in dui fermentum, non ullamcorper massa rutrum. Vestibulum varius blandit facilisis. Aenean bibendum lorem ac sem aliquet ultrices. Nam nunc metus, auctor vel metus ac, interdum vestibulum magna. Vivamus facilisis vulputate ligula. Interdum et malesuada fames ac ante ipsum primis in faucibus. Mauris volutpat tristique libero eu auctor. Ut ac vestibulum eros.
"""

wrapped_text_as_string = get_text_with_linebreaks_to_fit_ratio(input_text, 16/9)["as_string"]

img_width = 1000
img_height = 1000
img = Image.new('RGB', (img_width, img_height), (255, 255, 255))
img_D = ImageDraw.Draw(img)
img_D.multiline_text((10, 10), wrapped_text_as_string, fill=(0,0,0))
img.save("test_img.jpeg", 'jpeg', optimize=True, quality = 200)