topic Re: Breaking all curves at intersections and storing those points in .NET Forum

Breaking all curves at intersections and storing those points

ManiTraf — Sun, 11 Oct 2020 11:52:58 GMT

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?

Re: Breaking all curves at intersections and storing those points

norman.yuan — Sun, 11 Oct 2020 13:24:59 GMT

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

Re: Breaking all curves at intersections and storing those points

ManiTraf — Sun, 11 Oct 2020 13:35:23 GMT

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); } } }

Re: Breaking all curves at intersections and storing those points

SEANT61 — Sun, 11 Oct 2020 15:21:05 GMT

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.

Re: Breaking all curves at intersections and storing those points

ManiTraf — Sun, 11 Oct 2020 20:57:53 GMT

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!

Re: Breaking all curves at intersections and storing those points

ManiTraf — Mon, 12 Oct 2020 08:21:28 GMT

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); }

Re: Breaking all curves at intersections and storing those points

SEANT61 — Tue, 13 Oct 2020 07:14:32 GMT

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

Re: Breaking all curves at intersections and storing those points

Izhar_Azati — Sat, 17 Jun 2023 20:07:22 GMT

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)

Re: Breaking all curves at intersections and storing those points

ManiTraf — Mon, 19 Jun 2023 05:33:27 GMT

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