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.
    • ppoublanP Offline
      ppoublan
      last edited by

      Thanks for your answer,
      I will make more tests with this method.

      Regarding this point

      @unknownuser said:

      Regarding you code I'm not sure what you want to do with marking the Points with a boolean.
      It might be faster to append results to a new Array rather then store a lot of small arrays . And maybe even use a Hash.

      The idea was NOT to compare all points, but as some are discarded, to be sure they are not compared in the loop with all others, to reduce the total number of comparisons.
      If I copy "valid" points in another array, I will have to compare all points, even those already found as "too close".

      Thanks again
      Pascal

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

        @unknownuser said:

        The idea was NOT to compare all points, but as some are discarded, to be sure they are not compared in the loop with all others, to reduce the total number of comparisons.
        If I copy "valid" points in another array, I will have to compare all points, even those already found as "too close".

        Ah I see. As long as you have a plan for it πŸ˜„

        I was thinking if one could reverse engieneer the distance to only do added subtraction tests.
        Probably NOT since 1 large dimension value can negate the others (?). But it wont hurt trying to see if you could find an algorithm for that.

        1 Reply Last reply Reply Quote 0
        • 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