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

      @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