Delaunay Triangulation

Delaunay triangulation adalah model yang saya gunakan untuk membuat mesh berbentuk segitiga. Mesh berbentuk segitiga berbeda dengan mesh berbentuk grid. Mesh segitiga tidak ada aturan antara titik koordinat yang satu dengan titik koordinat yang lain.

Misal, pada data batimetri yang tidak berbentuk grid berdasarkan hasil pengukuran di lautan. Maka setiap koordinat x dan y tidak berubah secara beraturan sehingga perlu cara untuk memecahkan persoalan ini, yaitu dengan konsep Delaunay Triangulation. Konsep Delaunay secara lengkap bisa dibaca di http://en.wikipedia.org/wiki/Delaunay_triangulation

Dengan menggunakan bahasa pemrograman Delphi 7, saya berhasil membuat ulang script untuk membuat Delaunay Triangulation, dan dapat di download.

secara singkat saya jelaskan Delaunay Triangulation di bawah ini :

PTitik=^TTitik;                   //  Pointer untuk titik
PSisi=^TSisi;                     //  Pounter untuk Sisi
PSegitiga=^TSegitiga;             //  Pointer untuk segitiga

TTitik=record
  x,y:real;                       //  absis dan ordinat suatu titik
end;
TSisi=record
  index1,index2:integer;          //  nomor index titik 
end;
TSegitiga=record
  index1,index2,index3:integer;   //  nomor Index titik
  xp,yp:real;                     //  titik pusat segitiga
  r:real;                         //  jari-jari pusat segitiga
end;

TMesh=class                       //  Class untuk membuat mesh
private
  FTitik,FSegitiga,FSisi:TList;
  max_x,max_y:real;
  min_x,min_y:real;
  function GetTitik(Index:Integer):TTitik;
  function AddSegitiga(Data:TSegitiga):Integer;
  function GetSegitiga(index:integer):TSegitiga;
  function AddSisi(sisi:TSisi):integer;
  function GetSisi(index:integer):TSisi;
  procedure SetSisi(index:integer;Sisi:TSisi);
  function Jumlahsegitiga:integer;
  function Jumlahtitik:integer;
public
  constructor Create;
  destructor Destroy;override;
  function AddTitik(x,y:real;ori:boolean=true):integer;
  procedure BuiltSegitiga;
  procedure GambarSegitiga(Bitmap:TBitmap);
published
  property Jumlah_Segitiga:integer read Jumlahsegitiga;
  property Jumlah_Titik:integer read Jumlahtitik;
end;

Untuk contoh penggunaan script ini bisa dilihat di bagian bawah ini :

procedure TForm1.FormCreate(Sender: TObject);
var Mesh:TMesh;
  Bitmap:TBitmap;
  i:integer;
begin
  Mesh:=TMesh.Create;
  try
    randomize;
    for i:=1 to 100 do
    mesh.AddTitik(random(100),random(100));
    mesh.BuiltSegitiga;
    bitmap:=TBitmap.Create;
    try
      bitmap.Width:=510;
      bitmap.Height:=510;
      bitmap.PixelFormat:=pf24bit;
      image1.Picture.Assign(bitmap);
      bitmap.Width:=500;
      bitmap.Height:=500;
      bitmap.Canvas.Brush.Color:=clred;
      mesh.GambarSegitiga(Bitmap);
      image1.Canvas.Draw(5,5,bitmap);
      image1.AutoSize:=true;
    finally bitmap.Destroy; end;
  finally Mesh.Destroy; end;
end;

Hasil Delaunay Triangulation

Script lengkapnya dapat di download di sini

Insyaallah pada post selanjutnya akan dibahas pula cara Contouring berdasarkan hasil Triangulation. Semoga bermanfaat