Parallel Foreach Data Structure

Hi all,

I’m testing a Parallel Foreach C# node to test for curve containment. Basically extracting the discontinuity of each polyline curve and test if at least one point lies within the boundary curve. This works well while the data set is small, but becomes quite slow when a large number of curves are tested.

As I try to write a parallel process, it seems to work, but the order of these discontinuities get messed up so the resulting curves (organized as one curve per branch) are not connected properly. I could obviously cull the initial input with the test output without reconstructing the curves with points, but would still love to know how I would’ve done this for future/other data sets.

I understand that somehow it is related to how parallel processes need to be thread-safe, but am unsure how to fix this…I read through the post below but I believe the difference is that my data structure is a tree with branches containing multiple values themselves:

Attaching the file and below are screenshots of when the parallel boolean is set to False, and then True, and the gh setup with the code in the C# node. Any help is much appreciated!

containment_par_v3_test.gh (71.9 KB)



1 Like

What I’ve found is, rather than using curve.Contains, turn your closed curve into a mesh then use Mesh Ray at each point in the planes Z direction. You will get hit or miss bool values. It is a lot faster. https://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_Intersect_Intersection_MeshRay.htm

2 Likes

You just need one line:

test = pt.AsParallel().AsOrdered().Select(ptr => (int) (bnd.Contains(ptr, Plane.WorldXY, t)));

The reason is because ConcurrentDictionary doesn’t preserve the order of key-values, just as Dictionary vs SortedDictionary.

And here’s the code that PancakeAlgo, a misc plugin I wrote, uses to determine point inside polygon. It’s faster than MeshRay for single polygon shape. The code is licensed under Apache 2.0 License.

public static PointContainment Contains(Point2d[] polygon, Point2d ptr) {
 var crossing = 0;
 var len = polygon.Length;

 for (var i = 0; i < len; i++) {
  var j = i + 1;
  if (j == len) j = 0;

  var p1 = polygon[i];
  var p2 = polygon[j];

  var y1 = p1.Y;
  var y2 = p2.Y;

  var x1 = p1.X;
  var x2 = p2.X;

  if (Math.Abs(x1 - x2) < RhinoMath.ZeroTolerance && Math.Abs(y1 - y2) < RhinoMath.ZeroTolerance)
   continue;

  var minY = Math.Min(y1, y2);
  var maxY = Math.Max(y1, y2);

  if (ptr.Y < minY || ptr.Y > maxY)
   continue;

  if (Math.Abs(minY - maxY) < Tolerance) {
   var minX = Math.Min(x1, x2);
   var maxX = Math.Max(x1, x2);

   if (ptr.X >= minX && ptr.X <= maxX) {
    return PointContainment.Coincident;
   } else {
    if (ptr.X < minX)
     ++crossing;
   }
  } else {
   var x = (x2 - x1) * (ptr.Y - y1) / (y2 - y1) + x1;
   if (Math.Abs(x - ptr.X) <= Tolerance)
    return PointContainment.Coincident;

   if (ptr.X < x) {
    ++crossing;
   }
  }
 }

 return ((crossing & 1) == 0) ? PointContainment.Outside : PointContainment.Inside;
}
1 Like