Python: Group intersecting spheres into unique groups?

Good day,

I have a couple of hundred N.u.r.b.s. spheres that I evaluate for intersections.
The script mathematically checks each sphere for intersections with the other spheres and appends intersecting spheres, as well as the test sphere, to a sub group list (that is later added to a groups list).

Currently:

Each sphere is now associated with its intersecting neighbours, which is great, but what I want to have is a list of lists of neighbourhoods, where each sphere and its intersecting neighbours and their intersecting neighbours and so fourth are grouped in unique sublists, meaning that each sphere can only exist once in the list of lists.

Hopefully later:

Script Start

"""Evaluates the intersections between spheres.
  Inputs:
      S: List of Nurbs spheres
  Output:
      G: Tree with intersection groups"""

from Grasshopper.Kernel.Data import GH_Path
from Grasshopper import DataTree
import rhinoscriptsyntax as rs
import math

def center_point(sph):
""" Returns the center point of a nurbs sphere. """
pt_id = rs.AddPoint(rs.SurfaceAreaCentroid(sph)[0])
return rs.coerce3dpoint(pt_id)

def list_to_tree(nested_list):
""" Returns a GH Data Tree from a two
dimensional nested Python list. """
data_tree = DataTree[object]()
for i, item_list in enumerate(nested_list):
path = GH_Path(i)
data_tree.AddRange(item_list, path)
return data_tree

def pt_on_srf(srf):
  """ Returns a point in the middle
  of a nurbs surface. """
  dom_u = rs.SurfaceDomain(srf, 0)
  dom_v = rs.SurfaceDomain(srf, 1)
  u = dom_u[1]/2.0
  v = dom_v[1]/2.0
  pt = rs.EvaluateSurface(srf, u, v)
  return pt

groups = [] # All intersection groups

for i in range(len(S)):
  grp = [] # Intersection group per sphere
  center_pt = center_point(S[i])
  srf_pt = pt_on_srf(S[i])
  radius = rs.Distance(center_pt, srf_pt)
  grp.append(S[i])

  for j in range(len(S)):
      if i != j: # Avoid self-evaluation
      center_pt_x = center_point(S[j])
      srf_pt_x = pt_on_srf(S[j])
      radius_x = rs.Distance(center_pt_x, srf_pt_x)

      dist_pts = rs.Distance(center_pt, center_pt_x)

      # Evaluate the sphere relationship
      if dist_pts > (radius + radius_x): # No intersection or inclusion
          pass
      elif dist_pts <= math.fabs(radius - radius_x): # Inclusion
          pass
      else: # Intersection
          grp.append(S[j])

groups.append(grp)

G = list_to_tree(groups)

Script End

I would be very glad, if somebody could take a look at the script and point me into the right direction.

Thank you.

Attachments:

group_intersecting_spheres.gh, 13 KB

Replies to This Discussion

Permalink Reply by Marc on June 1, 2017 at 7:49am

Thanks for your fast reply. Your solution seems very elegant.

Could it be that your solution doesn't work, if there are lots of sphere intersections for a cluster?

When I input my spheres from the example above, the lowest bottom sphere of group X is always put in a separate single branch.

Permalink Reply by Marc on June 3, 2017 at 3:13am

Thanks, for all your help! I've managed to come up with a similar solution, by looking at Peter's C# script and translating it to Python. I've attached the working file to a comment below, if your interested.

Permalink Reply by peter fotiadis on June 1, 2017 at 6:12am

Good news: as Tom said as Plan B

Bad news: not nuclear science

Ugly news: C#

Load R file for the dual demo

BTW: DO NOT attempt to do this the classic way (bool intersections on Breps): Takes a year and a half. But since there's spheres around ... why bother?

Attachments:

Clusters_intersectingSpheres_V1.3dm, 372 KB
Clusters_intersectingSpheres_V1.gh, 120 KB

Permalink Reply by peter fotiadis on June 1, 2017 at 7:56am

For big N of spheres Intersection takes ages. If on the other hand he had to cluster intersecting breps ... mama mia (even using some // approach). That said is way faster to convert Breps to Meshes.

Permalink Reply by peter fotiadis on June 1, 2017 at 8:17am

Intersection is used because that way you can cluster closed curves (other wise [radii] you'll be limited to circles). Anyway for curves there's no big difference in speed,

Permalink Reply by peter fotiadis on June 2, 2017 at 10:28am

FYI: on "average" ccx ops on Breps require 20 times more time than on Meshes.

Here's using some test/demo stuff kindly provided by the Merciless Lord.

Permalink Reply by Marc on June 3, 2017 at 3:10am

Thanks for your flawless C# example!
I've rewritten it in Python. The file is attached, if anybody is interested.
I've tested it with a little more than 400 spheres and it still works great.

Attachments: