高价求够算法：如何求出包围任意折线多边形的最小矩形(300分)

H

HeroFirst

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-08-28

• #1

给出一任意折线多边形（各点坐标已知），现欲找到一最小矩形（求出四点坐标），
使各点均落在矩形边上或内部。

 

老

老屯

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-08-28

• #2

你是寻找最外面的矩形,这个简单,如果寻找内部最大矩形,多少会麻烦一点.

function GetRect(PolyPoints: Array of TPoint): TRect;
var
i: integer;
MinX,MinY,MaxX,MaxY: integer;
begin
MinX := PolyPoints[Low(PolyPoints)].X;
MinY := PolyPoints[Low(PolyPoints)].Y;
MaxX := PolyPoints[Low(PolyPoints)].X;
MaxY := PolyPoints[Low(PolyPoints)].Y;

for i := Low(PolyPoints)+1 to High(PolyPoints) do
begin
if PolyPoints.X < MinX then MinX := PolyPoints.X;
if PolyPoints.Y < MinY then MinY := PolyPoints.Y;
if PolyPoints.X > MaxX then MaxX := PolyPoints.X;
if PolyPoints.Y > MaxY then MaxY := PolyPoints.Y;
end;
Result.Left := MinX;
Result.Top := MinY;
Result.Right := MaxX;
Result.Bottom := MaxY;
end;

 

陈

陈晨

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-08-28

• #3

讲一下思路吧很简单的首先比较出坐标中x坐标的最大值和最小值同样也找出y的最大值
最小值分别得到（xmin，xmax）（ymin，ymax）则（xmin，ymin）（xmax，ymax）极为
所求

 

J

JohnsonGuo

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-08-29

• #4

以上两位的方法显然是错误的。他们的方法只考虑到该矩形水平放置的情况，
而没有考虑矩形可以倾斜放置。
假设给出的多边形是一个旋转了30度的矩形，那么其最小包含矩形便是其本身。

 

H

HeroFirst

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-08-29

• #5

同意JohnsonGuo，老屯的方法我也试过。请大家想出个“万全之策”

 

L

lengyx

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-09-01

• #6

小case
我曾经做过一个求任意形状物体长和宽的程序.
算法:
Mypoint[1..All]:array of pointer;//多边形所有顶点坐标
All:顶点总数
比较得到最上点TopPoint 和最左点Leftpoint坐标
1:从TopPoint开始
StartPoint:=TopPoint
Length1:=0;

repeat
设 flag:=0;
for i:=1 to All do
begin
flag:=0;
MyLength:= length between StartPoint and MyPoint;
if Mylength>length1 then
begin
length1:=Mylength;
flag:=flag+1;
EndPoint:=MyPoint;
end;

StarPoint和EndPoint交换;

end;
until flag:=0;
得到多边形长度length1->from StartPonit to EndPoint
2.从StartPoint:=LeftPoint开始同1中步骤得到length2
取其中最大的长度的EndPoint以StartPoint.

将EndPoint以StartPoint为园心旋转到与StartPoint水平,得到旋转矩阵
将多边形各顶点坐标依次旋转
得到其中最高点HighPoint和最低点LowPoint;
这4点就是你要的矩形边上的点
矩形的长边与线StartPoint to EndPoint 平行
由此不难得到你要的矩形顶点坐标

how difficult i sent the message

 

老

老屯

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-09-01

• #7

干什么用,下料么?

 

H

honestman

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-09-01

• #8

看到最后，居然不知道“矩形的长边与线StartPoint to EndPoint 平行”中
的StartPoint和EndPoint是指哪两点？？？

 

H

HeroFirst

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-09-05

• #9

lengyx，First thand you sent the message。
不过还是不太明白
找到距离最远的两点后，怎么旋转得到矩形四点？
可否发个较完整的源程序看看？
<A Href="mailto:coolzjs@sina.com">coolzjs@sina.com</A>

 

A

Another_eYes

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-09-21

• #10

go on

 

P

pxie

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-09-21

• #11

g

 

G

GGCAT

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-12

• #12

我考虑了一下，此题在本人的知识范围内似乎无精确解。
而最小包含的意义应是指该矩形的面积最小吧；

用一个笨办法还是可以求出近似解的（我的风格，没有捷径就走远路）

把该多边在 180 度 内行进行递增角度的旋转变换，为每一结果求出
水平包含矩形并连同当时角度一起记录下来。然后比较一系列矩形，
采用最小的一个用当时的角度变换回去就行了。
每次递增的值越小，得到的结果就越接近事实。为了提高速度，可采用
逼近计算。

这个方法够笨吧，不过只要不是用来搞科研，用来下料是够了，呵呵！

 

J

jxqjxq

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-12

• #13

找到距离最远的两点(xi,yi)(xj,yj)
求由这两点所构成直线与X轴的夹角 alpha=arctg((yj-yi)/(xj-xi))
对每各顶点(xk,yk)进行旋转得到新坐标(xk',yk')：
xk'=xk*cos(alphi)-yk*sin(alphi)
yk'=xk*sin(alphi)+yk*cos(alphi)

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-13

• #14

??能不能用于凹多边形
听听。

 

G

GGCAT

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-13

• #15

寻找最长边的方法是绝对错误的！！！！
小举一例：
一个简单的矩形，距离最长的两点是两个对角点，你把它这么一转。。。
然后再求上，下顶点，看看你的结果。哈哈，开玩笑吧！
我想也许用逐步逼近法也许是最好的了。因为原结果可能是不只一个的。
我已经在本机测试了，效果不错。

 

G

GGCAT

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-13

• #16

再 灌点水 吧！ 试一下我的程序：

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.

 

G

GGCAT

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-13

• #17

续集 ：
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.

 

P

pino

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-14

• #18

我想这应该是一个纯数学的问题，似乎再那里见过。
如果能够证明下面的推论一切就简单了：
与任意凸多边形象外切的矩形，矩形有一条边和多边形的一条边在同一条直线上。
如果是凹多边形的话可以先转成凸多边形。

 

吕

吕雪松

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-14

• #19

有可能是多解，另外，你需要的是最优解还是最快解？

 

H

hhzh426

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2000-10-14

• #20

你的多边形是画在平面内的吧，找出该平面上所表示的该多边形的所有顶点的坐标值，
然后求出所有坐标值中最大和最小的(x,y:maxx,maxy,minx,miny)，则该平面内的矩形：
(minx,miny,maxx,maxy)就是所求的最小矩形。