Solved

Line generalization algorithm

Posted on 2003-11-24
3
528 Views
Last Modified: 2010-04-03
Dear Sir/Madam,
I need to write a program in delphi to do line generalization.  Douglas Peucker Algorithm is adopted to generalize the line.  There are 2 units for my program and they are 'main' and 'douglas peucker'.  The algorithm works quite good but there is some problem for the 'main' unit.

At present, I can draw a line on the canva by using the mouse and press 'Simplify' to generalize the line.  However, I wish to draw a line by the following formula instead of using mouse as an input but I failed at last. So I need help to write some codes to incorporate the formula to 'main' unit.

X:=-3+6*i/100 (where i is 1, 2, 3......)
Y:=cos(X)+0.3*sin(4*X)+random(10)/100

The source of 'main' unit and 'douglas peucker' unit are as follows:

1. 'Main' Unit

unit Main;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ExtCtrls, Contnrs, DouglasPeuckers, OpenGL;

type
  TForm1 = class(TForm)
    pbMain: TPaintBox;
    Label5: TLabel;
    Label6: TLabel;
    lbNumPtsOrig: TLabel;
    Label7: TLabel;
    lbNumPtsSimple: TLabel;
    Button1: TButton;
    procedure pbMainPaint(Sender: TObject);
//    procedure pbMainMouseDown(Sender: TObject; Button: TMouseButton;
//      Shift: TShiftState; X, Y: Integer);
    procedure pbMainMouseMove(Sender: TObject; Shift: TShiftState; X,
      Y: Integer);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
    procedure AddPointToCurve(X, Y: integer);
    procedure CreateSimplifiedPolyline;
  public
    OrigList: array of TPoint;
    SimpleList: array of TPoint;
  end;

var
  Form1: TForm1;



implementation

{$R *.DFM}

procedure TForm1.AddPointToCurve(X, Y: integer);
var
  APoint: TPoint;
  //i:integer;
begin
//randomize;
  //PosX := X;
  //PosY := Y;
  APoint.X := X;
  APoint.Y := Y;
  SetLength(OrigList, Length(OrigList) + 1);
  OrigList[Length(OrigList) - 1] := APoint;
end;

procedure TForm1.pbMainPaint(Sender: TObject);
begin
  with pbMain.Canvas do begin
    // Draw original polyline
    if Length(OrigList) > 0 then begin
      Pen.Color := clBlack;
      Pen.Width := 1;
      PolyLine(OrigList);
    end;

    // Draw simplification
    if Length(SimpleList) > 0 then begin
      Pen.Color := clRed;
      Pen.Width := round(1);
      PolyLine(SimpleList);
    end;

  end;
  // Other controls
  lbNumPtsOrig.Caption   := IntToStr(Length(OrigList));
  lbNumPtsSimple.Caption := IntToStr(Length(SimpleList));
end;

procedure TForm1.pbMainMouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
begin
      // Store the new point
      AddPointToCurve(X, Y);
      pbMain.Invalidate;
    end;
  //end;
//end;

procedure TForm1.CreateSimplifiedPolyline;
// Create the simple polyline approximation
var
  ALength: integer;
  s:string;
  r:integer;
  begin
  s:=InputBox('Input Box','Please Input the Tolerance','0');
  r:=strtoint(s);
  // Create the simple polyline approximation
  SetLength(SimpleList, Length(OrigList));
  if length(OrigList) > 2 then begin
    ALength := PolySimplifyInt2D(r, OrigList, SimpleList);
    SetLength(SimpleList, ALength);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  // the button is pressed to draw the simplified line
  CreateSimplifiedPolyline;
  pbMain.Invalidate;
end;

end.

2. 'Douglas Peucker' Unit

unit DouglasPeuckers;

interface

uses
  OpenGL, Windows;// We use TPoint from the windows unit

type

  // Generalized float and int types
  TFloat = double;



{ PolySimplifyInt2D:
  Approximates the polyline with 2D integer vertices in Orig, with a simplified
  version that will be returned in Simple. The maximum deviation from the
  original line is given in Tol.
  Input:  Tol      = approximation tolerance
          Orig[]   = polyline array of vertex points
  Output: Simple[] = simplified polyline vertices. This array must initially
                     have the same length as Orig
  Return: the number of points in Simple
}
function PolySimplifyInt2D(Tol: TFloat; const Orig: array of TPoint;
  var Simple: array of TPoint): integer;

implementation

function VecMinInt2D(const A, B: TPoint): TPoint;
// Result = A - B
begin
  Result.X := A.X - B.X;
  Result.Y := A.Y - B.Y;
end;

function DotProdInt2D(const A, B: TPoint): TFloat;
// Dotproduct = A * B
begin
  Result := A.X * B.X + A.Y * B.Y;
end;

function NormSquaredInt2D(const A: TPoint): TFloat;
// Square of the norm |A|
begin
  Result := A.X * A.X + A.Y * A.Y;
end;

function DistSquaredInt2D(const A, B: TPoint): TFloat;
// Square of the distance from A to B
begin
  Result := NormSquaredInt2D(VecMinInt2D(A, B));
end;

procedure SimplifyInt2D(var Tol2: TFloat; const Orig: array of TPoint;
  var Marker: array of boolean; j, k: integer);
// Simplify polyline in OrigList between j and k. Marker[] will be set to True
// for each point that must be included
var
  i, MaxI: integer; // Index at maximum value
  MaxD2: TFloat;    // Maximum value squared
  CU, CW, B: TFloat;
  DV2: TFloat;
  P0, P1, PB, U, W: TPoint;
begin
  // Is there anything to simplify?
  if k <= j + 1 then exit;

  P0 := Orig[j];
  P1 := Orig[k];
  U  := VecMinInt2D(P1, P0); // Segment vector
  CU := DotProdInt2D(U, U); // Segment length squared
  MaxD2 := 0;
  MaxI  := 0;

  // Loop through points and detect the one furthest away
  for i := j + 1 to k - 1 do begin
    W  := VecMinInt2D(Orig[i], P0);
    CW := DotProdInt2D(W, U);

    // Distance of point Orig[i] from segment
    if CW <= 0 then begin
      // Before segment
      DV2 := DistSquaredInt2D(Orig[i], P0)
    end else begin
      if CW > CU then begin
        // Past segment
        DV2 := DistSquaredInt2D(Orig[i], P1);
      end else begin
        // Fraction of the segment
        try
          B := CW / CU;
        except
          B := 0; // in case CU = 0
        end;
        PB.X := round(P0.X + B * U.X);
        PB.Y := round(P0.Y + B * U.Y);
        DV2 := DistSquaredInt2D(Orig[i], PB);
      end;
    end;

    // test with current max distance squared
    if DV2 > MaxD2 then begin
      // Orig[i] is a new max vertex
      MaxI  := i;
      MaxD2 := DV2;
    end;
  end;

  // If the furthest point is outside tolerance we must split
  if MaxD2 > Tol2 then begin // error is worse than the tolerance

    // split the polyline at the farthest vertex from S
    Marker[MaxI] := True;  // mark Orig[maxi] for the simplified polyline

    // recursively simplify the two subpolylines at Orig[maxi]
    SimplifyInt2D(Tol2, Orig, Marker, j, MaxI); // polyline Orig[j] to Orig[maxi]
    SimplifyInt2D(Tol2, Orig, Marker, MaxI, k); // polyline Orig[maxi] to Orig[k]

  end;
end;

function PolySimplifyInt2D(Tol: TFloat; const Orig: array of TPoint;
  var Simple: array of TPoint): integer;
var
  i, N: integer;
  Marker: array of boolean;
  Tol2: TFloat;
begin
  Result := 0;
  if length(Orig) < 2 then exit;
  Tol2 := sqr(Tol);

  // Create a marker array
  N := Length(Orig);
  SetLength(Marker, N);
  // Include first and last point
  Marker[0]     := True;
  Marker[N - 1] := True;
  // Exclude intermediate for now
  for i := 1 to N - 2 do
    Marker[i] := False;

  // Simplify
  SimplifyInt2D(Tol2, Orig, Marker, 0, N - 1);

  // Copy to resulting list
  for i := 0 to N - 1 do begin
    if Marker[i]  then begin
      Simple[Result] := Orig[i];
      inc(Result);
    end;
  end;
end;

end.



Many thanks

Regards,

Kenneth
0
Comment
Question by:kennethtsui
  • 2
3 Comments
 
LVL 8

Expert Comment

by:gmayo
ID: 9811844
Not sure of your exact question - are you only asking how to draw a line on a form with the formula provided, or is it more in depth than that? I've assumed the former:

var i : integer;

for i := 1 to 10 do begin
  X:=-3+6*i/100 (where i is 1, 2, 3......)
  Y:=cos(X)+0.3*sin(4*X)+random(10)/100
  if i = 0 then Canvas.MoveTo(Round(X), Round(Y)) else Canvas.LineTo(Round(X), Round(Y));
end;

Depending on whether you are using degrees or radians, you may also need (for degrees, the above works for radians):
  Y:=cos(DegToRad(X))+0.3*sin(DegToRad(4*X))+random(10)/100

Geoff M.
0
 

Author Comment

by:kennethtsui
ID: 9815213
Dear Geoff M.

Thank you for your reply. Yes, I wish to draw a line on the canva by using the mentioned formulas which provide X and Y position.  By the way, I have 2 more problems.

1. The array show in the 'main' unit is a dynamic array.  If I use the loop function (i.e. for i=1 to 10 do begin) as you suggest, could it be ok?

2. With reference to the 'main' unit shown in the question, where should I insert your code?

I am sorry that I am a newbie to Delphi so maybe my question is not clear.  I am looking forward for your kind assistance.

Many thanks.
0
 
LVL 8

Accepted Solution

by:
gmayo earned 75 total points
ID: 9816528
1. In that case you can use the Low and High functions, which return the lowest index (0 for open arrays, but good practice to use the function rather than a magic number) and the highest index respectively. So that line should read "for i := Low(i) to High(i) do begin".

2. Probably in your pbMainPaint routine. However, as there is a random number in the loop, everytime the form gets redrawn, that line will change. It will get redrawn when another form obscures part of your form or when you drag it off-screen and back on again.

You might also want to call Randomize once at the start of your program, which makes sure you don't get the same "random" numbers each time.

Geoff M.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Need Delphi function to get Youtube video title 5 227
How to renew a Delphi rad-studio licence? 5 49
How to debug For loops? 3 46
RESTRequest Parameter 4 15
A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
Introduction I have seen many questions in this Delphi topic area where queries in threads are needed or suggested. I know bumped into a similar need. This article will address some of the concepts when dealing with a multithreaded delphi database…
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …
Windows 10 is mostly good. However the one thing that annoys me is how many clicks you have to do to dial a VPN connection. You have to go to settings from the start menu, (2 clicks), Network and Internet (1 click), Click VPN (another click) then fi…

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

25 Experts available now in Live!

Get 1:1 Help Now