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. Thumbs Up
    I knew I was doing something stupid.

    -ScottA


Log in to reply