Get room centerline(s) and intersections (For corridors/passage type rooms)

[amrut.modani.wwi]

How do I get the centerlines of a single room shown below?
I know one way is to divide the room manually into rectangular rooms with additional room separation lines, that way I can just use bounding boxes and get individual center lines.
But how Do I approach this for a single room with multiple turns/crossing/intersection??
Thanks in advance 🙂

[amrut.modani.wwi]

How do I get the centerlines of a single room shown below?
I know one way is to divide the room manually into rectangular rooms with additional room separation lines, that way I can just use bounding boxes and get individual center lines.
But how Do I approach this for a single room with multiple turns/crossing/intersection??
Thanks in advance 🙂

[jeremy_tammik]

This sounds like an interesting computational algebra task. I would suggest doing some purely geometrical research completely disconnected from Revit and BIM, to start with. Initially, I thought that an alpha shape might be useful for you, but just looking at the picture, the minimal spanning tree looks more like your goal:

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

Please let us know how it goes for you. I'll be happy to continue discussing this a bit more...

[jeremy_tammik]

This sounds like an interesting computational algebra task. I would suggest doing some purely geometrical research completely disconnected from Revit and BIM, to start with. Initially, I thought that an alpha shape might be useful for you, but just looking at the picture, the minimal spanning tree looks more like your goal:

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

Please let us know how it goes for you. I'll be happy to continue discussing this a bit more...

[amrut.modani.wwi]

Thanks for the Alpha Shape suggestion. That is what I am ultimately looking for. It's also called Concave hull in some forums.
I went through the steps where one has to vary the 'Alpha' to get the desired outcome which is basically the radius of the circle getting used in the algorithm. (Link for reference: https://stackoverflow.com/questions/16625063/alpha-shape-concave-hull-algorithm-in-c-sharp).
I definitely want to implement this for my case.

Meanwhile, me being lazy, I figured out an easy way to solve my particular problem.

I used part of your code from for convex hull. (https://thebuildingcoder.typepad.com/blog/2016/08/online-revit-api-docs-and-convex-hull.html#3) to get the vertices of the room (this is necessary as there are multiple boundary segments when there is an overlapping room separation line/ a door in the wall, etc).
Instead of calculating convex hull, I just iterated over those vertices, and got the pair of points which are 'nearby' (As the corridor width is fairly standard, I could just define the 'nearby' tolerance). Then I just calculate the center of the pairs, and can basically get centerlines.

I understand this is just a temporary and lazy solution that only works for my case. I intend to implement Alpha shape (concave hull) algorithm over the weekend. I'll reply here once I implement it.

[amrut.modani.wwi]

Thanks for the Alpha Shape suggestion. That is what I am ultimately looking for. It's also called Concave hull in some forums.
I went through the steps where one has to vary the 'Alpha' to get the desired outcome which is basically the radius of the circle getting used in the algorithm. (Link for reference: https://stackoverflow.com/questions/16625063/alpha-shape-concave-hull-algorithm-in-c-sharp).
I definitely want to implement this for my case.

Meanwhile, me being lazy, I figured out an easy way to solve my particular problem.

I used part of your code from for convex hull. (https://thebuildingcoder.typepad.com/blog/2016/08/online-revit-api-docs-and-convex-hull.html#3) to get the vertices of the room (this is necessary as there are multiple boundary segments when there is an overlapping room separation line/ a door in the wall, etc).
Instead of calculating convex hull, I just iterated over those vertices, and got the pair of points which are 'nearby' (As the corridor width is fairly standard, I could just define the 'nearby' tolerance). Then I just calculate the center of the pairs, and can basically get centerlines.

I understand this is just a temporary and lazy solution that only works for my case. I intend to implement Alpha shape (concave hull) algorithm over the weekend. I'll reply here once I implement it.

[jeremy_tammik · Accepted solution]

The simpler the better. Kiss! I love your pragmatic point-pair approach. Thank you very much for sharing that, and looking forward to the alpha shape results. Happy, fruitful weekend and successful coding!

[jeremy_tammik · Accepted solution]

The simpler the better. Kiss! I love your pragmatic point-pair approach. Thank you very much for sharing that, and looking forward to the alpha shape results. Happy, fruitful weekend and successful coding!

[mhannonQ65N2 · Accepted solution]

I think a straight skeleton, or some other topological skeleton, would work much better than an alpha shape for your situation.

[mhannonQ65N2 · Accepted solution]

I think a straight skeleton, or some other topological skeleton, would work much better than an alpha shape for your situation.

[amrut.modani.wwi]

So I was implementing Alpha shape for this polygon; and halfway through, I realized that it is already an Alpha shape. 😶
I read more about Straight skeleton. It led me to Medial Axis. Which is basically the centerlines that we are talking about. There are few algorithms to calculate Medial Axis, (One way: https://stackoverflow.com/questions/1069523/find-medial-axis-of-a-polygon-using-c-sharp). But this seems quite time consuming and for now I am adhering to Kiss! 🙂
Thanks @jeremy_tammik  and @mhannonQ65N2 for your inputs. 

[amrut.modani.wwi]

So I was implementing Alpha shape for this polygon; and halfway through, I realized that it is already an Alpha shape. 😶
I read more about Straight skeleton. It led me to Medial Axis. Which is basically the centerlines that we are talking about. There are few algorithms to calculate Medial Axis, (One way: https://stackoverflow.com/questions/1069523/find-medial-axis-of-a-polygon-using-c-sharp). But this seems quite time consuming and for now I am adhering to Kiss! 🙂
Thanks @jeremy_tammik  and @mhannonQ65N2 for your inputs. 

[jeremy_tammik]

Well, congratulations on successfully solving and completing the task, and thank you for your appreciation.

Would you like to share a few relevant code snippets of your approach, in case others encounter the same need?

It sounds pretty generic to me, and it might make a nicer blog post as well.

Thank you!

[jeremy_tammik]

Well, congratulations on successfully solving and completing the task, and thank you for your appreciation.

Would you like to share a few relevant code snippets of your approach, in case others encounter the same need?

It sounds pretty generic to me, and it might make a nicer blog post as well.

Thank you!

[amrut.modani.wwi]

Sure.
Here the Method which returns the List of pairs of vertices which are 'nearby'.
Note: This only works when the corridor width is around 1500mm (which is design standard in my firm). For larger width, we can vary the 'tolerance' variable. Also, the length of a single branch/ junction is not less than 2550mm. Otherwise it'll return additional pairs. Which is more or less fine as the center points of those pairs will also lie on the Medial Axis (corridor centerline)

        public List<List<XYZ>> ReturnVertexPairs (Room corridorRoom)
        {
            SpatialElementBoundaryOptions opt = new SpatialElementBoundaryOptions
            {
                SpatialElementBoundaryLocation =
              SpatialElementBoundaryLocation.Finish
            };

            IList<IList<BoundarySegment>> loops = corridorRoom.GetBoundarySegments(opt);

            List<XYZ> roomVertices = new List<XYZ>(); //List of all room vertices
            foreach (IList<BoundarySegment> loop in loops)
            {
                //TaskDialog.Show("Revit", "Total Segments = " + loop.Count().ToString());

                XYZ p0 = null; //previous segment start point
                XYZ p = null; // segment start point
                XYZ q = null; // segment end point

                foreach (BoundarySegment seg in loop)
                {
                    q = seg.GetCurve().GetEndPoint(1);

                    if (p == null)
                    {
                        roomVertices.Add(seg.GetCurve().GetEndPoint(0));
                        p = seg.GetCurve().GetEndPoint(0);
                        p0 = p;
                        continue;
                    }
                    p = seg.GetCurve().GetEndPoint(0);
                    if (p != null && p0 != null)
                    {
                        if (AreCollinear(p0, p, q))//skipping the segments that are collinear
                        {
                            p0 = p;
                            continue;
                        }
                        else
                        {
                            roomVertices.Add(p);
                        }
                    }
                    p0 = p;
                }
            }

            double tolerance = 2550; //Distance between two Points (in mm) should be less than this number
            List<List<XYZ>> nearbyPairs = new List<List<XYZ>>(); //List of Pairs of nearby points
            for (int i = 0; i < roomVertices.Count() - 1; i++)
            {
                for (int j = i + 1; j < roomVertices.Count(); j++)
                {
                    double dist = roomVertices[i].DistanceTo(roomVertices[j]) * 304.8;
                    if (dist < tolerance) //checking whether two points are nearby based on tolerance
                    {
                        nearbyPairs.Add(new List<XYZ> { roomVertices[i], roomVertices[j] });
                    }
                }
            }
            //TaskDialog.Show("Revit", "Total points = " + roomVertices.Count().ToString()
            //    + Environment.NewLine + "Total Pairs = " + nearbyPairs.Count());
            return nearbyPairs;
        }

 
Helper method to check whether points are collinear (to skip the boundary segments which are colinear)

        static bool AreCollinear (XYZ p1, XYZ p2, XYZ p3)
        {
            bool collinear = false;
            double area = 0.5*Math.Abs(p1.X * (p2.Y - p3.Y)
                + p2.X * (p3.Y - p1.Y)
                + p3.X * (p1.Y - p2.Y));
            //sometimes area is not exactly zero but is very small number
            if (area < 0.1)
            {
                collinear = true;
            }
            return collinear;
        }

[amrut.modani.wwi]

Sure.
Here the Method which returns the List of pairs of vertices which are 'nearby'.
Note: This only works when the corridor width is around 1500mm (which is design standard in my firm). For larger width, we can vary the 'tolerance' variable. Also, the length of a single branch/ junction is not less than 2550mm. Otherwise it'll return additional pairs. Which is more or less fine as the center points of those pairs will also lie on the Medial Axis (corridor centerline)

        public List<List<XYZ>> ReturnVertexPairs (Room corridorRoom)
        {
            SpatialElementBoundaryOptions opt = new SpatialElementBoundaryOptions
            {
                SpatialElementBoundaryLocation =
              SpatialElementBoundaryLocation.Finish
            };

            IList<IList<BoundarySegment>> loops = corridorRoom.GetBoundarySegments(opt);

            List<XYZ> roomVertices = new List<XYZ>(); //List of all room vertices
            foreach (IList<BoundarySegment> loop in loops)
            {
                //TaskDialog.Show("Revit", "Total Segments = " + loop.Count().ToString());

                XYZ p0 = null; //previous segment start point
                XYZ p = null; // segment start point
                XYZ q = null; // segment end point

                foreach (BoundarySegment seg in loop)
                {
                    q = seg.GetCurve().GetEndPoint(1);

                    if (p == null)
                    {
                        roomVertices.Add(seg.GetCurve().GetEndPoint(0));
                        p = seg.GetCurve().GetEndPoint(0);
                        p0 = p;
                        continue;
                    }
                    p = seg.GetCurve().GetEndPoint(0);
                    if (p != null && p0 != null)
                    {
                        if (AreCollinear(p0, p, q))//skipping the segments that are collinear
                        {
                            p0 = p;
                            continue;
                        }
                        else
                        {
                            roomVertices.Add(p);
                        }
                    }
                    p0 = p;
                }
            }

            double tolerance = 2550; //Distance between two Points (in mm) should be less than this number
            List<List<XYZ>> nearbyPairs = new List<List<XYZ>>(); //List of Pairs of nearby points
            for (int i = 0; i < roomVertices.Count() - 1; i++)
            {
                for (int j = i + 1; j < roomVertices.Count(); j++)
                {
                    double dist = roomVertices[i].DistanceTo(roomVertices[j]) * 304.8;
                    if (dist < tolerance) //checking whether two points are nearby based on tolerance
                    {
                        nearbyPairs.Add(new List<XYZ> { roomVertices[i], roomVertices[j] });
                    }
                }
            }
            //TaskDialog.Show("Revit", "Total points = " + roomVertices.Count().ToString()
            //    + Environment.NewLine + "Total Pairs = " + nearbyPairs.Count());
            return nearbyPairs;
        }

 
Helper method to check whether points are collinear (to skip the boundary segments which are colinear)

        static bool AreCollinear (XYZ p1, XYZ p2, XYZ p3)
        {
            bool collinear = false;
            double area = 0.5*Math.Abs(p1.X * (p2.Y - p3.Y)
                + p2.X * (p3.Y - p1.Y)
                + p3.X * (p1.Y - p2.Y));
            //sometimes area is not exactly zero but is very small number
            if (area < 0.1)
            {
                collinear = true;
            }
            return collinear;
        }

[jeremy_tammik]

Brilliant! Thank you for raising this interesting issue and sharing your nice efficient simple solution. I added it to The Building Coder to preserve for posterity:

https://thebuildingcoder.typepad.com/blog/2022/06/corridor-skeleton-copy-and-paste-api.html#3

[jeremy_tammik]

Brilliant! Thank you for raising this interesting issue and sharing your nice efficient simple solution. I added it to The Building Coder to preserve for posterity:

https://thebuildingcoder.typepad.com/blog/2022/06/corridor-skeleton-copy-and-paste-api.html#3