In-Place Offset Scaling of Polyline Polygons

@[toc]

Effect to be generated

The basic principle of hanging pits or sumps is to generate a circle of walls along the outside of the slab boundary for blocking.


Two methods for in-situ scaling of polyline polygons

One is the method in Zhou Peide’s Computational Geometry - Algorithm Design and Analysis (Third Edition), and the other is the method cited from Calculation Method of Polyline Parallel Lines. Finally, the second method solved the project problem, but since I wrote both algorithms, I analyzed both. This situation may be encountered in the future, so it is convenient to check back.

6.10 Polygon Enlargement, Reduction and Movement P309

The textbook records a method: make vectors from a point inside the closed polygon to each point, and offset based on the vector value to the outside by a specified distance. Values needed to be calculated:

1. Vector v between polygon internal point and boundary point
2. The offset value is the perpendicular distance between two parallel line segments, so the actual length needs to be calculated when encountering oblique line segments.

c# implementation

/// <summary>
/// Offset specified path value
/// </summary>
/// <param name="array">Floor outline collection</param>
/// <param name="insidePoint">Internal point, passed in after processing face origin</param>
/// <param name="k">Scaling factor</param>
/// <returns></returns>
public static CurveLoop OffsetPath(CurveLoop array,XYZ insidePoint,double k)
{
    //get all vertexes 
    var curves = new List<Curve>();
    var iEnumerator = array.GetEnumerator();
    while (iEnumerator.MoveNext())
    {
        //Take out all line segments
        var curve = iEnumerator.Current;
        curves.Add(curve);
    }

    
    if (curves.Count == 0) throw new ArgumentNullException();
    var points = new List<XYZ>();
    //Traverse each line segment, take point 1 of the line segment as the offset point, find the vertical vector of the line segment vector and find the angle cos theta
    //Find the specific offset distance kt, thereby finding the extension point, and add it to the collection points
    foreach (var curve in curves)
    {
        if (curve is Line line)
        {
            var vec = line.Direction.Normalize();
            var targetVec = GetVerticalVector(vec);
            //Take point 1 of the line segment as the reference point
            var referencePoint = line.GetEndPoint(1);
            var dir = new XYZ(insidePoint.X - referencePoint.X, insidePoint.Y - referencePoint.Y, 0)
                .Normalize();
            //
            var angle = dir.AngleTo(targetVec);
            if (angle > Math.PI / 2)
            {
                var count = Math.Floor(angle / (Math.PI / 2)); 
                angle -= Math.PI / 2 * count;
            }
            //Angles inside polygons are all acute. Because they form an acute triangle with the vertical vector of the vector, the maximum angle is 90°
            //Actual offset value, calculating the position of this point on the extension line based on the known vector
            var tk = k / Math.Cos(angle);
            
            //Find the extension line on the known vector. Only discussing extension to the outside here. Z is consistent, it is a two-dimensional vector
            //Input: origin o , boundary point vp , extension distance tk
            //Output: extension point tp
            // tp.x = o.x + abs(vp.x - o.x) / L(vp , o) * (tk + L(vp,o))
            // tp.y = o.y + abs(vp.y - o.y) / L(vp , o) * (tk + L(vp,o))
            //Vertical triangle three sides a, b, c, c is the longest. Each extension line can be regarded as a triangle. By comparing the ratio of c, the lengths of a and b specific be obtained, and the corresponding length is added from the origin.
            
            //L(vp,o)
            //Specific x, y offset values specific be calculated, but the generated complex hanging pit surface will have an overall offset. The reason is that rays are made to the outside, and 
            //offsetting from referencePoint will cause incorrect generation
            //from referencePoint

            var lVpO = Line.CreateBound(referencePoint, insidePoint).Length;
            var x = Math.Abs(referencePoint.X - insidePoint.X) / lVpO * (tk + lVpO);
            var y = Math.Abs(referencePoint.Y - insidePoint.Y) / lVpO * (tk + lVpO);
            var subtractionVec = (referencePoint - insidePoint).Normalize();//Take unit vector for judgment below
            if (subtractionVec.X <= 0)
            {
                if (subtractionVec.Y >= 0)
                {
                    var targetPoint = new XYZ((insidePoint.X - x).ReduceDouble(4), (insidePoint.Y + y).ReduceDouble(4), referencePoint.Z);
                    points.Add(targetPoint);
                }
                else
                {
                    var targetPoint = new XYZ((insidePoint.X - x).ReduceDouble(4), (insidePoint.Y - y).ReduceDouble(4), referencePoint.Z);
                    points.Add(targetPoint);
                }
            }
            else
            {
                if (subtractionVec.Y >= 0)
                {
                    var targetPoint = new XYZ((insidePoint.X + x).ReduceDouble(4), (insidePoint.Y + y).ReduceDouble(4), referencePoint.Z);
                    points.Add(targetPoint);
                }
                else
                {
                    var targetPoint = new XYZ((insidePoint.X + x).ReduceDouble(4), (insidePoint.Y - y).ReduceDouble(4), referencePoint.Z);
                    points.Add(targetPoint);
                }
            }

            
        }
        
    }

Disadvantages

This method is not suitable for complex slab boundaries, but it can be used for convex hull sets. It is relatively simple to understand, but needs to add quadrant addition and subtraction. Those who are interested can verify the book details according to the catalog.

Analysis

The first picture shows that most of it is inaccurate. The reason is that offsetting from the center point to the boundary direction will result in incorrect details. The lower boundary here needs to be offset to both sides separately, but a collective offset of convex corners occurs. So in actual projects, there will be cases where project hanging pit generation is incorrect.


Vector Scaling Method

In fact, the first method also uses vectors for modification, but to distinguish it, I casually called it a name. Original link, added my own explanation and c# code here.


Algorithm Analysis

1. Two groups of offset line segments can form a rhombus.
2. We can use trigonometric functions to calculate the length of one side.
3. According to the ratio of unit vector to length, the length of center PiQi can be calculated.

• Input: Actual offset distance, boundary point collection
• Output: Offset point collection

Algorithm Steps

1. Calculate unit vectors normal v1, normal v2 based on point collection
2. Organize formula 1: |a X b| = |a|*|b|*sin(θ)
3. A calculation formula for the angle can be obtained, but since ∠θ is collinear with another angle, according to the theorem, it can be deduced that sin(Π - θ) = sin(θ)
4. According to 3 and h distance, the length of the rhombus side in the v2 direction can be calculated through trigonometric functions. Lb is the length of the rhombus side, L represents h, that is: L/Lb = sin(Π - θ) and sin(Π - θ) = sin(θ)
5. Organize formulas 2 and 3 to obtain the final formula: Lb = L/|a X b|/|a|/|b|
6. Also because they are unit vectors, the modules of |a|, |b| are 1
7. Finally, through vector addition formula: Qi = Pi + L/|a x b| x (v1 + v2)
8. The direction of the vector represents reduction and enlargement. Mainly, the step L/sin(θ) in the original text may be confusing, so I explain it here.

c# Code

public static CurveLoop OffsetPath(CurveLoop array, double k)
{
                        
    /*
     * Second method: Source: https://blog.csdn.net/happy__888/article/details/315762
     * This method is suitable for in-situ reduction and enlargement of polyline polygons formed by parallel straight lines combined
     * Through the points before scaling and points after scaling and the vector (a, b) formed by two points, a rhombus shape with four equal sides can be formed
     * Parallelogram area: |a X b| = |a|*|b|*sin(θ) ,
     * With known offset length and perpendicular distance L of two parallel line segments, a right triangle can be obtained by making a perpendicular line on the rhombus side
     * Through triangle theorem, L/Lb = sin(Π - θ) and sin(Π - θ) = sin(θ)
     * So the final formula can be obtained: Lb = L/|a X b|/|a|/|b|
     * Also the final point is the starting point (Ps) + vector direction (a + b) * vector length (Lb) [Because the vector calculation simplified the vector to unit vector before, so the distance from the starting point to the midpoint should be the value of the rhombus side before unitization
     * Unitization previous value namely normal(Lb) / Lb = normal(LTargetPoint) / LTargetPoint]
     * So the final point can be calculated through the above formula
     * 
     */

    var vertices = new List<XYZ>();
    var newVertices = new List<XYZ>();
    //Because vertices in Revit are sorted counterclockwise, just take out the points
    foreach (var curve in array)
    {
        vertices.Add(curve.GetEndPoint(0));
    }
    //Traverse each point to get the previous point and the next point, get two vectors, the **vector direction at this position is related to the scaling form**
    for (int i = 0; i < vertices.Count; i++)
    {
        int iPrevious = -1;
        int iEnd = -1;
        if (i == 0)
        {
            iPrevious = vertices.Count - 1;
            iEnd = i + 1;
        }
        else if (i == vertices.Count - 1)
        {
            iPrevious = i - 1;
            iEnd = 0;
        }
        else
        {
            iPrevious = i - 1;
            iEnd = i + 1;
        }
        
        
        XYZ pPrevious = vertices[iPrevious];
        XYZ point = vertices[i];
        XYZ pEnd = vertices[iEnd];
        
        //normalize
        var v1 = (pPrevious - point).Normalize();
        var v2 = (pEnd - point).Normalize();
        var cross = (v1.X*v2.Y - v1.Y*v2.X);//Cross product, v1, v2 unit vector module is 1
        var lb = 0.00;
        if (cross == 0)
            continue;
        lb = k / cross;
        var tPoint = point + lb * (v1 + v2);
        newVertices.Add(tPoint);

    }

    
    //output 
    var loop = new CurveLoop();
    for (int i = 0; i < newVertices.Count; i++)
    {
        if(i == newVertices.Count - 1)
        {
            var c = Line.CreateBound(newVertices[i], newVertices[0]);
            loop.Append(c);
        }
        else
        {
            var c = Line.CreateBound(newVertices[i], newVertices[i + 1]);
            loop.Append(c);
        }
    }
    
    return loop;
}

Compared with the problem I encountered, this method has less code and better accuracy. The road to learning is bumpy and needs constant learning!

Revit API Method

If doing Revit development, if complex boundaries are not involved, you can use the CurveLoop.CreateViaOffset method inside, but this method will have errors, and expansion will become reduction in complex boundaries, as shown below


Generation using Method 2:


Generation by Method 1: