Cześć,
Muszę napisać program który wylosuje n przypadkowych punktów w układzie współrzędnych 2D, a potem stworzy dwa różne trójkąty otaczające wszystkie te punkty i porówna ich pole. Z wylosowaniem punktów nie było problemów, ale nie mam pojęcia jak się zabrać za wyznaczenie trójkątów. Chodzi mi bardziej o stronę logiczną, jak do tego podejść, z samym napisaniem powinienem sobie poradzić.
Moglibyście mi jakoś pomóc, doradzić? Może ktoś robił coś podobnego?
Z góry dziękuję.
Pozdrawiam
To jest bardzo proste. Wpierw znajdujesz prostokąt o bokach równoległych do osi, który zawiera wszystkie punkty. Potem opisujesz na nim trójkąt: dowolny z boków wydłużasz dwukrotnie, jego końce to dwa wierzchołki trójkąta. Trzeci wierzchołek leży nad środkiem przeciwległego boku prostokąta.
Zapomniałem dodać, że na każdym z boków trójkąta musi być co najmniej jeden z punktów.
Wpierw prosta l przez najbardziej na lewo położony wierzchołek. Na prostej l wybieramy punkt A leżący powyżej wszystkich wylosowanych punktów Pi. Szukamy takiego punktu Pi, żeby kąt między prostą l i odcinkiem APi był największy. Analogicznie wybieramy punkt B poniżej wylosowanych punktów i szukamy odpowiedniego punktu Pk. Szukany trójkąt ma wierzchołki A, B i punkt przecięcia APi z BPk.
Wielkie dzięki
L=Sqrt(((Ax-Cx)*(By-Ay)+(Cy-Ay)*(Bx-Ax))²*(By-Ay)²+((Ay-Cy)*(Bx-Ax)+(Cx-Ax)*(By-Ay))²*(Bx-Ax)²)/(2*((By-Ay)²+(Bx-Ax)²))
y=((x-Ax)*By-(x-Bx)*Ay-D*Sqrt((By-Ay)²+(Bx-Ax)²))/(Bx-Ax)
x=((y-Ay)*Bx-(y-By)*Ax+D*Sqrt((Bx-Ax)²+(By-Ay)²))/(By-Ay)
podstawiasz zamiast x,y Ax,Ay i dostajesz A'x,A'y. W sumie wychodzi 3 odcinki opisane 6-ma punktami.
5. Znajdujesz przecięcie się odcinka (A'x,A'y)-(B'x,B'y) z (C'x,C'y)-(A'x,A'y) i to będzie nowy punkt A. Przecięcie się prostych przez A-B oraz C-D
x=((Bx-Ax)*(Dx*Cy-Dy*Cx)-(Dx-Cx)*(Bx*Ay-By*Ax))/((By-Ay)*(Dx-Cx)-(Dy-Cy)*(Bx-Ax))
y=((Dy-Cy)*(Bx*Ay-By*Ax)-(By-Ay)*(Dx*Cy-Dy*Cx))/((Dy-Cy)*(Bx-Ax)-(By-Ay)*(Dx-Cx))
analogicznie do pozostałych dwóch par.
Dla kolejnego trójkąta powtórzyć od pkt 2.
Edit, z ciekawości sprawdziłem algorytm pod Lazarus'em, działa:
unit TriangleAroundPointsMain;
{$mode objfpc}{$H+}
interface uses
Classes,
SysUtils,
FileUtil,
Forms,
Controls,
Graphics,
Dialogs,
ExtCtrls;
type
TPointArray=array of TPoint;
{ TATriangleAroundPoint }
TATriangleAroundPoint = class(TForm)
procedure FormClick(Sender: TObject);
procedure FormDblClick(Sender: TObject);
procedure FormPaint(Sender: TObject);
private
arr:TPointArray;
a,b,c:TPoint;
public
function RandRect:TRect;
procedure RandPoints(Size:Integer);
procedure RandTriangle;
end;
var ATriangleAroundPoint:TATriangleAroundPoint;
implementation
{$R *.lfm}
{ TATriangleAroundPoint }
function RandPoint(const Rect:TRect):TPoint;
begin
Result.x:=Rect.Left+Random(Rect.Right-Rect.Left+1);
Result.y:=Rect.Top+Random(Rect.Bottom-Rect.Top+1);
end;
procedure RandPointArray(var arr:TPointArray;const Rect:TRect;Size:Integer);
var I:Integer;
begin
SetLength(arr,Size);
for I:=0 to Size-1 do arr[i]:=RandPoint(Rect);
end;
function DistancePointFromLine(const P,A,B:TPoint):Double;
var dx,dy,sdx,sdy,qx,qy,qdx,qdy:Integer;
begin
dx:=B.x-A.x; dy:=B.y-A.y;
qx:=P.x-A.x; qy:=P.y-A.y;
sdx:=dx*dx; sdy:=dy*dy;
qdx:=qy*dx-qx*dy;
qdy:=qx*dy-qy*dx;
Result:=Sqrt(0.25*qdx*qdx*sdy+0.25*qdy*qdy*sdx)/(sdy+sdx);
if qdy<0 then Result:=-Result;
end;
procedure ShiftLineByValue(const a,b:TPoint;V:Double;out ap,bp:TPoint);
var dx,dy:Integer;
var Len:Double;
begin
dx:=b.x-a.x;
dy:=b.y-a.y;
Len:=V*Sqrt(dy*dy+dx*dx);
ap:=Point(Round((dy*a.x+Len)/dy),Round((dx*a.y-Len)/dx));
bp:=Point(Round((dy*b.x+Len)/dy),Round((dx*b.y-Len)/dx));
end;
function CrossLines(const a,b,c,d:TPoint):TPoint;
var bax,bay,dcx,dcy,qab,qdc:Integer;
begin
bax:=b.x-a.x;
bay:=b.y-a.y;
dcx:=d.x-c.x;
dcy:=d.y-c.y;
qab:=b.x*a.y-b.y*a.x;
qdc:=d.x*c.y-d.y*c.x;
Result:=Point
(
Round((bax*qdc-dcx*qab)/(bay*dcx-dcy*bax)),
Round((dcy*qab-bay*qdc)/(dcy*bax-bay*dcx))
);
end;
function TATriangleAroundPoint.RandRect:TRect;
var sx,sy,mx,my:Integer;
begin
sx:=(ClientWidth)shr(1);
sy:=(ClientHeight)shr(1);
mx:=(sx)shr(2);
my:=(sy)shr(2);
Result:=Rect(sx-mx,sy-my,sx+mx,sy+my);
end;
procedure TATriangleAroundPoint.RandPoints(Size:Integer);
begin
RandPointArray(arr,RandRect,Size);
end;
procedure TATriangleAroundPoint.RandTriangle;
var ab,bc,ca,d:Double;
var pca,pcb,pab,pac,pbc,pba:TPoint;
var I:Integer;
var R:TRect;
begin
R:=RandRect;
while ((a.x=b.x)and(a.y=b.y))or((a.x=c.x)and(a.y=c.y))or((b.x=c.x)and(b.y=c.y)) do
begin
a:=RandPoint(R);
b:=RandPoint(R);
c:=RandPoint(R);
end;
ab:=0;
bc:=0;
ca:=0;
for I:=0 to Length(arr)-1 do
begin
d:=DistancePointFromLine(arr[i],a,b);
if ab<d then ab:=d;
d:=DistancePointFromLine(arr[i],b,c);
if bc<d then bc:=d;
d:=DistancePointFromLine(arr[i],c,a);
if ca<d then ca:=d;
end;
ShiftLineByValue(a,b,ab,pca,pcb);
ShiftLineByValue(b,c,bc,pab,pac);
ShiftLineByValue(c,a,ca,pbc,pba);
a:=CrossLines(pbc,pba,pca,pcb);
b:=CrossLines(pca,pcb,pab,pac);
c:=CrossLines(pab,pac,pbc,pba);
end;
procedure TATriangleAroundPoint.FormClick(Sender: TObject);
begin
RandTriangle;
Invalidate;
end;
procedure TATriangleAroundPoint.FormDblClick(Sender: TObject); // Form.OnCreate - również tu
begin
RandPoints(20);
RandTriangle;
Invalidate;
end;
procedure TATriangleAroundPoint.FormPaint(Sender: TObject);
var I:Integer;
begin
Canvas.Brush.Style:=bsClear;
Canvas.Pen.Style:=psSolid;
Canvas.Pen.Width:=1;
Canvas.Pen.Color:=clSkyBlue;
Canvas.MoveTo(A.x,A.y);
Canvas.LineTo(B.x,B.y);
Canvas.LineTo(C.x,C.y);
Canvas.LineTo(A.x,A.y);
Canvas.Pen.Style:=psClear;
Canvas.Brush.Style:=bsSolid;
Canvas.Brush.Color:=clBlack;
for I:=0 to Length(arr)-1 do Canvas.Ellipse(arr[I].x-2,arr[I].y-2,arr[I].x+3,arr[I].y+3);
Canvas.Brush.Color:=clRed;
Canvas.Ellipse(A.x-2,A.y-2,A.x+3,A.y+3);
Canvas.Brush.Color:=clBlue;
Canvas.Ellipse(B.x-2,B.y-2,B.x+3,B.y+3);
Canvas.Brush.Color:=clGreen;
Canvas.Ellipse(C.x-2,C.y-2,C.x+3,C.y+3);
end;
initialization
Randomize;
end.
Pod Delphi też powinno działać bez problemów.