二維坐標平面上有n個隨機點，如何求解這些點的最小外接矩形呢？

01-05

有O(n)解[1]。

更新：經評論提醒，需先進行 convex hull。

[1] Toussaint, Godfried T. "Solving geometric problems with the rotating calipers."Proc. IEEE Melecon. Vol. 83. 1983. https://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/calipers.pdf

你可以搜索一下「旋轉卡殼」

說下MATLAB的方法：

P = randn(100,2); K = convhull(P); v = feval(@(x)bsxfun(@rdivide,x,sqrt(sum(x.^2,2))),diff(P(K,:))); p = permute(P,[3 2 1]); m = cellfun(@(t){[min(t,"",3) max(t,"",3)]},... {sum(bsxfun(@times,p,v),2),sum(bsxfun(@times,v*[0 1;-1 0],p),2)}); [s,k] = min(diff(m{1},"",2).*diff(m{2},"",2)); rx = feval(@(x,y)v(k,1)*[x flip(x)]-v(k,2)*repelem(y,2),m{1}(k,:),m{2}(k,:)); ry = feval(@(x,y)v(k,2)*[x flip(x)]+v(k,1)*repelem(y,2),m{1}(k,:),m{2}(k,:));

fill(rx,ry,"r",P(K,1),P(K,2),"b","faceAlpha",.4), axis image line(P(:,1),P(:,2),"linestyle","n","color","k","marker","o")

如果點比較少，也可以按照像另外一個答案那樣那樣按照優化問題去做。不過點多的話效率比較低，且有可能得不到最優解，所以點多的時候不推薦

更新：

Mathematica 10.4 引入新函數 BoundingRegion 可用於解決這個問題，

pts = {{3, 10}, {6, 3}, {10, 2}, {2, 8}, {3, 3}}; BoundingRegion[pts, "MinOrientedRectangle"]

輸出：

Parallelogram[{6.53097,-1.0354},{{3.46903,3.0354},{-7.,8.}}]

Reference:

http://reference.wolfram.com/language/ref/BoundingRegion.html

-----------------------

$p$ 為 $n imes 2$ 的列表，表示一組點； $r$ 表示矩形的一邊與 $x$ 軸的夾角.

Mathematica:

p=RandomReal[1,{10,2}]; Minimize[Times@@(#-#2@@@MinMax/@(RotationMatrix@r.Transpose@p)),r]

可能的輸出:

{1.15201,{r-&>0.174946}}

其中 1.15201 表示矩形的面積.

日常秀Mathematica系列,雖然我看見標籤上寫著Matlab...

再運行一次

[ScriptCapitalR] = RandomReal[{0, 1}, {50, 2}]; chm = ConvexHullMesh[[ScriptCapitalR]]; lines = MeshPrimitives[chm, "Line"]; yaxis = Line[{{0, 0}, {0, 1}}]; tl = Table[Last[FindGeometricTransform[yaxis, l]], {l, lines}]; bounds = Table[RegionBounds[TransformedRegion[chm, t]], {t, tl}]; bboxes = Table[Rectangle @@ Transpose[b], {b, bounds}]; areas = Area /@ bboxes; index = Position[areas, Min[areas], 1][[1, 1]]; tf = Last[FindGeometricTransform[lines[[index]], yaxis]]; g = {EdgeForm[LightRed], Lighter[Yellow, 0.5], GeometricTransformation[bboxes[[index]], tf]}; Show[Graphics[g], chm, Graphics[Point[[ScriptCapitalR]]]] Area /@ {chm, g // Last // First}

題主，作業得自己寫。

想起最強大腦泰勒多邊形

for i in 平面上每一個點：

以i為圓心，向外擴展，當剛好包括四個點的時候，停止擴展，如果剛好五個…還沒想好…假定就是四個，計算面積m；

擴展：以上一個面積m為參照，初始無窮大，這裡還沒想好，但是會根據圓中已包含的點和m有個閥值，大於的話就停止，下一個點；

大題思路是這樣，不知道可行性，有好的想法歡迎補充。

矩形難道不是rectangle，長方形嗎？直接求所有點的最大X最大Y，最小X，最小Y就得到矩形的4個點了，時間複雜度是O(n)。

如果你想求的是convex hull，凸包的話，看這裡，有9種解法：

The Convex Hull of a Planar Point Set