[̲] [] [ ]

 

11.4

 

ᒺ- . : , . , . .

:

1.    ().

2.    ().

3.    ( ).

4.    .

11.2 ) ).

 

. 11.2

 

. , Point Segment. (1-4) : Convex, OneConv, TwoConv Polygon. , Deque. ᒺ, , Point Segment AnyObject. . 11.3.

 

. 11.3

 

Polygon TwoConv, , . Segment Point.

 

Point Segment Geom. Point AnyObject X,Y Init TX,TY; GetX, GetY X Y; Done. Point .

 

Segment . ³ A, B, ᒺ Point. Segment : Init; GetA, GetB A B; Len ; OnLine T ; Into T ; Square ; Done.

Init Segment A:=T1 B:=T2, A BPoint, . Init Point (A.Init(T1.GetX,T1.GetY); B.Init(T2.GetX,T2.GetY);). GetA, GetB T. A B. , Square S DTAB

 

1 |1 1 1|

S = -*|Tx Ax Bx|

2 |Ty Ay By|

 

(+ -) T, A B. AB , A B, DT1AB (. 11.4) +, DT2AB -.

 

. 11.4 г

 

Square , , , . OnLine , T AB. Square. 0. , 0 delta, . Into : s1 AT s2 TB. T AB s1, s2 AB, T AB.

 

 

{ }

Unit Geom;

 

interface

 

Uses AnyThing;

 

Type

PointRef = ^Point;

Point = Object(AnyObject) { }

private

X,Y: Real; { }

public

Constructor Init(TX,TY: Real); { }

Function GetX: Real; { X }

Function GetY: Real; { Y }

Destructor Done; Virtual; { }

end;

SegmentRef = ^Segment;

Segment = Object(AnyObject) { }

private

A,B: Point; { }

public

Constructor Init(T1,T2: Point); { }

Procedure GetA(VAR T: Point); { A }

Procedure GetB(VAR T: Point); { B }

Function Len: Real; { }

Function OnLine(T: Point): Boolean;{ T ? }

Function Into(T: Point): Boolean; { T ? }

Function Square(T: Point): Real; { TAB }

Destructor Done; Virtual; { }

end;

 

implementation

 

Constructor Point.Init;

begin

X:=TX; Y:=TY

end;

 

Function Point.GetX: Real;

begin GetX:=X end;

 

Function Point.GetY: Real;

begin GetY:=Y end;

 

Destructor Point.Done;

begin end;

 

Constructor Segment.Init;

begin

A.Init(T1.GetX,T1.GetY);

B.Init(T2.GetX,T2.GetY);

end;

 

Procedure Segment.GetA;

begin

T.Init(A.GetX,A.GetY)

end;

 

Procedure Segment.GetB;

begin

T.Init(B.GetX,B.GetY)

end;

 

Function Segment.Len: Real;

begin

Len:=Sqrt(Sqr(A.GetX-B.GetX)+Sqr(A.GetY-B.GetY))

end;

 

Function Segment.Square;

begin

Square:=0.5*(A.GetX*B.GetY-B.GetX*A.GetY+B.GetX*T.GetY

-T.GetX*B.GetY+T.GetX*A.GetY-A.GetX*T.GetY)

end;

 

Function Segment.OnLine;

const delta = 0.001;

begin

OnLine:=abs(Segment.Square(T)) <= delta

end;

 

Function Segment.Into;

var a1,b1: Point; s1,s2: Segment; l: Real;

begin

Segment.GetA(a1); s1.Init(a1,T);

Segment.GetB(b1); s2.Init(b1,T);

l:=Segment.Len;

Into:=Segment.OnLine(T) and (l >= s1.Len) and (l >= s2.Len)

end;

 

Destructor Segment.Done;

begin end;

 

end.

 

, , Conv. AnyThing, Geom, AnyDeque. ᒺ . AddPoint - , Show - Done. AddPoint T , . , ᒺ ( ᒺ ), , , , , . AddPoint ᒺ , . , ᒺ, , Self. ³, @Self ᒺ ᒺ. Show .

 

Convex . ³ Nangle , Per, Sq Init - , GetNAngle - , GetPer - , GetSq - , AddPoint - , Show , Done. AddPointOneConv, - .

 

OneConv Convex . ³ A Init - , GetA - , AddPoint - , Show , Done. AddPointTwoConv, . AddPoint .

 

TwoConv OneConv . ³ B Init - , GetB - B, AddPoint - , Show , Done. , 0. AB, Init Len Segment. AddPointPolygon, T AB. AddPoint T AB (. 11.5). T AB ( ), AB A ( B T), AB B ( A T).

 

. 11.5

 

Polygon , , . . , ( ) (. 11.6). . , , , .

 

. 11.6

 

() . , AB T, T AB TAB ( ) (. 11.7 ) ) , T AB TAB (. 11.7 ) ). T AB, AB T, TAB 0. ( S) T Visible, Conv .

 

. 11.7

 

Polygon Convex Dq Init - CurSide - , NextSide ; PreviousSide , AddPoint - , Show - , Done.

Init T1, T2, T3, . , . 3 : s1 (T1T2), s2 (T1T3), s3 (T2T3) . T2 . T1T3 T2, T1 , T3 - , .

CurSide , . , , . NextSide PreviousSide , . Show , . Done , .

, AddPoint ( 11.8). :

1)    T (. 11.8 ) );

2)    T (. 11.8 ) ).

 

. 11.8

 

1), . 2) 䳿:

         T (A1A2, A2A3, A3A4);

         T (A1T, TA4);

         , .

(A2, A3). T. n, p s :

 

n = n ndel + 2,

p = p pdel + l1 + l2,

s = s + sdel,

 

ndel , pdel , (A1A2, A2A3, A3A4), l1 A1T, l2 TA4, sdel , T , (DTA1A2 DTA2A3, DTA3A4).

AddPoint , , T. ( ). . ϳ , T ( , T ), T . T , , T, .

 

 

{ }

Unit Conv;

 

interface

 

Uses AnyThing, Geom, AnyDeque;

 

Type

ConvRef = ^Convex;

Convex = Object { }

private

NAngle: Integer; { }

Per,Sq: Real; { }

public

Constructor Init; { }

Function GetNAngle: Integer; { }

Function GetPer: Real; { }

Function GetSq: Real; { }

Function AddPoint(T: Point): ConvRef; Virtual;{ }

Procedure Show; Virtual; { }

Destructor Done; Virtual; { }

end;

OneRef = ^OneConv;

OneConv = Object(Convex) { }

private

A: Point; { }

public

Constructor Init(T: Point); { }

Procedure GetA(Var T: Point); { A }

Function AddPoint(T: Point): ConvRef; Virtual;{ }

Procedure Show; Virtual; { }

Destructor Done; Virtual; { }

end;

TwoRef = ^TwoConv;

TwoConv = Object(OneConv) { }

private

B: Point; { }

public

Constructor Init(T1,T2: Point); { }

Procedure GetB(Var T: Point); { B }

Function AddPoint(T: Point): ConvRef; Virtual;{ }

Procedure Show; Virtual; { }

Destructor Done; Virtual; { }

end;

PolyRef = ^Polygon;

Polygon = Object(Convex) { }

private

Dq: Deque; { }

public

Constructor Init(T1,T2,T3: Point); { }

Procedure CurSide(Var S: Segment); { }

Procedure NextSide; { }

Procedure PreviousSide; { }

Function AddPoint(T: Point): ConvRef; Virtual;{ }

Procedure Show; Virtual; { }

Destructor Done; Virtual; { }

end;

 

implementation

 

Constructor Convex.Init;

begin

NAngle:=0; Per:=0; Sq:=0

end;

 

Function Convex.GetPer;

begin

GetPer:=Per

end;

 

Function Convex.GetNAngle;

begin

GetNAngle:=NAngle

end;

 

Function Convex.GetSq;

begin

GetSq:=Sq

end;

 

Function Convex.AddPoint;

var p: OneRef;

begin

p:=ConvRef(@Self);

AddPoint:=New(OneRef,Init(T)); { }

dispose(p,Done);

end;

 

Procedure Convex.Show;

begin

writeln('P = ',Per:7:1);

writeln('S = ',Sq:7:1);

end;

 

Destructor Convex.Done;

begin end;

 

Constructor OneConv.Init;

begin

Convex.Init; NAngle:=1;

A.Init(T.GetX,T.GetY);

end;

 

Procedure OneConv.GetA;

begin

T.Init(A.GetX,A.GetY)

end;

 

Function OneConv.AddPoint;

var p: OneRef;

begin

p:=OneRef(@Self);

if (A.GetX <> T.GetX) or (A.GetY <> T.GetY) then begin

AddPoint:=New(TwoRef,Init(A,T)); { }

dispose(p,done) end

else AddPoint:=p

end;

 

Procedure OneConv.Show;

begin

writeln('( ',A.GetX:7:1,',',A.GetY:7:1,' )');

Convex.Show;

end;

 

Destructor OneConv.Done;

begin end;

 

Constructor TwoConv.Init;

var s: Segment;

begin

OneConv.Init(T1); NAngle:=2;

B.Init(T2.GetX,T2.GetY);

s.Init(A,B); Per:=s.Len;

end;

 

Procedure TwoConv.GetB;

begin

T.Init(B.GetX,B.GetY)

end;

 

Function TwoConv.AddPoint;

var s,s1,s2: Segment;

p: TwoRef;

begin

p:=TwoRef(@Self);

s.Init(A,B); s1.Init(A,T); s2.Init(B,T);

if s.Online(T) then { T,A,B ? }

begin

if s1.Into(B) then B:=T { B A,T ? }

else if s2.Into(A) then A:=T; { A B,T ? }

s.Init(A,B); Per:=s.Len; AddPoint:=p

end

else begin

AddPoint:=New(PolyRef,Init(A,B,T)); { }

dispose(p,done)

end

end;

 

Procedure TwoConv.Show;

begin

writeln('( ',B.GetX:7:1,',',B.GetY:7:1,' )');

OneConv.Show;

end;

 

Destructor TwoConv.Done;

begin end;

 

Function Visible(S: Segment; T: Point): Boolean;

begin

Visible:=(S.Online(T) and not S.Into(T)) or (S.Square(T) > 0)

end;

 

Constructor Polygon.Init;

var s1,s2,s3: Segment;

begin

s1.Init(T1,T2); s2.Init(T1,T3); s3.Init(T2,T3);

NAngle:=3; Per:=s1.Len+s2.Len+s3.len; Sq:=abs(s1.Square(T3));

Dq.Init;

Dq.PutBg(New(PointRef,Init(T2.GetX,T2.GetY))); { T2 }

if Visible(s2,T2) then { T1,T3 T2 ? }

begin

Dq.PutBg(New(PointRef,Init(T1.GetX,T1.GetY))); { T1 }

Dq.PutEn(New(PointRef,Init(T3.GetX,T3.GetY))) { T3 }

end

else

begin

Dq.PutBg(New(PointRef,Init(T3.GetX,T3.GetY))); { T3 }

Dq.PutEn(New(PointRef,Init(T1.GetX,T1.GetY))) { T1 }

end

end;

 

Procedure Polygon.CurSide;

var p1,p2: PointRef;

begin

p1:=PointRef(Dq.GetEn); p2:=PointRef(Dq.GetBg);

S.Init(p1^,p2^);

Dq.PutEn(p1); Dq.PutBg(p2)

end;

 

Procedure Polygon.NextSide;

begin

Dq.PutEn(Dq.GetBg);

end;

 

Procedure Polygon.PreviousSide;

begin

Dq.PutBg(Dq.GetEn);

end;

 

Function Polygon.AddPoint;

var s: Segment; p: PointRef;

ndel,i: Integer; vis: Boolean;

pdel: Real; { , }

sdel: Real; { , }

begin

Polygon.CurSide(s); vis:=Visible(s,T);

i:=1;

while (i <= NAngle) and vis do begin { }

Polygon.NextSide; Polygon.CurSide(s);

vis:=Visible(s,T); i:=i+1

end;

while (i <= NAngle) and not vis do begin { }

Polygon.NextSide; Polygon.CurSide(s);

vis:=Visible(s,T); i:=i+1

end;

if vis then begin

ndel:=1; pdel:=s.Len; sdel:=s.Square(T);

while true do begin { }

Polygon.NextSide; Polygon.CurSide(s);

if not Visible(s,T) then break;

ndel:=ndel+1; pdel:=pdel+s.Len; sdel:=sdel+s.Square(T);

p:=PointRef(Dq.GetEn); dispose(p,Done);

end;

Polygon.PreviousSide; { }

Dq.PutBg(New(PointRef,Init(T.GetX,T.GetY))); { T }

Polygon.CurSide(s); Per:=Per-pdel+s.Len;

Polygon.NextSide; Polygon.CurSide(s); Per:=Per+s.Len;

NAngle:=NAngle-ndel+2; Sq:=Sq+sdel;

end;

AddPoint:=@Self

end;

 

Procedure Polygon.Show;

var p: PointRef; i: Integer;

begin

for i:=1 to NAngle do begin

p:=PointRef(Dq.GetBg);

writeln('( ',p^.GetX:7:1,',',p^.GetY:7:1,' )');

Dq.PutEn(p);

end;

Convex.Show;

end;

 

Destructor Polygon.Done;

begin

Dq.Clear

end;

 

end.

 

 

ConvCalc ᒺ, , , , . input ( <Ctrl>+<Z>). AddPoint, Show, Done , .

 

 

Program ConvCalc;

 

Uses AnyThing,Geom,AnyDeque,Conv;

 

Var

cv: ConvRef;

t: Point; x,y: Real;

 

begin

writeln(' ');

New(cv,Init); { }

while true do begin { }

write(' : '); Readln(x,y);

if eof then break; { , }

t.Init(x,y);

cv:=cv^.AddPoint(t); { }

end;

writeln(' :');

cv^.Show; { }

dispose(cv,Done); { }

end.

 

 

 

 

11.1. PutEn GetEn C++.

 

11.2. C++.

 

11.3. () Show (, ) .

 

[̲] [] [ ]