Best way to calculate the index of a character in a string given a pixel offset

Related question: Getting a string index based on a pixel offset

I know this is close to that question, but this isn't asking how to do it directly, it's asking how to fake it best.

I am implementing my own text box for Windows Forms (because RichTextBox sucks) and I am trying to find the best way to, given strings that have been drawn on the screen, calculate what character the mouse is over. The problem is that characters can b开发者_运维技巧e variable-width.

I have come up with two possibilities:

1. Do Graphics.MeasureCharacterRange every time the mouse moves in a binary search fashion on the line that the mouse is over (as suggested in the question linked at the top)

2. Keep a list of the offset of every character of every line.

(1) Will have bad performance, and

(2) will be memory-inefficient plus make typing a character become a O(n) operation (because you have to adjust the offset of every character after it) plus impossible to do precisely because Graphics.MeasureCharacterRange isn't precise (it returns one value for one character, another value for another character, and a totally different value [that does not equal the two previous values added together] for both of them together in one string. E.g. W will be 16 pixels wide and f will be 5 pixels wide, but Wf is 20 pixels wide. Those numbers are from an actual test.).

So I am looking for a better strategy to do this, preferably one that requires minimal space and O(1) computational complexity (though I will gladly trade off a little memory efficiency for speed efficiency).

I don't think you have to do O(1). O(1) is assuming that every additional character has an affect on ALL previous characters, which it would not. At best I would see an O(1) for each word which should be crazy fast. It sounds like what you need is a way to store; 1 the location of each word, 2 each unique word, and 3 the width of each letter in the word. This would significantly reduce the storage and increase look up speed. Maybe something like:

IEnumerable<TextLocation> TextLocations = ...;

internal class TextLocation
{
    public RectF BoundingBox { get; set; }  //this is relative to the textbox
    public TextWord TextWord { get; set; }
}

internal class TextWord
{
    public string Text { get; set; }
    public IEnumerable<LetterInfo> Letters { get; set; }
}

internal class LetterInfo
{
    public char Letter { get; set; }
    public float left { get; set; }  //these would be relative to the bounding box
    public float right { get; set; } //not to the textbox
}

Then you might be able to do something like

var tl = TextLocations.FirstOrDefault(x => x.BoundingBox.Left < Mouse.X 
                                           && x.BoundingBox.Right > Mouse.X
                                           && x.BoundingBox.Top < Mouse.Y
                                           && x.BoundingBox.Bottom > Mouse.Y)

if (tl != null)
{
    //tl.TextWord.Text is the Word ("The", "Lazy", "Dog"...)

    var letter = tl.TextWord.Letters
                   .FirstOrDefault(x => Mouse.x - tl.BoundingBox.left > x.left
                                        Mouse.x - tl.BoundingBox.left < x.right);

    if (letter != null)
    {
        // you get the idea
    }                              
}