Plugin Cafe Homepage
Forum Home Forum Home > Plugin Cafe > PYTHON Development
  New Posts New Posts
  FAQ FAQ  Forum Search   Register Register  Login Login

Get all the Neighbors until a set distance

 Post Reply Post Reply
Author
Message
Rui Batista View Drop Down
Member
Member


Joined: 2002 Nov 30
Location: Portugal
Online Status: Offline
Posts: 1247
Post Options Post Options   Quote Rui Batista Quote  Post ReplyReply Direct Link To This Post Topic: Get all the Neighbors until a set distance
    Posted: 2016 Apr 24 at 7:35am
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
Back to Top
Rui Batista View Drop Down
Member
Member


Joined: 2002 Nov 30
Location: Portugal
Online Status: Offline
Posts: 1247
Post Options Post Options   Quote Rui Batista Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 24 at 12:51pm
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
Back to Top
Rui Batista View Drop Down
Member
Member


Joined: 2002 Nov 30
Location: Portugal
Online Status: Offline
Posts: 1247
Post Options Post Options   Quote Rui Batista Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 3:09am
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
Back to Top
ScottA View Drop Down
Member
Member


Joined: 2011 Jan 07
Online Status: Offline
Posts: 2288
Post Options Post Options   Quote ScottA Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 10:46am
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
Back to Top
Rui Batista View Drop Down
Member
Member


Joined: 2002 Nov 30
Location: Portugal
Online Status: Offline
Posts: 1247
Post Options Post Options   Quote Rui Batista Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 11:18am
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
Back to Top
ScottA View Drop Down
Member
Member


Joined: 2011 Jan 07
Online Status: Offline
Posts: 2288
Post Options Post Options   Quote ScottA Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 11:47am
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


Edited by ScottA - 2016 Apr 25 at 11:47am
Back to Top
Rui Batista View Drop Down
Member
Member


Joined: 2002 Nov 30
Location: Portugal
Online Status: Offline
Posts: 1247
Post Options Post Options   Quote Rui Batista Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 11:53am
Well, I was searching for faces, not points.
But I will see if I can implement the simpler version with points.
Thank you, Scott.
Back to Top
Rui Batista View Drop Down
Member
Member


Joined: 2002 Nov 30
Location: Portugal
Online Status: Offline
Posts: 1247
Post Options Post Options   Quote Rui Batista Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 3:06pm
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()
Back to Top
ScottA View Drop Down
Member
Member


Joined: 2011 Jan 07
Online Status: Offline
Posts: 2288
Post Options Post Options   Quote ScottA Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 3:23pm
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
Back to Top
Rui Batista View Drop Down
Member
Member


Joined: 2002 Nov 30
Location: Portugal
Online Status: Offline
Posts: 1247
Post Options Post Options   Quote Rui Batista Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 4:13pm
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()
Back to Top
Rui Batista View Drop Down
Member
Member


Joined: 2002 Nov 30
Location: Portugal
Online Status: Offline
Posts: 1247
Post Options Post Options   Quote Rui Batista Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 4:21pm
Oh, the error was occurring because you had to start with pli equal to nbr.GetPointPolys(i), not nbr.GetPolyInfo(i)

Edited by Rui Batista - 2016 Apr 25 at 4:22pm
Back to Top
ScottA View Drop Down
Member
Member


Joined: 2011 Jan 07
Online Status: Offline
Posts: 2288
Post Options Post Options   Quote ScottA Quote  Post ReplyReply Direct Link To This Post Posted: 2016 Apr 25 at 4:34pm
Thanks. That's got it. Thumbs Up
I knew I was doing something stupid.

-ScottA
Back to Top
 Post Reply Post Reply

Forum Jump Forum Permissions View Drop Down

Bulletin Board Software by Web Wiz Forums® version 9.61 [Free Express Edition]
Copyright ©2001-2009 Web Wiz

This page was generated in 0.125 seconds.