# Get all the Neighbors until a set distance

On 24/04/2016 at 07:35, xxxxxxxx wrote:

If I want to find all the points of a polygonal object that are within a certain distance from a specific point, I believe the using the Neighbors class is the fastest way, instead of going through all the points in the list.
However, the GetPointPolys only gets me the polygons that are attached the the starting point.
I would have to spread out the search until no polygon center was found that was within the specified distance.
Does this has to be done recursively?
I had this code but it is not working ``````
def get_near(p_center,distance,polygons,centers,pli,nbr) :
# p_center = the first point coordinates
# distance = the maximum allowed distance from p_center
# polygons = the list of all polygons of the object
# centers = the list of all polygons centers coordinates
# pli = the first set of neighboring polygons around the first point
# nbr = the neighbor structure

near=[]
changed=False

while changed==False:
changed=False

for poly in pli:
p = polygons[poly]

if poly not in near:
length=(centers[poly]-p_center).GetLength()
if length<=distance:
near.append(poly)

new_pli=nbr.GetPointPolys(p.a)
for new_poly in new_pli:
if new_poly not in near:
if (centers[new_poly]-p_center).GetLength()<=distance:
near.append(new_poly)
changed=True

new_pli=nbr.GetPointPolys(p.b)
for new_poly in new_pli:
if new_poly not in near:
if (centers[new_poly]-p_center).GetLength()<=distance:
near.append(new_poly)
changed=True

new_pli=nbr.GetPointPolys(p.c)
for new_poly in new_pli:
if new_poly not in near:
if (centers[new_poly]-p_center).GetLength()<=distance:
near.append(new_poly)
changed=True

new_pli=nbr.GetPointPolys(p.d)
for new_poly in new_pli:
if new_poly not in near:
if (centers[new_poly]-p_center).GetLength()<=distance:
near.append(new_poly)
changed=True

return near
``````

On 24/04/2016 at 12:51, xxxxxxxx wrote:

I guess I found a way. I'm doing it like this:

``````
def get_near(p_center,distance,polygons,centers,pli,nbr) :
near=pli

for poly in pli:
poly_info=nbr.GetPolyInfo(poly)
new_pli=poly_info['face']

for poly2 in new_pli:
if poly2!=c4d.NOTOK:
length=(centers[poly2]-p_center).GetLength()
if length<=distance:
if poly2 not in near:
near.append(poly2)

pli=near

return near
``````

On 25/04/2016 at 03:09, xxxxxxxx wrote:

Here is an optimized version, using sets.

``````
from sets import Set

# *******************************************************************************

def get_near(p_center,distance,centers,pli,nbr) :
near=Set(pli)
pli=Set(pli)

for poly in pli:
poly_info=nbr.GetPolyInfo(poly)
new_pli=Set(poly_info['face'])-near

for poly2 in new_pli:
if poly2!=c4d.NOTOK:
if poly2 not in near:
if (centers[poly2]-p_center).GetLength()<=distance:

pli=near-pli

return near
``````

On 25/04/2016 at 10:46, xxxxxxxx wrote:

Hi Rui,

Do you happen to have a more complete example of this?
I would like to compare it to the get all points version I have. But I'm having trouble creating some of your required parameters (p_center, centers, & pli).

-ScottA

On 25/04/2016 at 11:18, xxxxxxxx wrote:

I will provide you with the code and required info to get what you need, Scott
My code starts in a vertex and returns a list of polygons that at connected to that vertex until a specific distance.

p_center is just the coordinates of the vertex (in local space) where the search will start.

centers is a list of all the center coordinates of all polygons in the object (in local coordinates) and I got those pre-calculated with the following code:

``````
points = obj.GetAllPoints()
polygons = obj.GetAllPolygons()

centers = []

for p in polygons:
centers.append((points[p.a]+points[p.b]+points[p.c]+points[p.d])*.25)
``````

I used *.25 instead of /4 because multiplications are usually faster than divisions, in python.

The pli was got from:

``````
nbr = utils.Neighbor()
nbr.Init(obj)
pli = nbr.GetPointPolys(i)
``````

Where i is the index of the starting point (the one that I got the p_center from).

So, when I call get_near , I have the coordinates of index point i in p_center , the distance is the maximum distance from p_center to consider, centers is a list with all the polygon centers, pli is a list containing the first set of faces around the point with index i and nbr is the Neighbor structure initialized for my object.

I tried to make my get_near code as fast as I could but, if someone knows how to make it faster, please tell me

On 25/04/2016 at 11:47, xxxxxxxx wrote:

Thanks.
If you're using: point = obj.GetAllPoints() in your code.
Then I'm not sure if you are gaining any speed in your code by doing all the neighbor stuff.

Here is the version I have in my notes.
But I don't know if this is slower, or faster, than yours.

``````import c4d
def main() :
obj = doc.GetActiveObject()
if not obj: return False
points = obj.GetAllPoints()
pointCount = obj.GetPointCount()
selectedPoints = obj.GetPointS()

#Only allow the script to run if one point is selected
if selectedPoints.GetCount() != 1: return False

sourcePntID = None
sourcePntPos = None
for i, v in enumerate(selectedPoints.GetAll(pointCount)) :
if not v: continue         #Skip over the non selected points
sourcePntID = i
sourcePntPos = obj.GetPoint(i)

#Select the surroung points if they are within the radius distance
for id, pos in enumerate(points) :
deltaX = abs(sourcePntPos.x - pos.x)
deltaY = abs(sourcePntPos.y - pos.y)
deltaZ = abs(sourcePntPos.z - pos.z)

#print id
selectedPoints.Select(id)

if __name__=='__main__':
main()
``````

-ScottA

On 25/04/2016 at 11:53, xxxxxxxx wrote:

Well, I was searching for faces, not points.
But I will see if I can implement the simpler version with points.
Thank you, Scott.

On 25/04/2016 at 15:06, xxxxxxxx wrote:

Just performed a test and, amazingly, with a mesh of 10201 vertexes (10000 polygons), using my method, it took 0.5 seconds and using a "go through all the list" method, it took 8.2 seconds.
Because I need to go through the entire list for each vertex. So, with a "go through all the list" I get N * N interactions.
This means that all vertexes are dealt with, as if they all had the same amount of possible relation with the starting point. In fact, statistically, they all are equal candidates.
With my method, the search starts in the point itself and it only goes through the adjacent polygons until no more candidates fulfill the requirements. As soon as no polygon center is within the maximum distance, it stops.
I managed to make it all a little faster by checking for GetLengthSquared(), instead of GetLength()

On 25/04/2016 at 15:23, xxxxxxxx wrote:

I still can't figure out how to make your custom method work. I'm getting "requires an int" error from it.
I'm using it on a sphere targeting point #141 as the starting point.

``````import c4d
from c4d import utils

def getNearestPoly(p_center, distance, polygons, centers, pli, nbr) :

near = pli

for poly in pli:

poly_info = nbr.GetPolyInfo(poly)
new_pli = poly_info['face']

for poly2 in new_pli:

if poly2 != c4d.NOTOK:
length = (centers[poly2]-p_center).GetLength()

if length <= distance:
if poly2 not in near:
near.append(poly2)

pli = near

return near

def main() :

obj = doc.GetActiveObject()
if obj is None: return

nbr = utils.Neighbor()
nbr.Init(obj)

pli = None
for i in xrange(obj.GetPolygonCount()) :
pli = nbr.GetPolyInfo(i)

points = obj.GetAllPoints()
polygons = obj.GetAllPolygons()
centers = []
for p in polygons:
centers.append((points[p.a]+points[p.b]+points[p.c]+points[p.d])*.25)

p_center = obj.GetPoint(141)
distance = 10

getNearestPoly(p_center, distance, polygons, centers, pli, nbr) #Error!!

if __name__=='__main__':
main()
``````

-ScottA

On 25/04/2016 at 16:13, xxxxxxxx wrote:

Try this, and change the distance variable.

``````
import c4d
from c4d import utils

def getNearestPoly(p_center,distance,centers,pli,nbr) :
near=set(pli)
pli=set(pli)

for poly in pli:
poly_info=nbr.GetPolyInfo(poly)
new_pli=set(poly_info['face'])-near

for poly2 in new_pli:
if poly2!=c4d.NOTOK:
if poly2 not in near:
if (centers[poly2]-p_center).GetLength()<=distance:

pli=near-pli

return near

def main() :

obj = doc.GetActiveObject()
if obj is None: return

nbr = utils.Neighbor()
nbr.Init(obj)

points = obj.GetAllPoints()
polygons = obj.GetAllPolygons()
centers = []
for p in polygons:
centers.append((points[p.a]+points[p.b]+points[p.c]+points[p.d])*.25)

p_center = obj.GetPoint(141)
pli = nbr.GetPointPolys(141)
distance = 30

near=getNearestPoly(p_center, distance, centers, pli, nbr)
print near

if __name__=='__main__':
main()
``````

On 25/04/2016 at 16:21, xxxxxxxx wrote:

Oh, the error was occurring because you had to start with pli equal to nbr.GetPointPolys(i) , not nbr.GetPolyInfo(i)

On 25/04/2016 at 16:34, xxxxxxxx wrote:

Thanks. That's got it. I knew I was doing something stupid.

-ScottA