确定文本宽度的算法

在我用未命名语言编写的程序中，我有一段宽度未知的文本，我所知道的只是该块文本的最大宽度。鉴于这些信息，我需要找出可能的最小宽度（假设我不能使用字符/字形的度量或字符数）。到目前为止，我只是有一个蛮力解决方案，它看起来像如下：确定文本宽度的算法

for (int i = .1; i < maxTextWidth; i += .1) 
{ 
     if (textFitsInGivenWidth(text, i)) 
     { 
      textWidth = i; 
      break; 
     } 
}

我想尝试和优化这是尽我所能。我的第一个想法是使用二进制搜索，但我无法以正确的方式执行此操作（并且我不确定是否有可能）。有没有人有任何建议，我可以在这里做什么来改善运行时间，只使用我在上述解决方案中给出的内容？

来源

2012-08-03 Ser Pounce

二进制搜索的确是答案。

http://en.wikipedia.org/wiki/Binary_search_algorithm

的整数二进制搜索，它可以是：

minW=0, maxW=maxTextWidth 
while(minW<=maxW){ 

    mid=(minW+maxW)/2; 
    if (textFitsInGivenWidth(text, mid)){ 
    maxW=mid-1; 
    }else{ 
    minW=mid+1; 
    } 
} 
textWidth=minW

的想法是，如果你有textFitsInGivenWidth(text, mid) == True，

，那么你必须有textFitsInGivenWidth(text, i) == True所有i>=mid，

如果它是假的，那么你有textFitsInGivenWidth(text, i) == False所有i<=mid

所以每次我们检查要检查的间隔的中间，并将间隔减半。的时间是O（logN）的，其中，N = maxTextWidth

更新：对于浮体支撑件，见下面的例子：

float minW=0, maxW=maxTextWidth 
while(1){ 
    if (maxW-minW<0.05) 
    break; 
    float mid=(minW+maxW)/2; 
    if (textFitsInGivenWidth(text, mid)){ 
    maxW=mid; 
    }else{ 
    minW=mid; 
    } 
} 

textWidth=minW

和获得的0.1精度，简单地改变最后一行：

textWidth=int(minW*10)/10.0

来源

2012-08-03 07:34:14 lavin

谢谢先生。如果我正在处理浮点数，这是否会以同样的方式工作？例如，如果mid是浮动的，并且我想将其设置为最接近的.1而不是1，那么我是否会简单地将中间值更改为浮点值，然后从if中减去并将其加1。 – 2012-08-03 07:59:15

如果它只是1和.1的区别，你可以简单的改变代码：'... maxW = maxTextWidth * 10; ... if（textFitsInGivenWidth（text，mid/10.0））... textWidth = minW/10.0;' – lavin 2012-08-03 08:20:14

ps：我不认为更改1到.1将工作。要获得完整的浮动支持，请查看帖子中的更新。 – lavin 2012-08-03 08:31:51

确定文本宽度的算法

回答

相关问题