縮放DrawingVisuals算法

Question

我試圖實現一個算法，它會找到儘可能最好的縮放係數和最佳可能的角度來定位圖形，使其不與容器的邊緣重疊，並且需要最佳角度（由數字儘可能寬的角度定義）。我使用DrawingVisual來表示該數字。

我心裏有什麼，現在是一個蠻力檢查它看起來是這樣的：

set scale to 1; 
while (overlaps with end points(in set (verticies) { !exists vertex which position.x > window.width && position.y > window.height && position.X < 0 && position.Y < 0)){ 
for 0 : 360 { 
    check whether at this angle all the points are aligned correctly,if yes 
    save the result as the last valid tuple(angle and scale) and continue 
    } 
    increase scale by a constant 
} 

如果任何人都知道這樣的實現已經可以在網上請大家分享的，否則給我一個大概的字你在想什麼，我現在在想什麼。

編輯：您始終可以認爲圖形的中心點位於屏幕的中心。

Answer 1

編輯我編輯了這篇文章，並提出了另一種解決方案。

目前還不太清楚「圖」和「容器」的邊緣是什麼。我認爲容器是一種具有軸對齊矩形作爲表面的畫布。

然後你就可以在三個步驟適合身材：

• 確定你的身影convex hull。這當然取決於你的身材的性質，但是如果你的身材已經是一個多邊形，這就像扔出所有凹點一樣簡單。

• 找到最佳旋轉角度，見下文。 （我之前曾建議用rotating calipers算法找到包含最小區域的包圍矩形，但這並不提供最佳解決方案。）

• 通過縮放和翻譯將旋轉後的圖形擬合到容器中。

最佳旋轉角度是旋轉圖形的軸對齊邊界框的縱橫比最接近容器縱橫比的角度。你的蠻力解決方案的想法是一個好的開始，但它可以被改進：

• 你不必增加規模成功;一旦找到了最佳角度，您就可以輕鬆地從旋轉圖形邊界框和容器的尺寸計算比例。

• 您不需要測試高達360°的所有角度。檢查四分之一圓就足夠了：如果θ是一個解，則θ+ 180°是相同的解，只能旋轉。您可以通過檢查θ - 90°的高度和寬度交換邊界框來檢查90°到180°範圍內的解決方案。

• 通過以一度步驟探測解決方案的範圍，您將只會得到一個粗略的解決方案。更好的方法可能是用逐漸減小的角度來探測更小的角度範圍。 （您可以根據您所需的精度和性能來匹配搜索間隔的確切值，性能應該沒問題，因爲凸包通常只有幾個點。）

• 沒有必要圍繞中心旋轉的屏幕。只需旋轉原點並在最後一步中將多邊形放入容器中即可。

這是Javascript中的一個實現。 （你問的C＃，但我不熟悉的，你應該沒有問題，採用這種代碼爲其他語言，雖然）

/* 
*  Return left, right, top and bottom points of a polygon 
*/ 
function bounds(poly) { 
    bx = { 
     left: poly[0], 
     right: poly[0], 
     top: poly[0], 
     bottom: poly[0] 
    }; 

    for (var i = 1; i < poly.length; i++) { 
     var p = poly[i]; 

     if (p.x < bx.left.x) bx.left = p; 
     if (p.x > bx.right.x) bx.right = p; 
     if (p.y < bx.top.y) bx.top = p; 
     if (p.y > bx.bottom.y) bx.bottom = p; 
    } 

    return bx; 
}  

/* 
*  Return a transformed (rotated, scaled, offset) polygon 
*/ 
function transform(poly, deg, scale, dx, dy) { 
    var phi = Math.PI * deg/180; 
    var c = Math.cos(phi); 
    var s = Math.sin(phi); 

    var rot = []; 

    for (var i = 0; i < poly.length; i++) { 
     var p = poly[i]; 
     var x = scale * (c * p.x - s * p.y + dx); 
     var y = scale * (s * p.x + c * p.y + dy); 
     rot.push(new Pt(x, y)); 
    } 

    return rot; 
} 

/* 
*  Return a polygon rotated by deg degrees. 
*/ 
function rotate(poly, deg) { 
    return transform(poly, deg, 1, 0, 0); 
} 

/* 
*  Assess a rotation of the polygon and update the optimum 
*  solution so far if necessary. 
*/ 
function assess(opt, poly, angle, ratio) { 
    var rot = rotate(poly, angle); 
    var box = bounds(rot); 
    var w = box.right.x - box.left.x; 
    var h = box.bottom.y - box.top.y; 
    var r = w/h; 

    if (Math.abs(r - ratio) < opt.delta) { 
     opt.delta = Math.abs(r - ratio); 
     opt.angle = angle; 
     opt.width = w; 
     opt.height = h; 
     opt.left = box.left.x; 
     opt.top = box.top.y; 
    } 

    if (Math.abs(1/r - ratio) < opt.delta) { 
     opt.delta = Math.abs(1/r - ratio); 
     opt.angle = angle + 90; 
     opt.width = h; 
     opt.height = w; 
     opt.left = -box.bottom.y; 
     opt.top = box.left.x; 
    } 
} 

/* 
*  Fit polygon inside a rectangle of width x height 
*/ 
function fit(poly, width, height) { 
    var ratio = width/height; 
    var opt = { delta: 1.0e+30 }; 

    for (var i = 0; i < 90; i += 10) assess(opt, poly, i, ratio); 

    for (d = 1; d > 0.002; d *= 0.1) { 
     var a = opt.angle; 

     for (var i = a - 9*d; i < a + 9.5*d; i += d) { 
      assess(opt, poly, i, ratio); 
     } 
    } 

    var sx = width/opt.width; 
    var sy = height/opt.height; 

    return transform(poly, 
     opt.angle, Math.min(sx, sy), 
     -opt.left, -opt.top); 
} 

這種迭代的方法可能並不總是能找到的最佳的解決方案，但它會找到一個足夠好的。

Answer 2

如果這是你的正在試圖找出

那麼答案（弧度）是

// Width W is the limit 
θ = Math.Atan(h/w)+Math.Acos(W/Math.Sqrt(h*h+w*w)); 
// Height H is the limit (like picture) 
θ = Math.Asin(H/Math.Sqrt(h*h+w*w))-Math.Atan(h/w); 

檢查其Math.Abs(θ)是最小的爲最終的答案。