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   
    added=True   
  
    while added==True:   
          
        added=False   
  
        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)   
                            added=True   
  
        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)   
    added=True   
  
    while added:   
          
        added=False   
  
        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:   
                            near.add(poly2)   
                            added=True   
  
        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)  
  
  radius = 50   #The radius surrounding the source point's position  
    
  #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)   
            
      if deltaX <= radius and deltaY <= radius and deltaZ <= radius:  
          #print id  
          selectedPoints.Select(id)  
            
  c4d.EventAdd()  
  
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  
  added = True  
  
  while added==True:  
  
      added = False  
  
      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)  
                          added = True  
  
      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!!  
        
  c4d.EventAdd()  
  
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)   
    added=True   
  
    while added:   
          
        added=False   
  
        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:   
                            near.add(poly2)   
                            added=True   
  
        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   
          
    c4d.EventAdd()   
  
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