Delaunay triangulation : PAS Code to Xbase++

This forum is for ideas and or code to be contributed for general use.
Post Reply
Message
Author
User avatar
Auge_Ohr
Posts: 1405
Joined: Wed Feb 24, 2010 3:44 pm

Delaunay triangulation : PAS Code to Xbase++

#1 Post by 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
TriAngle_1000_Ribs.jpg (133.19 KiB) Viewed 20888 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
TriAngle_1000_Gradient.jpg (83.72 KiB) Viewed 20888 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 1108 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.
greetings by OHR
Jimmy

User avatar
Eugene Lutsenko
Posts: 1649
Joined: Sat Feb 04, 2012 2:23 am
Location: Russia, Southern federal district, city of Krasnodar
Contact:

Re: Delaunay triangulation : PAS Code to Xbase++

#2 Post by Eugene Lutsenko »

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

User avatar
rdonnay
Site Admin
Posts: 4722
Joined: Wed Jan 27, 2010 6:58 pm
Location: Boise, Idaho USA
Contact:

Re: Delaunay triangulation : PAS Code to Xbase++

#3 Post by rdonnay »

Excellent work, Jimmy. Thank you for helping Eugene on this project.
The eXpress train is coming - and it has more cars.

User avatar
Auge_Ohr
Posts: 1405
Joined: Wed Feb 24, 2010 3:44 pm

Re: Delaunay triangulation : PAS Code to Xbase++

#4 Post by 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
DLT_PATCH1_19968.jpg (16.95 KiB) Viewed 20845 times
coming next :

i have ASORT(::aPoints, ...) :think: ... what about calculate Distance and create a Matrix ... :idea:
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
Attachments
DLT004.ZIP
v1.9.355 EXE only
(36.7 KiB) Downloaded 1013 times
greetings by OHR
Jimmy

User avatar
rdonnay
Site Admin
Posts: 4722
Joined: Wed Jan 27, 2010 6:58 pm
Location: Boise, Idaho USA
Contact:

Re: Delaunay triangulation : PAS Code to Xbase++

#5 Post by 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.
Attachments
dlt_new.zip
(7.08 KiB) Downloaded 987 times
The eXpress train is coming - and it has more cars.

User avatar
Auge_Ohr
Posts: 1405
Joined: Wed Feb 24, 2010 3:44 pm

Re: Delaunay triangulation : PAS Code to Xbase++

#6 Post by Auge_Ohr »

rdonnay wrote: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
greetings by OHR
Jimmy

User avatar
Eugene Lutsenko
Posts: 1649
Joined: Sat Feb 04, 2012 2:23 am
Location: Russia, Southern federal district, city of Krasnodar
Contact:

Re: Delaunay triangulation : PAS Code to Xbase++

#7 Post by 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.
Image
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
Attachments
tr17.rar
(91.53 KiB) Downloaded 1142 times

User avatar
Eugene Lutsenko
Posts: 1649
Joined: Sat Feb 04, 2012 2:23 am
Location: Russia, Southern federal district, city of Krasnodar
Contact:

Re: Delaunay triangulation : PAS Code to Xbase++

#8 Post by Eugene Lutsenko »

Auge_Ohr wrote: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
Attachments
tr18b.jpg
tr18b.jpg (300.83 KiB) Viewed 20772 times
tr18a.jpg
tr18a.jpg (236.47 KiB) Viewed 20772 times
tr18.rar
(817.3 KiB) Downloaded 1036 times

Post Reply