如何求出包围任意折线多边形的最小矩形

给出一任意折线多边形（各点坐标已知），现欲找到一最小矩形（求出四点坐标）， 使各点均落在矩形边上或内部。
GGCAT, 时间：2000-10-13 19:26:07, ID：365137
寻找最长边的方法是绝对错误的！！！！
小举一例：
一个简单的矩形，距离最长的两点是两个对角点，你把它这么一转。。。
然后再求上，下顶点，看看你的结果。哈哈，开玩笑吧！
我想也许用逐步逼近法也许是最好的了。因为原结果可能是不只一个的。
我已经在本机测试了，效果不错。
　
　
来自：GGCAT, 时间：2000-10-13 22:30:00, ID：365279
再 灌点水 吧！ 试一下我的程序：
unit PloyTest;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;
type
TPolyVertex=record //浮点型顶点定义
Xouble;
Youble
End;
TMinRect=Record //矩形记录
p1:TPolyVertex;
p2:TPolyVertex;
p3:TPolyVertex;
p4:TPolyVertex;
Sizeouble;
Degreeouble;
End;
TPolyArray=Array of TpolyVertex; //多边型浮点数组类型
　
TForm1 = class(TForm)
Test: TButton;
procedure TestClick(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
Procedure PloyRotate(Var SrcPoly,DstPoly:TPolyArray; Valueouble);
Function BuildMinRect(Poly:TpolyArray):TminRect;
var
Form1: TForm1;
RandomPoly:TPolyArray;
implementation
{$R *.DFM}
Procedure PloyRotate(Var SrcPoly,DstPoly:TPolyArray; Valueouble);
Var I,H:Integer;
CosV,SinVouble; //旋转变换
Begin
H:=High(SrcPoly);
SetLength(DstPoly,H+1);
CosV:=Cos(Value);SinV:=Sin(Value);
For I:=0 to H do
Begin
DstPoly.X:=SrcPoly.X*CosV-SrcPoly.Y*SinV;
DstPoly.Y:=SrcPoly.X*SinV+SrcPoly.Y*CosV;
End;
End;
Function BuildMinRect(Poly:TpolyArray):TminRect; //求最小水平包含矩形
Var I:Integer;
HMin,HMax,VMin,VMaxouble;
Begin
HMin:=999999999999; HMax:=-999999999999
VMin:=999999999999; VMax:=-999999999999
For I:=0 to High(Poly) Do
Begin
IF Poly.X<HMin then HMin:=Poly.X;
IF Poly.X>HMax then HMax:=Poly.X;
IF Poly.Y<VMin then VMin:=Poly.Y;
IF Poly.Y>VMax then VMax:=Poly.Y;
End;
Result.p1.X:=Hmin; Result.p1.Y:=Vmin;
Result.p2.X:=Hmax; Result.p2.Y:=Vmin;
Result.p3.X:=HMax; Result.p3.Y:=VMax;
Result.p4.X:=Hmin; Result.p4.Y:=VMax;
Result.Size:= ((Hmax-Hmin)*(Vmax-Vmin));
End;
　
procedure TForm1.TestClick(Sender: TObject);
Var TempPoly:TPolyArray;
I,J:Integer;
SizeMin,Step,Degreeouble;
ARect,MinRect:TminRect;
RectPoly:TpolyArray;
Begin
J:=Random(10)+3; RandSeed:=GetTickCount;
Setlength(RandomPoly,J);
For I:=0 to J-1 do //随机的多边形生成
Begin
RandomPoly.X:=Random(300)+100;
RandomPoly.Y:=Random(300)+50;
End;
Degree:=0 Step:=PI/720; //精确度
SizeMin:=9999999999999999;
while Degree<PI DO //角度递增旋转
Begin
PloyRotate(RandomPoly,TempPoly,Degree); //变换
ARect:=BuildMinRect(TempPoly); //求水平包含矩形
IF Arect.Size<SizeMin then
Begin
SizeMin:=ARect.Size; //记录最小面积的包含矩形
Minrect:=ARect;
MinRect.Degree:=Degree;
End;
Degree:=Degree+Step;
End;
SetLength(TempPoly,4);
TempPoly[0]:=MinRect.p1; TempPoly[1]:=MinRect.p2;
TempPoly[2]:=MinRect.p3; TempPoly[3]:=MinRect.p4;
PloyRotate(TempPoly,RectPoly,-Minrect.Degree); //反向变换结果矩形
Canvas.Brush.Color:=Clwhite;
Canvas.Rectangle(Canvas.Cliprect); //清除原内容
Canvas.Pen.Color:=ClBlue; //画多边形
canvas.Moveto(Round(RandomPoly[0].X),Round(RandomPoly[0].Y));
For I:=1 to J-1 do
canvas.Lineto(Round(RandomPoly.X),Round(RandomPoly.Y));
canvas.Lineto(Round(RandomPoly[0].X),Round(RandomPoly[0].Y));
Canvas.Pen.Color:=ClRed; //画包含矩形
canvas.Moveto(Round(RectPoly[0].X),Round(RectPoly[0].Y));
For I:=1 to 3 do
canvas.Lineto(Round(RectPoly.X),Round(RectPoly.Y));
canvas.Lineto(Round(RectPoly[0].X),Round(RectPoly[0].Y));
End;
end.
　
　
来自：GGCAT, 时间：2000-10-13 22:47:23, ID：365291
续集 ：
while Degree<PI DO //角度递增旋转
Begin
PloyRotate(RandomPoly,TempPoly,Degree); //变换
ARect:=BuildMinRect(TempPoly); //求水平包含矩形
IF Arect.Size<SizeMin then
Begin
SizeMin:=ARect.Size; //记录最小面积的包含矩形
Minrect:=ARect;
MinRect.Degree:=Degree;
End;
Degree:=Degree+Step;
End;
SetLength(TempPoly,4);
TempPoly[0]:=MinRect.p1; TempPoly[1]:=MinRect.p2;
TempPoly[2]:=MinRect.p3; TempPoly[3]:=MinRect.p4;
PloyRotate(TempPoly,RectPoly,-Minrect.Degree); //反向变换结果矩形
Canvas.Brush.Color:=Clwhite;
Canvas.Rectangle(Canvas.Cliprect); //清除原内容
Canvas.Pen.Color:=ClBlue; //画多边形
canvas.Moveto(Round(RandomPoly[0].X),Round(RandomPoly[0].Y));
For I:=1 to J-1 do
canvas.Lineto(Round(RandomPoly.X),Round(RandomPoly.Y));
canvas.Lineto(Round(RandomPoly[0].X),Round(RandomPoly[0].Y));
Canvas.Pen.Color:=ClRed; //画包含矩形
canvas.Moveto(Round(RectPoly[0].X),Round(RectPoly[0].Y));
For I:=1 to 3 do
canvas.Lineto(Round(RectPoly.X),Round(RectPoly.Y));
canvas.Lineto(Round(RectPoly[0].X),Round(RectPoly[0].Y));
End;
end.