How to determine if a point(XYZ) is inside a curveloop (IList<XYZ>)?

[Anonymous]

internal bool IsInside(XYZ point, IList<XYZ> panel )
{
    // true if point is inside the loop else false
}

[Anonymous]

Afaik there is no function in revit to determn a point within a closed loop. You have to code it yourself with mathemathics. The only objects to have this function are rooms.

[jeremytammik · Accepted solution]

Just as Remy says, the mathematics is not hard.

It helps to use a clever algorithm, and such an algorithm is known.

Here is my example implementation from 1996, ported to C# and the Revit API in 2010:

http://thebuildingcoder.typepad.com/blog/2010/12/point-in-polygon-containment-algorithm.html

Please let us know how it works for you and exactly how you end up making use of it.

A little reproducible sample would be nice to see, to test it in real life:

http://thebuildingcoder.typepad.com/blog/about-the-author.html#1b

Thank you!

Cheers,

Jeremy

[Anonymous]

It worked. Thank you!

I had to write condition to detect points on the panel edges. 

internal bool IsPointInsidePanel(IList<Curve> polygon, XYZ point)
{
           bool result = false;

           foreach (Curve c in polygon)
           {
                 Line edge = c as Line;
                 if (null != edge)
                 {
                       if (edge.Contains(point))
                       {
                            result = true;
                            break;
                        }
               }
           }

           if (!result)
           {
               IList<UV> uvPolyPoints = new List<UV>();
               foreach (Curve c in polygon)
               {

                            UV uv = ProjectPointOnExteriorFace(c.GetEndPoint(0));
                            uvPolyPoints.Add(uv);
               }

              UV uvPoint = ProjectPointOnExteriorFace(point);

              result = PolygonContains(uvPolyPoints, uvPoint);
          }

         return result;

}

public static class LineExtension
{
    public static bool Contains(this Line line, XYZ point)
    {
         XYZ a = line.GetEndPoint(0); // Line start point
         XYZ b = line.GetEndPoint(1); // Line end point
         XYZ p = point;       
        return (Math.Abs(a.DistanceTo(b) - (a.DistanceTo(p) + p.DistanceTo(b))) < WevrConstants.EPSILON);
   }

}

[jeremytammik]

Dear Raji,

Congratulations on putting it together, and thank you for the confirmation!

You Line.Contains extension function is interesting. I have never seen that solution before. I like it. It does not directly compare the distance of the point P to the line. Instead, it compares the length of the line with the sum of the two segments line start point to P plus P to line end point. That defines an ellipse and has to do with Kepler and planetary movements  🙂

https://en.wikipedia.org/wiki/Ellipse

Cheers,

Jeremy

[jeremytammik]

Dear Raji,

I took a closer look at your Line.Contains method.

There is no need for the Math.Abs, since the sum of the two distances to the point is always larger than the line length.

You should probably also consider the distance in relation to the length of the line.

I implemented a suggestion and added it to The Building Coder samples:

https://github.com/jeremytammik/the_building_coder_samples/blob/master/BuildingCoder/BuildingCoder/U...

  public static class JtLineExtensionMethods
  {
    /// <summary>
    /// Return true if the given point is very close 
    /// to this line, within a very narrow ellipse
    /// whose focal points are the line start and end.
    /// The tolerance is defined as (1 - e) using the 
    /// eccentricity e. e = 0 means we have a circle; 
    /// The closer e is to 1, the more elongated the 
    /// shape of the ellipse.
    /// </summary>
    public static bool Contains( 
      this Line line, 
      XYZ p,
      double tolerance = Util._eps )
    {
      XYZ a = line.GetEndPoint( 0 ); // line start point
      XYZ b = line.GetEndPoint( 1 ); // line end point
      double f = a.DistanceTo( b ); // distance between focal points
      double da = a.DistanceTo( p );
      double db = p.DistanceTo( b );
      // da + db is always greater or equal f
      return ((da + db) - f) / f < tolerance;
    }
  }

Can you take a look and see whether that satisfies your needs as well, and maybe better?

Thank you!

Cheers,

Jeremy

[Anonymous]

Yes it does! Thank you!

[FAIR59]

@jeremytammik

I tested your formula and the Original to see where the switch point from true to false lies.

As you suspected the distance from the switchpoint to the line  is dependant on the length of the line, however your formula makes things worse.

My suggestion for the formula :  return ((da + db) - f) * f < tolerance;

Here are my results: (tolerance = 0.0001)

Line length  1
   Original switch point  (0.007100000, 0.500000000, 0.000000000)
   Jeremy switch point  (0.007100000, 0.500000000, 0.000000000)
  FAIR switch point  (0.007100000, 0.500000000, 0.000000000)

Line length  5
   Original switch point  (0.015850000, 2.500000000, 0.000000000)
   Jeremy switch point  (0.035400000, 2.500000000, 0.000000000)
  FAIR switch point  (0.007100000, 2.500000000, 0.000000000)

Line length  10
   Original switch point  (0.022400000, 5.000000000, 0.000000000)
   Jeremy switch point  (0.070750000, 5.000000000, 0.000000000)
  FAIR switch point  (0.007100000, 5.000000000, 0.000000000)

Line length  50
   Original switch point  (0.050050000, 25.000000000, 0.000000000)
   Jeremy switch point  (0.353600000, 25.000000000, 0.000000000)
  FAIR switch point  (0.007100000, 25.000000000, 0.000000000)

Line length  100
   Original switch point  (0.070750000, 50.000000000, 0.000000000)
   Jeremy switch point  (0.707150000, 50.000000000, 0.000000000)
  FAIR switch point  (0.007100000, 50.000000000, 0.000000000)

[jeremytammik]

Dear Fair59,

Thank you ever so much for performing this test and correcting the formula.

I had a strong suspicion that it would not work just like that out of my head, and I am very glad to have that confirmed.

Never trust anyone over 30, said the hippies.

I ceased to trust myself long ago  🙂

I do trust your correction, though.

I updated The Building Coder samples accordingly:

https://github.com/jeremytammik/the_building_coder_samples/compare/2017.0.132.5...2017.0.132.6

Thank you!

Cheers,

Jeremy

[Anonymous]

How to do if curveloop contains a Arc?

[jeremytammik · Accepted solution]

The easiest would be to approximate the arc arc by a tessellation and use the point in polygon containment algorithm on that:

http://thebuildingcoder.typepad.com/blog/2010/12/point-in-polygon-containment-algorithm.html

Cheers,

Jeremy

[Anonymous]

May I ask: What is the definition of "If a point is inside a curveloop" here?

In 2D, a point can be determined if it is in a polygon.

But in 3D, a point may not be coplanar with the curveloop, the curveloop even may not be coplanar itself.

So what do we want to achieve here? The following are my guesses:

1. If a point is in a curveloop when viewing from a given viewport.

2. Determine the pivot of the curveloop first, such that the cureloop can rotate around the pivot. The point is inside if the curveloop can "contain/include" the point when rotating.

[K.Calero_Arup]

@Anonymous in your solution you have this method:

UV uv = ProjectPointOnExteriorFace(c.GetEndPoint(0));

can you share that method please? I don't see it anywhere else or in API docs.

Thank you

[shern3]

Here is an extremely simple solution that works for me. Make sure the list of points "Polygon" contains sorted points (so it is retrieved from a closed curveloop for example), and that the list does not have duplicate points:

public static bool IsPointInsidePolygon(XYZ point, List<XYZ> polygon)
            {
                int intersections = 0;
                int count = polygon.Count;

                for (int i = 0; i < count; i++)
                {
                    XYZ p1 = polygon[i];
                    XYZ p2 = polygon[(i + 1) % count]; // Ensures the last point connects to the first

                    // Check if the point is exactly on a vertex
                    if (point.Equals(p1) || point.Equals(p2))
                    {
                        return true; // On a vertex counts as inside
                    }

                    // Check if the point is on an edge
                    if ((point.Y > Math.Min(p1.Y, p2.Y)) && (point.Y <= Math.Max(p1.Y, p2.Y)) && 
                        (point.X <= Math.Max(p1.X, p2.X)) && (p1.Y != p2.Y)) 
                    {
                        double xinters = (point.Y - p1.Y) * (p2.X - p1.X) / (p2.Y - p1.Y) + p1.X;
                        if (p1.X == p2.X || point.X <= xinters)
                        {
                            intersections++;
                        }
                    }
                }

                // Odd number of intersections means the point is inside
                return (intersections % 2 != 0);
            }