Random point distribution problem


#1

Hi,
Trying to make a randomized spread of a chosen number of points, distributed within a set square or cubic range. The problem is ensuring that no two points are closer than a chosen distance.

I thought, as each new point is added, it could be checked against all other existing points.

The distance is evaluated and used to keep or delete the “just-added” point.

Debugging says: “Local variable ‘dbldist’ referenced before assignment.”

I can’t see where the problem is.

Is there something in the for loop that I’m just not getting?


#2

i’m not familiar with that editor but… is there something weird going on with the indentation here?


also… it looks like it might fail in that line anyway… rs.Distance wants a point3d and i think you’re feeding it a guid?

line 25 is rs.AddPoint which returns a guid… that’s appended to the list then you’re using it to assign chkpta? if so, you could do something like:

newpt = rs.coerce3dpoint([x, y, z])
rs.AddPoint(newpt)
pointlist.append(newpt)

maybe.


but then rs.DeleteObject(chkpta) will probably fail :confused:


#3

I guess in this case, I would add the point coordinates to the list without adding the points to the document at the same time. At each point added, you can do your min distance check. If it passes, add the python point3d object (coordinates) to the list - but don’t add the Rhino point object to the document using AddPoint().

Once your list of good points is as long as you want, THEN add all the points at once to the document using rs.AddPoints(list).

It’s going to get pretty slow if you have large numbers of points, you have to do at least n! number of distance checks (where n is the number of points), plus as many more as needed when you find a “bad” point.

I’m wondering if you start out with a regular grid of n points that are spaced sufficiently, then move each point randomly but that the limits of the random movement are such that two points can never be moved closer than the asked-for distance…

–Mitch


#4

Thanks Jeff,

I will try that and see how far I get.
I did not see coerce3dpoint() in the programmer’s reference… will look around.

That is the editor I get from EditPythonScript. But most of the point creation lines (before the distance check - culling part) was imported from a previous script written elsewhere.

jw


#5

Hi Mitch,

If I understand you correctly, I think you are right about generating a list of point values (not points) for the locations. Then using math to make sure that the distance values are not smaller than the limit. And finally, assigning points to an “approved” list of x,y,z values all in one shot. Seems like that should be less computation and less time. I’m guessing that’s probably going to involve some extension of Pythagorean triangulation between each location… still quite a lot of math! I suppose that it’s possible to check only the closest values and avoid having to check each x,y and z value against every other? Would that really save any time?

I actually did also think of that grid, or maybe point cloud grid, as a starting strategy last night. What would be next though, shifting points with randomized vectors? It would generate a more even dispersion. That would be a very different strategy.

Ultimately, I am looking toward getting Delaunay or Voronoi triangulations from these points and pipe them, maybe with t-splines. In the past I have used point distributions for this but the diameter of the pipes causes overlaps when vertices are too close. This gives me internal surfaces that not only look funny, but cause problems in the print. So I need a way to either cull or avoid points that are too close.

Thank you very much I will look into both ways!

Also, since my questions and script experience is far more rudimentary than most here. Is there is a better forum for me to engage?

jw


#6

this is the best place to post.
not too long ago, i was asking way more basic questions than you are.
(as in, mitch suggested ‘learn python’ and i was like ‘ok, how?’ :slight_smile: )


#7

As Jeff said, this is the place. Everyone from beginner to master hangs out here and questions are always welcome.

Since the distance is measured in 3D space, it will be difficult to set up a short-circuit logic to throw out points immediately based on X, Y or Z. However instead of using rs.Distance() you could use a purely mathematacal pythagorean formula function which might be faster for large numbers of points, or at least use test_point.DistanceTo(check_point). DistanceTo() is a built in method of a Rhino-Python point3d object.

–Mitch


#8

maybe something of concern…
it might get stuck in the while loop depending on the parameters entered…

if asked to make too many points or too great a distance, it will probably hit a place where no more points can be added without being closer than your minimum… so it will just go round&round without stopping.


#9

That’s certainly possible… Probably need a counter and if the loop goes over a certain predetermined number of iterations, break out of it and announce failure… --Mitch


#10

Hello wojo-

I’ve looked at the same problem and found using Rhino.Geometry.PointCloud.ClosestPoint function to be an easy solution. They do most of the math and looping for you. Just make a new point cloud, generate the random point, use that function to find the closest point in the cloud, calculate that distance, if it is ok then add the point to the cloud. If not throw it away and try again.


#11

yeah, that seems good… a first draft at it:

import rhinoscriptsyntax as rs
import random

grid = 100  # size of cube
points = 100
short = 5  # shortest allowable distance between two points

cloud = []
count = 1

while len(cloud) < points:

    x = random.uniform(0, grid)
    y = random.uniform(0, grid)
    z = random.uniform(0, grid)

    if len(cloud) == 0:
        first = rs.coerce3dpoint([x, y, z])
        cloud.append(first)
        rs.AddPoint(first)
        continue

    test = rs.coerce3dpoint([x, y, z])
    closest = rs.PointArrayClosestPoint(cloud, test)
    distance = rs.Distance(test, cloud[closest])

    count += 1
    if distance < short:
        continue
    else:
        cloud.append(test)
        rs.AddPoint(test)

msg = "{} points were discarded"
print msg.format(count - points)

note-- probably don’t try that exact code with short set to something over 20 …to make the array of 100 points with 20 as the distance, it will potentially discard ~10,000 points… anything higher and you might get stuck in the loop. (no breaks are in place)


[EDIT]… i should take my own advice… tried it with 25 and now looping with no end in sight :cry:


#12

Ha yes, it can be tricky. I did a min/max constraint which is even more picky. Wound up with three possible terminators: Max points, max consecutive failed attempts, and escape key test.


#13

Hi All… and thank you all.

Eureka … well sort of.
I used Mitch’s suggestion to create the x,y,z values only, do all the math first using a pythagorean distance checker. Then add the good points… works fast.

My remaining problem is, sometimes the script fails. I believe it fails when there is no more room for another point…maybe?

In any case, if anyone has some error checking advice I would certainly welcome that,

code here…
\
python

import rhinoscriptsyntax as rs
import _random as rnd
import math

def RandPtsCloseChck():
	npoints = rs.GetInteger("How many points? ", 200, 5, 1000)
	l = rs.GetReal(" In Units, what is the square or cubic range? (500 is the limit) ", 40, 1, 500)
	lmt = rs.GetReal("In units, what is the closest any 2 points can be?", 2.0, 0.1, 10.0)
	r = (rnd.Random())	
	count = 0
	pvlist = []

	while count < npoints: 
		RandPointVals(l, pvlist, r, lmt)
		count = len(pvlist)
	MakePointsFromList(pvlist)		

def RandPointVals(u, list, r, lmt):		
	pvx = u*r.random() 
	pvy = u*r.random() 
	pvz = u*r.random()		
	listval = [pvx,pvy,pvz] #create a list of values	
	list.append(listval) #nested list
	if len(list) >= 2: CheckLastWithAll(list, lmt) #send to the checker

def CheckLastWithAll(list, lmt): # compares the last to all previous			
	junklist = []
	chkvala = list[len(list)-1]
	for i in range (len(list)-2):
		chkvalb = list[i]
		dist = PythValChk( chkvala, chkvalb) 
		if dist < lmt: 
			junk = list.pop()
			junklist.append(junk) # trashcan
			
def PythValChk( new, chk ): #pythagorean distance checker
	xdif = (new[0] - chk[0])
	ydif = (new[1] - chk[1])
	zdif = (new[2] - chk[2])			
	xydist = math.sqrt((xdif**2) + (ydif**2))
	dist =  math.sqrt((xydist**2) + (zdif**2))	
	return dist		

def MakePointsFromList(list):  # point maker		 	
	for j in range(len(list)):
			x = list[j][0]
			y = list[j][1]
			z = list[j][2]
			rs.AddPoint((x,y,z))

if __name__=="__main__":
    RandPtsCloseChck()

\\


#14

Spoke too soon…
… still doesn’t work.


#15

it gives me an ‘index out of range’ error if i enter a value higher than 3 for closest point.

…which i believe the problem is in line30

chkvalb = list[i]

whatever number i is at the time doesn’t coincide with the list length… i might be 5 but the list only has 3 objects in it (for example)


#16

Hi Jeff,

Yes, I agree. Have been puzzling over what to do about it.
Thinking I should do some logic diagram or something…?

Possibly instead of using the original “listval” list to keep the good point values, sort the values to two separate lists a “junk list” and “good list” … seems redundant. Will work on it some today.


#17

I think you only need one list which contains points that have been found to be valid… then use the list to check test points against.

tracking the junk points is unnecessary and adds confusion.

if your values fail the distance test, you can stop right there and do nothing more with the bad numbers. using continue will stop the loop and return to the start of the loop for another go at it with a new set of random numbers…(and break will stop the loop and exit from it)