bb.donnay-software.com

Donnay Software Web Forums
It is currently Tue Aug 04, 2020 1:35 am

All times are UTC - 7 hours




Post new topic Reply to topic  [ 8 posts ] 
Author Message
PostPosted: Thu Mar 10, 2016 10:15 pm 
Offline
User avatar

Joined: Wed Feb 24, 2010 3:44 pm
Posts: 1189
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 )
Attachment:
TriAngle_1000_Ribs.jpg
TriAngle_1000_Ribs.jpg [ 133.19 KiB | Viewed 12454 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
Attachment:
TriAngle_1000_Gradient.jpg
TriAngle_1000_Gradient.jpg [ 83.72 KiB | Viewed 12454 times ]

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

Attachment:
File comment: "pure" Xbase++ Source, no LIB need
DLT_Source.ZIP [44.08 KiB]
Downloaded 569 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


Top
 Profile  
 
PostPosted: Fri Mar 11, 2016 5:02 am 
Offline
User avatar

Joined: Sat Feb 04, 2012 2:23 am
Posts: 1349
Location: Russia, Southern federal district, city of Krasnodar
Thank you, Jimmy! Most recently, I is not even dream! I will study.

_________________
http://lc.kubagro.ru/
https://www.researchgate.net/profile/Eugene_Lutsenko
http://ej.kubagro.ru/
http://ej.kubagro.ru/a/viewaut.asp?id=11


Top
 Profile  
 
PostPosted: Fri Mar 11, 2016 7:17 am 
Offline
Site Admin
User avatar

Joined: Wed Jan 27, 2010 6:58 pm
Posts: 4144
Location: Boise, Idaho USA
Excellent work, Jimmy. Thank you for helping Eugene on this project.

_________________
The eXpress train is coming - and it has more cars.


Top
 Profile  
 
PostPosted: Fri Mar 11, 2016 11:55 pm 
Offline
User avatar

Joined: Wed Feb 24, 2010 3:44 pm
Posts: 1189
Perform Patch 1

Fixed Error :

1.) RANDOMINT() can generate "dupe" Points ... this is not allowed
Code:
   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:
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:
#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%
Attachment:
DLT_PATCH1_19968.jpg
DLT_PATCH1_19968.jpg [ 16.95 KiB | Viewed 12411 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:
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:
File comment: v1.9.355 EXE only
DLT004.ZIP [36.7 KiB]
Downloaded 503 times

_________________
greetings by OHR
Jimmy
Top
 Profile  
 
PostPosted: Sat Mar 12, 2016 2:40 pm 
Offline
Site Admin
User avatar

Joined: Wed Jan 27, 2010 6:58 pm
Posts: 4144
Location: Boise, Idaho USA
Quote:
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:
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 477 times

_________________
The eXpress train is coming - and it has more cars.
Top
 Profile  
 
PostPosted: Sat Mar 12, 2016 3:32 pm 
Offline
User avatar

Joined: Wed Feb 24, 2010 3:44 pm
Posts: 1189
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


Top
 Profile  
 
PostPosted: Sun Mar 13, 2016 11:11 am 
Offline
User avatar

Joined: Sat Feb 04, 2012 2:23 am
Posts: 1349
Location: Russia, Southern federal district, city of Krasnodar
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 606 times

_________________
http://lc.kubagro.ru/
https://www.researchgate.net/profile/Eugene_Lutsenko
http://ej.kubagro.ru/
http://ej.kubagro.ru/a/viewaut.asp?id=11
Top
 Profile  
 
PostPosted: Wed Mar 16, 2016 1:31 pm 
Offline
User avatar

Joined: Sat Feb 04, 2012 2:23 am
Posts: 1349
Location: Russia, Southern federal district, city of Krasnodar
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 12338 times ]
tr18a.jpg
tr18a.jpg [ 236.47 KiB | Viewed 12338 times ]
tr18.rar [817.3 KiB]
Downloaded 516 times

_________________
http://lc.kubagro.ru/
https://www.researchgate.net/profile/Eugene_Lutsenko
http://ej.kubagro.ru/
http://ej.kubagro.ru/a/viewaut.asp?id=11
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group