microsoft / microsoft/automatic-graph-layout
MDS graph with Prism overlap removal => InvalidOperationException in CdtTriangle.ctor()
Nobody has claimed this yet.
- Dominant language
- C#
- Stars
- 1.5k
- Forks
- 319
- Avg merge
- 38m
- Merged PRs (30d)
- 1
Description
For certain graphs I observe the below error occurring in MDS graph Prism overlap removal process, The error occures in CdtTriangle when is called for 3 points spanning a line instead of a triangle, hence orientation is Collinear and InvalidOperation exception is thrown :

The issue is specific for Prism overlap removal. Using MinmalSpanningTree it works correctly.
Unfortunately this leads to an unrecoverable error and graph rendering stops. Could you please suggest some way how to fix this ? Or any clue why is this happening ?
See call stack below:
Microsoft.Msagl.dll!Microsoft.Msagl.Routing.ConstrainedDelaunayTriangulation.CdtTriangle.CdtTriangle(Microsoft.Msagl.Routing.CdtSite a, Microsoft.Msagl.Routing.CdtSite b, Microsoft.Msagl.Routing.CdtSite c, System.Func<Microsoft.Msagl.Routing.CdtSite, Microsoft.Msagl.Routing.CdtSite, Microsoft.Msagl.Routing.CdtEdge> createEdgeDelegate) Line 26 C#
Microsoft.Msagl.dll!Microsoft.Msagl.Routing.ConstrainedDelaunayTriangulation.CdtSweeper.CdtSweeper(System.Collections.Generic.List<Microsoft.Msagl.Routing.CdtSite> listOfSites, Microsoft.Msagl.Routing.CdtSite p_1, Microsoft.Msagl.Routing.CdtSite p_2, System.Func<Microsoft.Msagl.Routing.CdtSite, Microsoft.Msagl.Routing.CdtSite, Microsoft.Msagl.Routing.CdtEdge> createEdgeDelegate) Line 29 C#
Microsoft.Msagl.dll!Microsoft.Msagl.Routing.ConstrainedDelaunayTriangulation.Cdt.SweepAndFinalize() Line 160 C#
Microsoft.Msagl.dll!Microsoft.Msagl.Routing.ConstrainedDelaunayTriangulation.Cdt.RunInternal() Line 155 C#
Microsoft.Msagl.dll!Microsoft.Msagl.Core.AlgorithmBase.Run() Line 24 C#
Microsoft.Msagl.dll!Microsoft.Msagl.Core.Layout.ProximityOverlapRemoval.ProximityOverlapRemoval.DoSingleIteration(int currentIteration, ref bool scanlinePhase) Line 389 C#
Microsoft.Msagl.dll!Microsoft.Msagl.Core.Layout.ProximityOverlapRemoval.ProximityOverlapRemoval.RemoveOverlaps() Line 337 C#
Microsoft.Msagl.dll!Microsoft.Msagl.Core.Layout.ProximityOverlapRemoval.ProximityOverlapRemoval.RemoveOverlaps(Microsoft.Msagl.Core.Layout.GeometryGraph geometryGraph, double nodeSeparation) Line 725 C#
Microsoft.Msagl.dll!Microsoft.Msagl.Layout.MDS.MdsGraphLayout.LayoutConnectedGraphWithMds(Microsoft.Msagl.Core.Layout.GeometryGraph compGraph) Line 220 C#
Thank you !
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the CdtTriangle.ctor call in the constrained Delaunay triangulation stack, then trace how CdtSweeper and ProximityOverlapRemoval supply sites during MDS layout. Reproduce the failure with a graph containing collinear points and determine the expected behavior for that case. Done means the Prism overlap-removal path no longer stops graph rendering and has regression coverage.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- csharp
- Domain
- computer-graphics
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 28/100