Breaking all curves at intersections and storing those points

[ManiTraf]

Hello there,

I want to create a shortest path function based of polylines, lines and arcs. The actual pathfinding won't be the problem, finding the intersections doesn't look like a problem either. My problem is that I can't figure out how to split the curve2ds after an intersection and make sure the loop continues correctly.

I have a list<curve2d> which consists of either circulararc2d or linesegment2d objects. I want to run a double for loop, so everything get's checked against everything. Easy, now I can't figure out what to do when there is an intersection, and the curve2d should be split. Do I remove the current curve from the list and add the new 2 curves( obviously only if the intersection doesn't happen at the start or end). I'm pretty sure that messes up the indexing too. I have tried messing with the i and j values, but it kept missing intersections after some curve had interesected another. Am I overlooking something simple or do I need your brilliant minds?

[norman.yuan]

Have you looked into Curve2d[Curve3d, Curve].GetSplitCurves() method?

[ManiTraf]

Yes, my problem is mainly what to do with the lines it returns. Right now I replace the current line for one of the added lines and add the last one. But it's still not working out great with lines with more than 1 intersection. 

for (int i = 0; i < curve2Ds.Count - 1; i++)
            {
                var curve_i = curve2Ds[i];
                for (int j = i + 1; j < curve2Ds.Count; j++)
                {
                    var curve_j = curve2Ds[j];
                    try
                    {
                        CurveCurveIntersector2d curveCurveIntersector = new CurveCurveIntersector2d(curve_i, curve_j);

                        if (curveCurveIntersector.NumberOfIntersectionPoints > 1)
                        {
                            
                            for (int k = 0; k < curveCurveIntersector.NumberOfIntersectionPoints; k++)
                            {
                                var p = (PointModel)Storage.storage.Points.GetOrAdd(curveCurveIntersector.GetIntersectionPoint(k));
                                p.SetIdMessage("ERROR: " + k);
                                return;
                            }
                        }
                        else if (curveCurveIntersector.NumberOfIntersectionPoints > 0)
                        {
                            var point = curveCurveIntersector.GetIntersectionPoint(0);
                            PointModel node = (PointModel)Storage.storage.Points.GetOrAdd(point);

                            var intersection = curveCurveIntersector.GetIntersectionParameters(0);

                            var curve = curve_i;
                            Check if intersection is on the edge or not
                            if (!curve.StartPoint.Equals(point) && !curve.EndPoint.Equals(point))
                            {
                                var startNode = (PointModel)Storage.storage.Points.GetOrAdd(curve.StartPoint);
                                var endNode = (PointModel)Storage.storage.Points.GetOrAdd(curve.EndPoint);
                                var curves = curve.GetSplitCurves(intersection[0]).ToList();

                                curve_i = curves[0];
                                curve2Ds.Add(curves[1]);

                                startNode.ReplaceConnection(node, endNode, curves[0]);
                                endNode.ReplaceConnection(node, startNode, curves[1]);
                            }

                            curve = curve_j;

                            if (!curve_j.StartPoint.Equals(point) && !curve_j.EndPoint.Equals(point))
                            {
                                var startNode = (PointModel)Storage.storage.Points.GetOrAdd(curve.StartPoint);
                                var endNode = (PointModel)Storage.storage.Points.GetOrAdd(curve.EndPoint);
                                var curves = curve.GetSplitCurves(intersection[1]).ToList();

                                curve_j = curves[0];
                                curve2Ds.Add(curves[1]);

                                startNode.ReplaceConnection(node, endNode, curves[0]);
                                endNode.ReplaceConnection(node, startNode, curves[1]);
                            }

                        }
                        Storage.storage.Curves.Clear();
                        Storage.storage.Curves.AddRange(curve2Ds);
                    }
                    catch (Autodesk.AutoCAD.Runtime.Exception ex)
                    {
                        ed.WriteMessage("\n Error in FindIntersections Loop \n{0},\n {1}", ex.Message, ex.StackTrace);
                    }
                }

            }

[SEANT61 · Accepted solution]

It looks like you are close to what you need but, as another variation on looping:

Prepare double loop

Perhaps use BoundBlock2d.IsDisjoint as preliminary test

If not Disjointed

Record the parameter of the intersection in a Dictionary<int, DoubleCollection>.

i.e., Curve2dCollection remains unchanged

Then Loop yet again coordinating the original Curve2ds with the intersection parameters to split each Curve.

Quite possibly there will be more than one – perhaps even several –  intersections.  It may make sense to sort the DoubleCollection parameter values to help coordinate splitting the various remnants.

[ManiTraf]

Awesome, thanks for pointing me in the right direction. I will update the OP when I have cleaned it up a bit.

I had to go with Point2dCollection instead of DoubleCollection because the points kept being off after the curves had been split.

The preliminary boundblock check is a great idea too, thanks for that as well!

[ManiTraf]

Here is the full solution.

// List curve2Ds consists of LineSegment2d & CircularArc2d, NOTHING ELSE!
        public void FindIntersections(List<Curve2d> curve2Ds)
        {
            var intersections = new Dictionary<int, Point2dCollection>();

            for (int i =0; i < curve2Ds.Count -1; i++)
            {
                var curve_i = curve2Ds[i];
                if (!intersections.ContainsKey(i))
                {
                    intersections.Add(i, new Point2dCollection());
                }
                
                for (int j = i+1; j < curve2Ds.Count; j++)
                {
                    var curve_j = curve2Ds[j];
                    if (!intersections.ContainsKey(j))
                    {
                        intersections.Add(j, new Point2dCollection());
                    }

                    if (!curve_i.BoundBlock.IsDisjoint(curve_j.BoundBlock))
                    {
                        var curveCurveIntersector = new CurveCurveIntersector2d(curve_i, curve_j);
                        if (curveCurveIntersector.NumberOfIntersectionPoints > 1)
                        {
                            for (int k = 0; k < curveCurveIntersector.NumberOfIntersectionPoints; k++)
                            {
                                Func<PointModel> fun = delegate ()
                                {
                                    return new PointModel(curveCurveIntersector.GetIntersectionPoint(k), Storage.storage.Points.GetUnusedId());
                                };
                                var p = (PointModel)Storage.storage.Points.GetOrAdd(curveCurveIntersector.GetIntersectionPoint(k), fun);
                                p.SetIdMessage("ERROR: " + k);
                                return;
                            }
                        }

                        else if (curveCurveIntersector.NumberOfIntersectionPoints > 0)
                        {
                            var intersectionPoint = curveCurveIntersector.GetIntersectionPoint(0);

                            if (!curve_i.StartPoint.Equals(intersectionPoint) && !curve_i.EndPoint.Equals(intersectionPoint))
                            {
                                var param = curve_i.GetParameterOf(intersectionPoint);
                                if (!intersections[i].Contains(intersectionPoint))
                                {
                                    intersections[i].Add(intersectionPoint);
                                }
                            }

                            if (!curve_j.StartPoint.Equals(intersectionPoint) && !curve_j.EndPoint.Equals(intersectionPoint))
                            {
                                var param = curve_j.GetParameterOf(intersectionPoint);
                                if (!intersections[j].Contains(intersectionPoint))
                                {
                                    intersections[j].Add(intersectionPoint);
                                }
                            }
                        }
                    }
                }
            }
            // Split all curves at intersections and add them to a new list

            var curves = new List<Curve2d>();

            PointModel startPointModel = null;
            PointModel endPointModel = null;

            for (int i = 0; i < curve2Ds.Count; i++)
            {
                var curve = curve2Ds[i];
                var intersects = intersections[i].ToArray();
                var sortedIntersects = intersects.OrderBy(p => curve.GetParameterOf(p));

                Point2d point = new Point2d();
                Func<PointModel> func = delegate ()
                {
                    return new PointModel(point, Storage.storage.Points.GetUnusedId());
                };

                ed.WriteMessage("\n Intersections for {0} are {1}", i, intersections[i].Count);
                foreach (var p in sortedIntersects)
                {
                    var param = curve.GetParameterOf(p);
                    var splitCurves = curve.GetSplitCurves(param);
                    ed.WriteMessage("\n Double d = {0}, splitcount = {1}", param, splitCurves.Length); ;
                    curves.Add(splitCurves[0]);

                    point = splitCurves[0].StartPoint;
                    startPointModel = (PointModel)Storage.storage.Points.GetOrAdd(point, func);

                    point = splitCurves[0].EndPoint;
                    endPointModel = (PointModel)Storage.storage.Points.GetOrAdd(point, func);

                    startPointModel.AddConnection(endPointModel, splitCurves[0]);
                    endPointModel.AddConnection(startPointModel, splitCurves[0]);

                    curve = splitCurves[1];


                };
                // Add the last part of the line, or if no intersections found the whole line.
                point = curve.StartPoint;
                startPointModel = (PointModel)Storage.storage.Points.GetOrAdd(point, func);

                point = curve.EndPoint;
                endPointModel = (PointModel)Storage.storage.Points.GetOrAdd(point, func);

                startPointModel.AddConnection(endPointModel, curve);
                endPointModel.AddConnection(startPointModel, curve);
                curves.Add(curve);
            }

            ed.WriteMessage("\n From {0} curves to {1}", curve2Ds.Count,curves.Count);

            
            
        }

[SEANT61]

Kudos.  I can appreciate the effort to make an inherently complex procedure possible.  Nicely done.  

[Izhar_Azati]

Hello @ManiTraf 

In the code, is "Storage" is "Azure Storage"?

What is the minimum implementation of "PointModel" so that the function can be compiled?

In my case I want to take a collection of curves, break them at all intersection points, use REGION creation from all the curves and then create all the polygons.
(Something similar to MAPCLEAN and creating a polygonal topology)

[ManiTraf]

Hi there,

It's been a while and I've changed things since, but Storage was just a class where I would share lists ands dicts in.

The collectionmodels are dictionaries with <T, id> and some helper functions for that.

I think the pointmodel only has 

public Point3d Position 

I would advise you to use the steps in the code to convert the list of curves into a list of all broken curves, your application for this seems different than mine was and I think you don't need as much code as I did