Large search space


#1

From selected vertices of a mesh, I need to extract their adjacent faces.

Search space: 1,713,900 faces to 799 vertices, getting to a crazy app.1.37e9.

  1. Does Member Index use binary search tree?
  2. Any suggestions?

Thanks!


#2

Just getting adjacentcy queries takes long?
(GetConnectedFaces and then if you need them sorted without duplicates adding them to HashSet)

Upload the file to undestand what kind of issue you have and the size of the mesh.


#3

neighbouringMeshFaceTest.gh (12.2 KB)

Thanks!


(qythium) #4

If you don’t mind a bit of Python scripting, here’s an easy way to test for inclusion in a set without going through datatree acrobatics and the overhead of deconstructing and constructing meshes:
Python sets are hashed (i.e. testing element in set(x) runs in constant time) so this should only scale linearly with number of faces in your mesh.

hashset = set(indices)
inside = []
for face in faces:
    inside.append(any([(vertex in hashset) for vertex in face]))


neighbouringMeshFaceTest.gh (11.7 KB)

I’m not sure how the native Grasshopper components scale but passing hundreds of thousands of inputs through them probably causes significant overhead due to the background type conversions.


(qythium) #5

Update: here’s an alternative, slightly more readable implementation:

hashset = set(indices)
in_faces = []
for face in faces:
    for vertex in face:
        if vertex in hashset:
            in_faces.append(face)
            break

It’s also faster due to the short-circuiting evaluation which breaks out of the inner loop as soon as a single vertex satisfies the condition – this might make a small difference depending on the size of your intersecting mesh.
neighbouringMeshFaceTest_v2.gh (14.6 KB)


#6

Wow, awesome!
Thanks!