Delaunay triangulation : PAS Code to Xbase++

[Auge_Ohr]

based on include PAS Source i have translate it into Xbase++ Class Code.
it do work fine with 100 Point but using 1000 Points it take > 4 Hour ( FX8350 : Xbase++ using 1 CPU of 8 )

TriAngle_1000_Ribs.jpg (133.19 KiB) Viewed 24436 times

this is not while Xbase++ is so slow ... it is the "simple" Logic of the PAS Code
to find 1st Ribs PAS Source have 3 Loops -> 1000*1000*1000 so you can imagine how long it take.

after calculate Triangle you can use Color of each Point to create a Texture with GraGradient

TriAngle_1000_Gradient.jpg (83.72 KiB) Viewed 24436 times

! Note :
this work will normal be done by Grafic Card using DirectX which is 1000 % faster than GDI/GDI+

DLT_Source.ZIP

"pure" Xbase++ Source, no LIB need

(44.08 KiB) Downloaded 1443 times

Syntax : DLT.EXE <cNumPoints> // default 100

if you have "save" last Calculation it will load from DBF at Start and "Repaint Ribs" will be enable.

[Eugene Lutsenko]

Thank you, Jimmy! Most recently, I is not even dream! I will study.

[rdonnay]

Excellent work, Jimmy. Thank you for helping Eugene on this project.

[Auge_Ohr]

Perform Patch 1

Fixed Error :

1.) RANDOMINT() can generate "dupe" Points ... this is not allowed

Code: Select all

   DO WHILE .T.
      mX := RANDOMINT( 1, aSize[1]-2)
      mY := RANDOMINT( 1, aSize[2]-2)
  
      // dupe Check
      //
      IF ASCAN(aCheck,{|X| X[1] = mX .AND. X[2] = mY } ) > 0
         LOOP
      ELSE
         AADD(aCheck,{mX,mY})
         EXIT
      ENDIF
   ENDDO

New :

i wonder why FindFirstRib() had 3 Loops in PAS Code just to get P1 & P2 ( Index-Number of Point Array )
i try to find out "what" he is searching for ...

P1 seems to be Max_X, Max_Y while
P2 seems to be Min_X , Max_Y

now i can ASORT Array and find Points "on-fly" instead of 3 Loops ( 1000*1000*1000 )

Code: Select all

METHOD DemoDlg:FindFirstRib()
...
#IFDEF AO_PATCH1
   aTest := ASORT( aTest,,, {|aX,aY| STR(aX[1])+STR(aX[2]) < ;
                                     STR(aY[1])+STR(aY[2]) } )
   ::Ribs[1].p2 := aTest[P2][3] // { Min_X,Max_Y }


   aTest := ASORT( aTest,,, {|aX,aY| STR(aX[2])+STR(aX[1]) > ;
                                     STR(aY[2])+STR(aY[1]) } )
   ::Ribs[1].p1 := aTest[P1][3] // { Max_X,Max_Y }
#ENDIF

! Note : i have add 4 Points on Edge to "fill Screen" which might be the Reason that this works (fast)


while "FindPoint()" try R1 & R2 there will be a lot of "dupe" ( 20-30 % )

Code: Select all

#IFDEF AO_PATCH1
   IF ASCAN(::aDupe,{|x| x[1] = r1 .AND. x[2] = r2  }) > 0
      RETURN(0)
   ELSE
      AADD(::aDupe,{r1,r2})
   ENDIF
#ENDIF

but it still use 2 FOR / NEXT Loop to compare with "each other" Point it a Circle match ...

those "Patch" have reduce "solve" for 100 Point to < 20000 ( we have start with > 37000 ) so Time decrease about 50%

DLT_PATCH1_19968.jpg (16.95 KiB) Viewed 24393 times

coming next :

i have ASORT(::aPoints, ...) ... what about calculate Distance and create a Matrix ...
i can get Distance R1 to every other Point and same with R2

Code: Select all

METHOD DemoDlg:Distance(aPos1,aPos2)
LOCAL nLen:=Len(aPos1), i, nTotal
/* For 1,2,3, or notional Dimensions, perform a Distance calculation */
  nTotal:=0
  FOR i:=1 TO len(aPos1)
    nTotal+=((aPos1[i]-aPos2[i])^2)
  NEXT i
RETURN Sqrt(nTotal)

i have already implement in Source ...

i guess i still need 2 FOR / NEXT Loop but i can begin with shortest Distance of R1 / R2
... to be continue

[rdonnay]

it do work fine with 100 Point but using 1000 Points it take > 4 Hour

Jimmy -

I optimized the code by using LOCAL variables in your loops.
Look at the small test program:

Three (3) loops run for 1 million iterations each.

Loop 1 accesses all iVars
Loop 2 accesses all Locals
Loop 3 accesses Locals that point to iVars

Notice that the loops that only access locals run 4 times faster.
Accessing iVars and Methods takes longer because classes are dynamically created and use symbols whereas locals are pushed onto a stack.

Code: Select all

FUNCTION Main()

LOCAL oTest := Test():new(), nTest := 1000000, aTest[nTest], ;
      nSeconds, cTest := 'test2', i

nSeconds := Seconds()
FOR i := 1 TO oTest:test1
  oTest:testArray[i] := oTest:test2
NEXT

? '      Ivars:', Seconds() - nSeconds

nSeconds := Seconds()
FOR i := 1 TO nTest
  aTest[i] := cTest
NEXT

? '     Locals:', Seconds() - nSeconds

nSeconds := Seconds()
nTest := oTest:test1
aTest := oTest:testArray
cTest := oTest:test2
FOR i := 1 TO nTest
  aTest[i] := cTest
NEXT

? 'Local Ivars:', Seconds() - nSeconds
wait

RETURN nil

* ----------

CLASS Test

   EXPORTED:

   VAR test1
   VAR test2
   VAR testArray

   INLINE METHOD Init()

   ::test1 := 1000000
   ::test2 := 'test2'
   ::testArray := Array(::test1)

   RETURN self

ENDCLASS

I have attached an updated DLT_NEW.PRG in which I have made local pointers to the arrays.

My tests show about a 60% to 100% performance improvement.

[Auge_Ohr]

I optimized the code by using LOCAL variables in your loops.
...
My tests show about a 60% to 100% performance improvement.

WOW ... i did not know that LOCAL are so much faster, THX

[Eugene Lutsenko]

Finally, with the help of Roger, Jimmy and developer of Belarus Dmitry, who proposed algorithm in Pascal, I was able to do what I wanted.

http://lc.kubagro.ru/Dima/tr17.rar
Thank you all for your time. For me, this result is very valuable. I hope this will be useful not only to me

[Eugene Lutsenko]

based on include PAS Source i have translate it into Xbase++ Class Code.
it do work fine with 100 Point but using 1000 Points it take > 4 Hour ( FX8350 : Xbase++ using 1 CPU of 8 )

We Dimitri from Belarus advanced algorithms. Now Delaunay triangulation points 1000 are less than 8 minutes (not including time to search the first rib). Below is working with the source code program:
http://lc.kubagro.ru/Dima/tr18.rar