Polyline boundary simplification

Hi,
I am looking for a reliable method of simplifying a closed polyline boundary. The inputs I have are building sections with small protrusions (facade elements, etc). The desired output is pretty intuitive if you’re doing it manually, but I haven’t found a nice way to automate this process. The desired output is not always convex.

I can’t rely on reduce polyline because it runs into problems when the protrusions are on the corners of the desired output shape. I have tried loose offsetting but it doesn’t always work. My latest idea is to explode the curve and identify the longest segments through some sort of clustering function, then extend those curves and curveboolean.
I’ve also mucked around with some stuff in galapagos: routines that run reduce polyline and then jitter the control points until the angles of the result are as close as possible to the angles of the input polyline segments. But this hasn’t been successful.

Could anyone point me toward resources for this problem? It seems like there must be some research on this somewhere.
boundary-simplification.3dm (87.8 KB)

You might have luck with (maybe iteratively) deleting short segments, but that does not take angles (local shape) into account and might “distort” the macro shape. A more advanced algorithm might be to identify N consecutive short segments with substantial angular difference, and then deleting these from the polyline.

Thanks, that sounds like it’s worth a shot. I’m imagining that if you wanted to set the “short” threshold properly you could pick a consecutive bunch of line segments (say, 20 at a time) and decide what counts as “short” or “long” based on that set… Will have to try this out.

Here’s a quick implementation:

190118_DeleteShortSegments_00.gh (5.1 KB)

As you can see there are issues with vertices getting removed where a short segment meets a long one (the corner). I think I’d simply keep track of all vertices belonging to long segments, and then re-insert these (or snap the nearest point to) into the polyline afterwards, if they have been deleted.

3 Likes

This is close but leaves some corners chamfered. It uses the Polyline Offset component from Clipper

https://www.food4rhino.com/app/clipper-grasshopper-and-rhino

simplify polyline.gh (8.0 KB)

Hi all.


CurveBoolean.gh (24.1 KB)

This definition 90% rotates around “CurveBoolean” (rhino command)…
I had to call it from c#… probably it’s not a great implementation… but it works…
Here it is:

  private void RunScript(List<Curve> x, Point3d y, ref object A)
  {
    this.RhinoDocument.Objects.UnselectAll();
    for(int i = 0;i < x.Count;i++){
      this.RhinoDocument.Objects.Add(x[i]);
      Rhino.DocObjects.RhinoObject obj = this.RhinoDocument.Objects.MostRecentObject();
      obj.Select(true);
    }
    string str = "_CurveBoolean d a " + y.ToString() + " _Enter ";
    Rhino.RhinoApp.RunScript(str, false);
    A = GH_Convert.ToGeometryBase(this.RhinoDocument.Objects.GetSelectedObjects(false, false).ElementAt(0).Geometry);
    Rhino.RhinoApp.RunScript("Delete ", false);
    this.RhinoDocument.Objects.UnselectAll();
  }

The sequence is:

  • deleting small segments, under length value “x”
  • extending ALL remaining segments by the double of “x” , on both extremities
  • doing CurveBoolean with an approximate center (so it could still completely fail in some situation)
  • using discontinuity point to create a new polyline (it will remove curved segments)

Edit: I hadn’t even read first post (just looked at the pictures… lol ) … @S_L , you did already mention what I’ve done here… well… had the same idea XD

Here’s a solution requiring no scripting or booleaning or 3rd party plugins - just vanilla grasshopper :slight_smile:

simplify-boundary.gh (13.2 KB)

6 Likes

Thanks for the variety of answers!
I came up with one myself in python, may be a little convoluted. Logic is similar to some of the posts here: delete short segments to get a polyline as described by Anders. Then wherever there are “stems” or “fillets” (identified by segment length), replace the points on either end of the stem/fillet with the intersection of the lines before and after the stem or fillet.

I tried identifying the length threshold for stems or fillets automatically by partitioning the lengths of the polyline segments. It works for this case but it’s a little volatile and I think it would fall apart in some other test cases…
simplify_boundary_3.gh (11.8 KB)