Nearest Connected Neighbors

[Macha]

Does anybody know of an algorithm to find the connected neighbours of a point?

[symek]

Does anybody know of an algorithm to find the connected neighbours of a point?

In vex? Sure :

http://www.sidefx.com/docs/houdini10.0/vex/functions/getneighbours

[Macha]

I was more thinking of Python. I'm trying to learn the stuff (so it's not terribly important). That Vex code depends on getneighbor, right? So it won't be straightforward to translate I guess.

[symek]

I was more thinking of Python. I'm trying to learn the stuff (so it's not terribly important). That Vex code depends on getneighbor, right? So it won't be straightforward to translate I guess.

Ach so! Above code approximates a single function getneighbours(), which does exactly that. There are a bunch of similar stuff in hscript, like pointneighbours() expression, so hou.hscriptExpression() might help. In case you really want to go wild, there are some python modules* for working with graphs, which may help you do stuff like finding shortest edge between two points, finding point's neighours and so on.

skk.

* - http://igraph.sourceforge.net/

- http://networkx.lanl.gov/

- etc.

[Macha]

Einfach genial! I came up with some rubbish search procedure that couldn't take connectivity into consideration. I'll look at those tasty modules then!

[edward]

The simplest approach goes something like this:

- maintain a dictionary of (point, neighbour list) pairs

- for each primitive, go through all vertices

- from each vertex, you can obtain its point number

- for each vertex i in the primitive, you can determine the neighbour via vertex (i-1) and (i+1)

- (make sure to handle wrap around conditions and if the polygon is open)

- now just look up vertex i's point number in the dictionary and add the neighbouring points to its neighbour list

- (take care to avoid duplicates)

Now you have a dictionary data structure that quickly finds the point neighbours.

[Macha]

OK, a question about vertices. Are vertices numbered locally with respect to the primitive, or globally (each has a unique number, like $PT)

Because if I use this I get sequences of repeating numbers.

geo = hou.pwd().geometry()

prim = geo.prims()

for each in prim:

vert = each.vertices()

for v in vert:

print v.number()

[graham]

They are numbered locally. A way you can see this is to look in the Geometry Spreadsheet/Details View and display Vertices. All the vertices appear as #:#, where the first number is the primitive number, and the second is the vertex number.

[Macha]

- from each vertex, you can obtain its point number

- for each vertex i in the primitive, you can determine the neighbour via vertex (i-1) and (i+1)

I'm a bit stuck here. I can find the point from the vertex if I do like so:

for each in prim:

vert = each.vertices()

for v in vert:

v.point().number()

But since v is not a number but belongs to hou.vertex class I can't simply access its neighbor by doing something like v-1, or v[-1], etc.

Is there a trick to this?

[graham]

You'll have to access them by index.

for prim in prims:
        verts = prim.vertices()
        num_verts = prim.numVertices()

        for i in range(num_verts):
            current_vert = verts[i]
            next_vert = verts[(i+1) % num_verts]
            prev_vert = verts[(i-1) % num_verts]

Edited January 7, 2010 by graham

[Macha]

Something is wrong... Maybe I misunderstand the algorithm

If I have a single square then point and vertice numbers are identical (right?).

But the connections for V1 are V0 and V3, not V0 and V2.

I get the correct neighbors, except for the 2nd point in every primitive...

This is what I got so far.

# This code is called when instances of this SOP cook.
geo = hou.pwd().geometry()
print "----------------------------------------------------------"
# Add code to modify the contents of geo.
prim = geo.prims()
points = geo.points()
pdict = {} # point-neighborlist pairs

for each in prim:
    vert = each.vertices()
    num_vert = each.numVertices()
    max_vi = max(range(num_vert))

    print "\nPrimitive "+str(each.number()) + " has " +str(max_vi+1)+" Vertices:"+ str(range(num_vert))
    print""

    for vi in range(num_vert):
        current_vert = vert[vi]

        if (vi+1)<= max_vi: # check existence of next vertex
            next_vert = vert[(vi+1)]
        else:
            next_vert = vert[0]

        if (vi-1) > 0: #check existence of previous vertex
            prev_vert = vert[(vi-1)]
        else:
            prev_vert = vert[(max_vi)]

        current_point = current_vert.point().number()
        next_point = next_vert.point().number()
        prev_point = prev_vert.point().number()
        pdict[current_point] = next_point, prev_point

        print "   V"+str(prev_vert.number())+"--V"+str(current_vert.number())+"--V"+str(next_vert.number()),
        print "   P"+str(prev_point)+"--P"+str(current_point)+"--P"+str(next_point)

print "\n   " + str(pdict)

[Macha]

Hoho! I found the mistake! (vertex number != point number for one primitive)

I can now find all neighbors. Wohohoo! Now just need to find a way to put them properly into the dictionary!

Edited January 7, 2010 by Macha

[Macha]

Yippi-oh, tatara! It seems to work! Thank you everybody.

I feel so clever now, thanks to your superbrains!

It's like Christmas all over again. The door to a new Houdini-world has opened.

Here is an example:

Point: [Neighbors]

0: [1, 3]

1: [2, 4, 0]

2: [4, 1]

3: [4, 5, 0]

4: [7, 6, 1, 2, 3]

5: [3, 6]

6: [4, 7, 5]

7: [6, 4]

[Macha]

Now the yellow numbers show the neighbors of the blue ones.

[Symbolic]

Hi Macha,

Could you please post your latest Python script.

Thanks.

[sibarrick]

Hoho! I found the mistake! (vertex number != point number for one primitive)

I can now find all neighbors. Wohohoo! Now just need to find a way to put them properly into the dictionary!

They would be if you first add a sort sop and sort by vertex number, but by default there is no requirement for the 2 to match.

[hyperforce]

Its also possible to do it with a vop-sop inside a foreach node.

It took me a while to figure it out but since I know nothing about python or how to work with VEX script, this is my solution.

step 1 - setting up the base:

Create a for-each node set to "Each Number" mode with an 0 & npoints("../previous node")-1 expression in the first two number range fields.

Turn off merge results to set the for-each node into a feedback loop.

Feed your geometry into the foreach sop.

step 2 - inside the foreach node:

Create a group node with point pattern: `stamp("../","FORVALUE",0)` to isolate the current point to check.

After this create a vopsop node and feed the groups output into its first input.

step 3 - inside the vop sop:

Create a for-loop node and a neighbourcount node.

Connect Global1's Point number to the neighbourcount nodes input slot as well as to the "Next Input" slot of the for_loop node.

Connect the neighbourcount1's output to the for_loop's "End Value" input slot.

step 4 - inside the for_loop vop

Create a add_point_to_group node and a neighbour node. (not neighbourcount like before)

Connect the subinput1's "initial value" output to the Neighbour node's "neighbour number" input.

Connect the subinput1's "point number" output to the Neighbour node's "point number" input.

Connect the Neighbour node's output to the add_point_to_group's "point number" input.

Inside the add_point_to_group node, promote the Group string input value to become a parameter.

Step 5 - back to the for_each node layer

select the vopsop and in its new Group_Name attribute, add: PG_`stamp("../","FORVALUE",0)`

The result:

For each point number you will now get a group called PG_# (with # the points number)

Each group will hold this points neighbouring point numbers.

Edited April 11, 2012 by hyperforce

[glassman3d]

Hoho! I found the mistake! (vertex number != point number for one primitive)

I can now find all neighbors. Wohohoo! Now just need to find a way to put them properly into the dictionary!

if I may throw my two cents in here

I have found it always much quicker to iterate points and prims in the geometry object using the

iterpoints and iterprims functions. they create a generator rather than storing a list into memory

cheers