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.
    • jolranJ Offline
      jolran
      last edited by

      The distance method use Square root. So it's bound to be slow.

      You could do testing with "distance squared" method, although it won't give you the accurate distance.
      But maybe for sorting out some Points for a more detailed test.

      You could compute the 1 comparing distance from distance = (dist*dist) and compare with that perhaps.

      Distance Square uses 3 multiplications and 3 subtract. So I don't know if the Ruby version will be faster than the API "distance" method, though. ❓
      In a C-extension it is for sure.

      Point a and b

      x = a.x-b.x; y = a.y-b.y; z = a.z-b.z # Don't remember if one has to use .abs (?)
      dist_sq = xx + yy + z*z

      Distance = Math.sqrt( dist_sq )

      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.

      I can imagine some clever person have convoluted API way for comparing distances between points. This code will work in a C-extension though..

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