Distance between two points / optimization

ppoublan

Dear all,

I have an array of points.
I would like to remove those that are at a distance from another point less than a minimum spacing.

The following code seems to do it, but I would like to know if you think there is a faster/more efficient way to proceed (the distance comparison of all points, not the drawing part).

Yours
Pascal


def test_distance

	pts = []
	
	max = 5000
	maxdist = 1000
	mindist = 50
	
	for i in 0..max
		pt = Geom;;Point3d.new(rand*maxdist,rand*maxdist,rand*maxdist)
		pts << [pt, true]
	end
	
	start_time = Time.now.to_f
	
	for i in 0..max
		if pts[i][1] == true
			for j in (i + 1)..max
				if pts[j][1] == true
					pt1 = pts[i][0]
					pt2 = pts[j][0]
					dist = pt1.distance pt2
					if dist < mindist
						pts[j][1] = false
					end
				end
			end
		end
	end
	
	end_time = Time.now.to_f
	
	puts (end_time - start_time).to_s
	
	Sketchup.active_model.start_operation("test",true,false,false)
	for i in 0..max
		if pts[i][1] == true
			Sketchup.active_model.entities.add_cpoint(pts[i][0])
		end
	end
	Sketchup.active_model.commit_operation

end

jolran

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..

ppoublan

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

jolran

@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.

CAUL

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`

jolran

@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.

sdmitch

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

jolran

@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

CAUL

@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()..?

jolran

@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.

tt_su

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.

ppoublan

@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

jolran

@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

404 — Bitbucket

(bitbucket.org)

thomthom

@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

404 — Bitbucket

(bitbucket.org)

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