求Polygon的布尔运算算法

Question

哪位高手知道Polygon的交\并\补算法,贡献出来,小弟以高分求教!!万分感谢!!

Answer 1

你说清楚些好吗。
比如说交，
是不是说两个或多个Polygon，只取他们相交的部分图形但你的两个Polygon是先后画出来的，你第一个Polygon画出来时已经显示出来了，
再画第二个，怎么取交呢。
你把你的要求说清楚些好吗，

Answer 2

我这里提供两个多边形的点集：Points1,Points2:array of TPoint，经过交、并、差运算后如果成功，函数返回运算后的点集。
  请问高手该如何写呀？

Answer 3

这个太复杂了，需要图形学的支持。也许有图形高手知道
如果你愿意，可以加我的QQ，让我思考几天。
QQ：68816088

Answer 4

我最近也在研究这个问题，曾经找到一份论文，感觉不错，你可以看看：
http://www.jos.org.cn/1000-9825/14/845.pdf

Answer 5

procedure MoveCursorToPosition(ACtrl:TControl;Pt:TPoint);
begin
  if ACtrl<>nil then
    Pt:=ACtrl.ClientToScreen(Pt);
  SetCursorPos(Pt.x,Pt.y);
end;function GetRectClient(ARect:TRect):TPoint;
begin
  Result:=Point((ARect.Left+ARect.Right) div 2,
                (ARect.Top+ARect.Bottom) div 2); 
end;procedure GetSquarePoints(cPt:TPoint;NumSides,Radius:Integer;
  FA:Extended;var Points:TArrayOfPoint);
Var
  I, X, Y : Integer;
  A:Extended;
Begin
  SetLength(Points,0);
  if NumSides>0 then
  begin
     A:=360/NumSides;
     SetLength(Points,NumSides);
     For I:=0 to NumSides-1 Do
     Begin
        X:=cPt.x+Round(Radius*Sin((FA+A*I)*Pi/180));
        Y:=cPt.y-Round(Radius*Cos((FA+A*I)*Pi/180));
        Points[I]:=Point(X,Y);
     End;
  end;
End;function NormalizeRect (ARect: TRect): TRect;
var
  tmp: Integer;
begin
  if ARect.Bottom < ARect.Top then
  begin
    tmp := ARect.Bottom;
    ARect.Bottom := ARect.Top;
    ARect.Top := tmp;
  end;
  if ARect.Right < ARect.Left then
  begin
    tmp := ARect.Right;
    ARect.Right := ARect.Left;
    ARect.Left := tmp;
  end;
  Result := ARect;
end;function MakeRect(Pt1 : TPoint;
                  Pt2 : TPoint) : TRect;
begin
  if pt1.x < pt2.x then begin
    Result.Left := pt1.x;
    Result.Right := pt2.x;
  end else begin
    Result.Left := pt2.x;
    Result.Right := pt1.x;
  end;
  if pt1.y < pt2.y then begin
    Result.Top := pt1.y;
    Result.Bottom := pt2.y;
  end else begin
    Result.Top := pt2.y;
    Result.Bottom := pt1.y;
  end;
end;
这是我整理的图形操作函数，可能有一两个函数调用了其他的单元，那些暂时可以忽略！

Answer 6

type
    TPointFLoat = record
    X : Real;
    Y : Real;
    end;// subtract 1 vector from another
function Subtract(AVec1, AVec2 : TPoint) : TPoint;
begin
  Result.X := AVec1.X - AVec2.X;
  Result.Y := AVec1.Y - AVec2.Y;
end;//判断线和线是否相交//
function LinesCross(LineAP1, LineAP2, LineBP1, LineBP2 : TPoint) : boolean;
Var
  diffLA, diffLB : TPoint;
  CompareA, CompareB : integer;
begin
  Result := False;
  diffLA := Subtract(LineAP2, LineAP1);
  diffLB := Subtract(LineBP2, LineBP1);
  CompareA := diffLA.X*LineAP1.Y - diffLA.Y*LineAP1.X;
  CompareB := diffLB.X*LineBP1.Y - diffLB.Y*LineBP1.X;
  if ( ((diffLA.X*LineBP1.Y - diffLA.Y*LineBP1.X) < CompareA) xor
    ((diffLA.X*LineBP2.Y - diffLA.Y*LineBP2.X) < CompareA) ) and
    ( ((diffLB.X*LineAP1.Y - diffLB.Y*LineAP1.X) < CompareB) xor
    ((diffLB.X*LineAP2.Y - diffLB.Y*LineAP2.X) < CompareB) ) then
    Result := True;
end;//取得线与线的交点//
function LineIntersect(LineAP1, LineAP2, LineBP1, LineBP2 : TPoint) : TPointFloat;
Var
  LDetLineA, LDetLineB, LDetDivInv : Real;
  LDiffLA, LDiffLB : TPoint;
begin
  LDetLineA := LineAP1.X*LineAP2.Y - LineAP1.Y*LineAP2.X;
  LDetLineB := LineBP1.X*LineBP2.Y - LineBP1.Y*LineBP2.X;
  LDiffLA := Subtract(LineAP1, LineAP2);
  LDiffLB := Subtract(LineBP1, LineBP2);
  LDetDivInv := 1 / ((LDiffLA.X*LDiffLB.Y) - (LDiffLA.Y*LDiffLB.X));
  Result.X := ((LDetLineA*LDiffLB.X) - (LDiffLA.X*LDetLineB)) * LDetDivInv;
  Result.Y := ((LDetLineA*LDiffLB.Y) - (LDiffLA.Y*LDetLineB)) * LDetDivInv;
end;function Distance(XPos, YPos, X, Y: Real): Real;
begin
  Result:=sqrt(
    Power(XPos-X,2)+Power(YPos-Y,2));
end;function PointInCircle(cPt:TPointFloat;r:real;Pt:TPointFloat):Boolean;
begin
  Result:=Distance(Pt.x,Pt.y,cPt.x,cPt.y)<r;
end;function PointInEllipse(cPt:TPoint;L,T,R,B:Integer):Boolean;
var
  BtnEllipse : HRgn;     
begin
  BtnEllipse := CreateEllipticRgn(L,T,R,B);
  try
    Result := PtInRegion(BtnEllipse,cPt.x,cPt.y);
  finally
    DeleteObject(BtnEllipse);
  end;
end;function LineCrossRect(Pt1,Pt2:TPoint;ARect:TRect):Boolean;
var
  IsPt1InRect,IsPt2InRect:Boolean;
begin
  IsPt1InRect:=PtInRect(ARect,Pt1);
  IsPt2InRect:=PtInRect(ARect,Pt2);
  if IsPt1InRect and IsPt2InRect then
    Result:=False
  else
    Result:=LinesCross(Pt1,Pt2,Point(ARect.Left,ARect.Top),Point(ARect.Right,ARect.Top)) or
       LinesCross(Pt1,Pt2,Point(ARect.Right,ARect.Top),Point(ARect.Right,ARect.Bottom)) or
       LinesCross(Pt1,Pt2,Point(ARect.Right,ARect.Bottom),Point(ARect.Left,ARect.Bottom)) or
       LinesCross(Pt1,Pt2,Point(ARect.Left,ARect.Bottom),Point(ARect.Left,ARect.Top));
end;function clipTest(const p,q:Extended;var u1,u2:Extended):Boolean;
var
  r:Extended;
begin
  Result:=True;
  if (p<0.0) then
  begin
    r:=q/p;
    if (r>u2) then
      Result:=False
    else
      if (r>u1) then
        u1:=r;
  end
  else if (P>0.0) then
  begin
    r:=q/p;
    if (r<u1) then
      Result:=False
    else if (r<u2) then
      u2:=r;
  end
  else
  begin
    if (q<0.0) then
      Result:=False;
  end;
end;

Answer 7

function clipLine(ARect:TRect;Pt1,Pt2:TPoint;var IPt1,IPt2:TPoint):Boolean;
var
  u1,u2,dx,dy:Extended;
  mPt1,mPt2:TPointFloat;
begin
  Result:=False;
  
  mPt1.x:=Pt1.x;
  mPt1.y:=Pt1.y;
  mPt2.x:=Pt2.x;
  mPt2.y:=Pt2.y;
  
  u1:=0.0;
  u2:=1.0;
  dx:=Pt2.x-Pt1.x;
  if clipTest(-dx,Pt1.x-ARect.Left,u1,u2) then
    if clipTest(dx,ARect.Right-Pt1.x,u1,u2) then
    begin
      dy:=Pt2.y-Pt1.y;
      if clipTest(-dy,Pt1.y-ARect.Top,u1,u2) then
        if clipTest(dy,ARect.Bottom-Pt1.y,u1,u2) then
        begin
          if (u2<1.0) then
          begin
            mPt2.x:=Pt1.x+u2*dx;
            mPt2.y:=Pt1.y+u2*dy;
          end;
          if (u1>0.0) then
          begin
            mPt1.x:=Pt1.x+u1*dx;
            mPt1.y:=Pt1.y+u1*dy;
          end;          IPt1:=Point(Round(mPt1.x),Round(mPt1.y));
          IPt2:=Point(Round(mPt2.x),Round(mPt2.y));          Result:=True;
        end;
    end;
end;function clipRect(const Rect1,Rect2:TRect;var IRect:TRect):Boolean;
var
  Points : TArrayOfPoint;
begin
  Result:=False;  SetLength(Points,4);
  Points[0]:=Point(Rect1.Left,Rect1.Top);
  Points[1]:=Point(Rect1.Right,Rect1.Top);
  Points[2]:=Point(Rect1.Right,Rect1.Bottom);
  Points[3]:=Point(Rect1.Left,Rect1.Bottom);  ClipPolygon(Points,Rect2);  if High(Points)-Low(Points)>0 then
  begin
    IRect.Left:=Points[0].x;
    IRect.Top:=Points[0].y;
    IRect.Right:=Points[2].x;
    IRect.Bottom:=Points[2].y;
    Result:=True;
  end;  SetLength(Points,0);
end;