Solved

Line generalization algorithm

Posted on 2003-11-24
3
525 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

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Suggested Solutions

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…
Hello everybody This Article will show you how to validate number with TEdit control, What's the TEdit control? TEdit is a standard Windows edit control on a form, it allows to user to write, read and copy/paste single line of text. Usua…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This tutorial demonstrates a quick way of adding group price to multiple Magento products.

708 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

17 Experts available now in Live!

Get 1:1 Help Now