Многоугольник, Fpc, Ооп, Оптимизация Опции

[Bokul]

Реализовал объект многоугольник, который имеет неопределенное количество вершин. Но скорость работы с ним критическая, поэтому надо как можно сильнее его оптимизировать.
Вот, что он из себя представляет:

  
unit Polygone;
interface
uses UnitTVector,ListOfVertex,objects;
    TPPolygone=^TPolygone;
    TPolygone=object
       List:TVertexList;//Кольцевой список
       constructor init;//инициализируем поля
       procedure   AddVertex(x,y:integer);//добавляем вершину, x,y - ее координаты
       procedure   Increase(Const vector:TVector);//Увеличиваем координаты всех вершины на вектор vector, описание - ниже
       procedure   Decrease(Const vector:TVector);//Уменьшаем координаты всех вершины на вектор vector, описание - ниже
       procedure   ForEach(proc:ToDO);//Проделываем процедуру типа ToDO с каждой вершиной
       function    ContainsPoint(point:TPoint):boolean;//входит ли точка point в объект
       function    IsInside(OtherPolyg:TPolygone):boolean;//входит ли объект в OtherPolyg
       function    ContainsOtherPolyg(OtherPolyg:TPolygone):boolean;// входит ли OtherPolyg в объект
       destructor  done;//Удаляем все поля
    end;

Кольцевой список

unit ListOfVertex;
interface
uses objects;
type
   ToDo=procedure(point:TPoint);//тип процедуры, вызываемой с ForEach

   TPVertexItem=^TVertexItem;//элемент списка
   TVertexItem=record
      vertex:TPoint;//информационная часть - координаты вершины
      next:TPVertexItem;
   end;

   TPVertexList=^TVertexList;
   TVertexList=object
      Last:TPVertexItem;
      constructor init;//инициализируем поля
      procedure   AddElement(data:TPoint);//добавляем новый элемент
      function    DeleteElement(p:TPVertexItem):boolean;//удаляем элемент
      procedure   ForEach(proc:ToDo);//Проделываем процедуру типа ToDO с каждым элементом
      destructor  done;//удаляемся
   end;

Модуль для работы с векторами

unit UnitTVector;
interface
Type
    TVector=record
       X,Y:integer;
    end;
Operator + (Const v1,v2:TVector) R:TVector; //складываем два вектора
Operator - (Const v1,v2:TVector) R:TVector;//отнимаем от первого вектора второй
Operator * (Const k:double; v:TVector) R:TVector;//перемножаем вектор на коэффициент k
Operator * (Const v:TVector; k:double) R:TVector;//тоже самое, только другой порядок
Operator / (Const v:TVector; k:double) R:TVector;//делим вектор на коэффициент 

Программа для проверки минимальной работоспособности

uses crt,ListOfVertex,objects, UnitTVector, Polygone;
procedure Show(p:TPoint);
begin
  writeln('X = ',p.x,' Y = ',p.y);
end;

var obj1,obj2:TPPolygone;
    p1:TPoint;
    mem:longint;
    vector:TVector;
begin
  clrscr;
  mem:=GetHeapStatus.TotalFree;
  vector.x:=4;
  vector.y:=8;
  p1.x:=40;
  p1.y:=50;
  new(obj2,init);
  with obj2^ do
       begin
            AddVertex(30,10);
            AddVertex(30,20);
            AddVertex(50,20);
            AddVertex(50,10);
       end;
  new(obj1,init);
  with obj1^ do
       begin
            AddVertex(10,10);
            AddVertex(40,60);
            AddVertex(1000,10);
            writeln('First');
            ForEach(show);
            writeln;
            writeln('Point x=',p1.x,' y=',p1.y);
            if ContainsPoint(p1) then writeln('First contains Point')
            else writeln('First does not contain Point');
            writeln; 
            Writeln('After decrease: ');
            writeln('Vector: x=',vector.x,' y=',vector.y);
            decrease(vector);
            ForEach(show);
            writeln;
            writeln('Second');
            obj2^.ForEach(show);
            if ContainsOtherPolyg(obj2^) then writeln('First contains second object')
            else writeln('First does not contain second object');
            if IsInside(obj2^) then writeln('Second is inside first object')
            else writeln('Second is not inside first object');
       end;
  dispose(obj1,done);
  dispose(obj2,done);
  writeln;
  writeln('Difference: ',mem-GetHeapStatus.TotalFree);
  readln;
end.

Три модуля вмести:  Polygone.rar ( 13.71 килобайт ) Кол-во скачиваний: 448


PS в принципе код прозрачен, но если что-то не понятно - спрашивайте.

[volvo]

Попытался добавить статистику, но как-то не сильно она хочет работать

Чего-то ты переусложнил по-моему работу со статистикой... Смотри, как это же делал бы я:
1. Пишем очень простой модуль:

unit stat;

interface

type
  tstatindex = (
    siInit, siAddVertex, siIncrease, siDecrease,
    siForEach, siContainsPoint, siContainsOtherPolyg,
    siInside, siDone);
  tstatrec = record
    time: dword;
    counter: dword;
  end;

var
  stat_array: array[tstatindex] of tstatrec;

  // Назначение следующих 2-х переменных поймешь позже...
  curr_stat: tstatindex;
  curr_T: dword;

procedure print_stat;

implementation

const
  title: array[tstatindex] of string = (
    'Init',
    'siAddVertex',
    'siIncrease',
    'siDecrease',
    'siForEach',
    'siContainsPoint',
    'siContainsOtherPolyg',
    'siInside',
    'siDone'
  );

procedure print_stat;
var i: tstatindex;
begin
  writeln('methods calling:');
  for i := low(tstatindex) to high(tstatindex) do
    with stat_array[ i ] do begin
      write(title[ i ] + ': ', 'count:: ', counter:6,
              ' time:: ', time:6);

      if counter =  0    then writeln(' zero division')
      else writeln(' average:: ', (time / counter): 10 :5);
    end;
end;

end.

Как видишь - ничего особенного, просто выделяем место для хранения статистики, и процедура для их печати

2. Пишем 2 очень маленьких файлика:
before.inc

begin
  inc(stat_array[curr_stat].counter);
  curr_T := gettickcount();
end;

и
after.inc

begin
  inc(stat_array[curr_stat].time, gettickcount() - curr_T);
end;

3. Зачем? А вот зачем: теперь вместо конструкции вида:

procedure   TPolygone.ForEach(proc:ToDO);
{$ifdef StatisticPolygone}var t:dword;   {$endif}
begin
  {$ifdef StatisticPolygone}
     t:=gettickcount();
  {$endif}

  list.foreach(proc);

  {$ifdef StatisticPolygone}
     inc(Stat.ForEach.time,gettickcount-t);
     inc(Stat.ForEach.n);
  {$endif}
end;

достаточно написать

procedure   TPolygone.ForEach(proc:ToDO);
begin
  curr_stat := siForEach;
  {$i before.inc}

  list.foreach(proc);

  {$i after.inc}
end;

(понятно назначение тех двух переменных - я ввел их просто чтобы не описывать вот эти вои локальные переменные, и сэкономить этим на объеме текста)... А проверять {$ifdef StatisticPolygone} можно и внутри файлов before.inc/after.inc

Переделал твою программу, добавив в нее свой модуль статистики - вот что получилось:

ForEach: Number: 10000 Time: 15 Time for each: 0.001500
Increase: Number: 10000 Time: 0 Time for each: 0.000000
Decrease: Number: 10000 Time: 15 Time for each: 0.001500
ContainsPoint: Number: 10000 Time: 47 Time for each: 0.004700
ContainsOtherPolyg: Number: 10000 Time: 0 Time for each: 0.000000
IsInside: Number: 10000 Time: 0 Time for each: 0.000000
methods calling:
Init: count:: 10000 time:: 0 average:: 0.00000
siAddVertex: count:: 1000000 time:: 250 average:: 0.00025
siIncrease: count:: 10000 time:: 0 average:: 0.00000
siDecrease: count:: 10000 time:: 15 average:: 0.00150
siForEach: count:: 10000 time:: 15 average:: 0.00150
siContainsPoint: count:: 30000 time:: 47 average:: 0.00157
siContainsOtherPolyg: count:: 10000 time:: 0 average:: 0.00000
siInside: count:: 20000 time:: 0 average:: 0.00000
siDone: count:: 0 time:: 0 zero division
Difference: -79872

По-моему, больше похоже на правду... А насчет Difference я тебе уже сказал в другой теме, куда смотреть...