sketchucation logo sketchucation
    • Login
    ℹ️ Licensed Extensions | FredoBatch, ElevationProfile, FredoSketch, LayOps, MatSim and Pic2Shape will require license from Sept 1st More Info

    Distance between two points / optimization

    Scheduled Pinned Locked Moved Developers' Forum
    14 Posts 6 Posters 1.5k Views 6 Watching
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • C Offline
      CAUL
      last edited by

      You could try to use a space hash. The code below generate the points well within 1s.

      ` module PointCloud

      def self.init(box_side, min_dist)
      @min_dist = min_dist
      @divs = (box_side / min_dist) - 1.0
      @dInv = 1.0 / (box_side / @divs)
      @hash = []
      (0..@divs - 1).each { |i| @hash << []
      (0..@divs - 1).each { |j| @hash[i] << []
      (0..@divs - 1).each { |k| @hash[i][j] << []
      }}}

      @nBox = []
      [0, -1, 1].each { |i|
        [0, -1, 1].each { |j|
          [0, -1, 1].each { |k|
            @nBox << [i, j, k]
      }}}    
      

      end

      def self.validBox?(xi, yi, zi)
      return xi >= 0 && yi >= 0 && zi >= 0 && xi < @divs && yi < @divs && zi < @divs
      end

      def self.getBox(p)
      x = (p.x * @dInv).floor
      y = (p.y * @dInv).floor
      z = (p.z * @dInv).floor
      return nil unless validBox?(x, y, z)
      return [x, y, z]
      end

      def self.validPoint?(p, ind)
      xi = yi = zi = 0
      @nBox.each { |offset|
      xi = ind[0] + offset[0]; yi = ind[1] + offset[1]; zi = ind[2] + offset[2]
      next unless validBox?(xi, yi, zi)
      box = @hash[xi][yi][zi]
      box.each { |p2| return false if p.distance(p2) < @min_dist }
      }
      return true
      end

      def self.add(p)
      ind = getBox(p)
      return false if ind == nil
      return false unless validPoint?(p, ind)
      @hash[ind[0]][ind[1]][ind[2]] << p
      return true
      end

      def self.main
      mod = Sketchup.active_model
      ent = mod.entities
      res_g = ent.add_group

      box_side = 1000
      min_dist = 50
      no_of_points = 5000
      
      t0 = Time.now
      init(box_side, min_dist)
      (1..no_of_points).each { |i|
        pt = Geom::Point3d.new(rand * box_side, rand * box_side, rand * box_side)
        res_g.entities.add_cpoint(pt) if add(pt)
      }
      t1 = Time.now
      puts (t1 - t0).to_s
      

      end

      main

      end`

      1 Reply Last reply Reply Quote 0
      • jolranJ Offline
        jolran
        last edited by

        @unknownuser said:

        You could try to use a space hash.

        That looks nice! Did you get that from the Geometric Tools library ?
        Ive seen something similar like this before and can't remember where it was.
        Looks useful for other tests as well.

        Edit: the distance Square method gives 0.016 sec for 5000 Points btw...
        About twice as fast as pt.distance(pt)
        Scratch that. I forgot to mute the subtractions. About same as API distance method. So I would suggest trying CAULS method.
        There is probably Little to gain from using distance squared in Ruby vs API methods.

        1 Reply Last reply Reply Quote 0
        • sdmitchS Offline
          sdmitch
          last edited by

          Here are my results with the two code options

          8.400599956512451
          0..5000
          PointCloud.main
          45.5006
          nil
          8.503999948501587
          0..5000
          PointCloud.main
          46.4774
          nil
          8.392800092697144
          0..5000
          PointCloud.main
          45.6526
          nil

          Pascal's averaged 8.4 versus 45.9 for Caul's

          Nothing is worthless, it can always be used as a bad example.

          http://sdmitch.blogspot.com/

          1 Reply Last reply Reply Quote 0
          • jolranJ Offline
            jolran
            last edited by

            @unknownuser said:

            Pascal's averaged 8.4 versus 45.9 for Caul's

            Heh, really ?? 8 seconds vs 45 for 5000 Points ?

            edit:( My timings: Pascal ~ 10 sec, CAUL's module 1.11 sec )
            Then CAUL's method add constructionpoints inside the timings, also.

            I forgot to mention I tested under Su8. So maybe "distance squared" performs better under Ruby2 ? Might be worthwhile to do some profiling after all then.

            (I don't know the accuracy of the test..)

            	mod = Sketchup.active_model
            	sel = mod.selection
            	ents = mod.entities
            
            	sel.clear
            	
            	cps = []
            	saved = []
            
            	maxdist = 1000
            	mindist = 500
            	
            	minSQ = mindist*mindist
            	
            	tp = ents.add_cpoint( ORIGIN ) #testpoint Try offsets from 0,0,0 ?
            	tp = tp.position
            	
            	for i in 0..5000
            		cp = ents.add_cpoint( Geom;;Point3d.new(rand*maxdist,rand*maxdist,rand*maxdist) )
            		cps << cp
            	end
            
            	t = Time.now
            	
            	cps.each{|cp|
            		
            		pt = cp.position
            		
            		x = tp.x-pt.x
            		y = tp.y-pt.y
            		z = tp.z-pt.z
            		
            		#next unless pt.distance(tp) <= mindist
            		next unless ( x*x + y*y + z*z ) <= minSQ
            		
            		saved << cp
            	}
            	
            	puts Time.now-t
            	
            	sel.add( saved )
            	nil
            	
            	
            
            1 Reply Last reply Reply Quote 0
            • C Offline
              CAUL
              last edited by

              @jolran said:

              That looks nice! Did you get that from the Geometric Tools library ?

              Well, no, it's a very primitive (just a plain 3D-array) standard space hash. It's surprisingly effective on average; memory intense though. I use variations of this quite often, here's another example.

              @sdmitch said:

              Here are my results with the two code options [Pascal's averaged 8.4 versus 45.9 for Caul's]

              That's very strange, I've tested on two computers and my results are more like ~0.2s (vs 4.7s for Pascal's code). I wonder where the huge time penalty comes from in your tests, maybe it's the memory allocation in init()..?

              1 Reply Last reply Reply Quote 0
              • jolranJ Offline
                jolran
                last edited by

                @unknownuser said:

                Well, no, it's a very primitive (just a plain 3D-array) standard space hash. It's surprisingly effective on average; memory intense though. I use variations of this quite often, here's another example.

                Nice. Useful to know. Also good it doesent come from a library that has draconian licence policy πŸ˜‰
                I might try it out a bit πŸ˜„

                @unknownuser said:

                That's very strange, I've tested on two computers and my results are more like ~0.2s (vs 4.7s for Pascal's code). I wonder where the huge time penalty comes from in your tests, maybe it's the memory allocation in init()..?

                If I remember correctly(?), I think he is on a laptop. So memory consumtion might slow things down in his case.
                edit: missread the topic..

                Since I did not see the aim of this algorithm. I think it's a relevant question to pose
                what are you going to do with these Points ?

                It looks to me like the result in both methods are in an unorderly fashion.

                Unless this algorithm takes care of the sorting you would have to dig through the set again.

                edit2
                Ah β˜€ , Pascal's maker of the Tree plugin. Now I can see the usage of pointcloud.

                1 Reply Last reply Reply Quote 0
                • tt_suT Offline
                  tt_su
                  last edited by

                  So - I did this for Vertex Tools. Any implementation is Ruby was slow. I then wrote a tiny Ruby C extension and the performance was 100+ times faster than the fastest Ruby implementation I had.
                  There is simply so much overhead by Ruby itself that this kind of stuff is better passed off to C - Even with the overhead of converting the point set to C structures and back to Ruby at the end it just blows away pure Ruby computation.

                  And as it's been mentioned, you want to avoid square root. Since you want to filter point by a given distance, convert the distance to the power of it self and do the distance calculation without square root. Gives your calculation an extra boost.

                  1 Reply Last reply Reply Quote 0
                  • ppoublanP Offline
                    ppoublan
                    last edited by

                    @unknownuser said:

                    Since I did not see the aim of this algorithm. I think it's a relevant question to pose
                    what are you going to do with these Points ?

                    I'm working on a new way to create grass within Tree Maker (put a lot of plants on surfaces) that I would like to look more realistic with more or less dense zones. Now it works, but looking to improve and optimze it.

                    Really thanks to all of you for your very good ideas and feedbacks.
                    Now I have to implement this.

                    Pascal

                    1 Reply Last reply Reply Quote 0
                    • jolranJ Offline
                      jolran
                      last edited by

                      @unknownuser said:

                      I'm working on a new way to create grass within Tree Maker (put a lot of plants on surfaces) that I would like to look more realistic with more or less dense zones. Now it works, but looking to improve and optimze it.

                      I started to suspect you where doing something like that. No real precise need for ordered Points
                      then.

                      As a continuation of Thomthoms advice. Should you ever want to create a C-extension easily for distance between Points the code is already written and available πŸ˜„

                      https://bitbucket.org/thomthom/sketchup-ruby-c-extension/src/e2fe0f2e43e43ebae568535b6d7a98e160b4624c/src/Example%20-%20Basics/SXBasics.c?at=default

                      1 Reply Last reply Reply Quote 0
                      • thomthomT Offline
                        thomthom
                        last edited by

                        @jolran said:

                        As a continuation of Thomthoms advice. Should you ever want to create a C-extension easily for distance between Points the code is already written and available πŸ˜„

                        https://bitbucket.org/thomthom/sketchup-ruby-c-extension/src/e2fe0f2e43e43ebae568535b6d7a98e160b4624c/src/Example%20-%20Basics/SXBasics.c?at=default

                        Note: That example is OLD! You can refer to it for how I resolve the distance calculation, but had I done that today I would have done it in C++ using Visual Studio and Xcode:
                        https://github.com/SketchUp/ruby-c-extension-examples

                        Thomas Thomassen β€” SketchUp Monkey & Coding addict
                        List of my plugins and link to the CookieWare fund

                        1 Reply Last reply Reply Quote 0
                        • 1 / 1
                        • First post
                          Last post
                        Buy SketchPlus
                        Buy SUbD
                        Buy WrapR
                        Buy eBook
                        Buy Modelur
                        Buy Vertex Tools
                        Buy SketchCuisine
                        Buy FormFonts

                        Advertisement