RC: Detecting Concave Corners of Planar Polygon?

Rhino Developer
,
1

Dear friends,

I am struggling with detecting nonconvex/concave corners for planar polygons. Is there an easy way in RhinoCommon to achieve this? (I need this for detecting proper vectors from which i can determine facenormals for nonconvex planar faces of my own halfedge data structure)

best regards from austria,

heinz

2

Hi Heinz,

If polygons are planar, you can generate circles at each corner of your polygon. Split those circles with the polygon. Identify which parts of the splitted circles are inside of the polygon.
Measure the length of those inside splitted circles. Polygon concave corners will have the length of the inside splitted circles larger than pi*circleRadius.

This method will also work for non planar polygons (of course of certain tolerance) but the polygon would have to projected to a plane first.

3

@chuck, any suggestions here?

4

Take the cross product of the edge directions. For 3 consecutive points, P0, P1, P2,

(P1-P0) X (P2-P1) dot (Plane Normal) is positive for left turns, negative for right, 0 for no turn or 180 deg turn.

5

Thanks @djordje @dale @chuck !!

@chuck : i do understand the cross product part, but - where do i get the plane normal from? if i had a plane normal, i wouldn’t need the entire operation in the first place… :slight_smile:

6

Hi Heinz,

The plane comes from the planar curve. For example:

/// <summary>
/// Finds the concave corner points in a closed, planar polyline curve.
/// </summary>
/// <param name="curve">The polyline curve.</param>
/// <param name="tolerance">The tolerance required to determine if the curve is planar.
/// When in doubt, use the document's model absolute tolerance.</param>
/// <returns>The concave points if successful.</returns>
private static Point3d[] FindConcaveCornerPoints(Curve curve, double tolerance)
{
  var rc = new Point3d[0];

  // Make sure we have a curve and it's closed.
  if (null == curve || !curve.IsClosed)
    return rc;

  // Make sure the curve is planar, within our tolerance.
  Plane plane;
  if (!curve.TryGetPlane(out plane, tolerance))
    return rc;

  // Make sure the curve is a polyline.
  Polyline polyline;
  if (!curve.TryGetPolyline(out polyline) || null == polyline)
    return rc;

  // For closed polylines, the first and last points are identical.
  // So we can remove the last one.
  polyline.RemoveAt(polyline.Count - 1);

  // Find the concave corner points...
  var points = new List<Point3d>();
  for (var current = 0; current < polyline.Count; current++)
  {
    var prev = current == 0 ? polyline.Count - 1 : current - 1;
    var next = current == polyline.Count - 1 ? 0 : current + 1;

    var dir0 = polyline[current] - polyline[prev];
    dir0.Unitize();

    var dir1 = polyline[next] - polyline[current];
    dir1.Unitize();

    var dir2 = Vector3d.CrossProduct(dir0, dir1);
    dir2.Unitize();

    var dot = dir2 * plane.Normal; // dot product
    if (dot < 0.0)
      points.Add(polyline[current]);
  }

  return points.ToArray();
}

Does this help?

– Dale

1 Like
7

thanks a lot, @dale! this helps indeed. i didn’t realize that TryGetPlane() from an oriented planar polygon gives me a directed plane. since my polygons are properly oriented, this is enough for creating my facenormals.

all the best, heinz