microsoft / microsoft/automatic-graph-layout

MDS graph with Prism overlap removal => InvalidOperationException in CdtTriangle.ctor()

Open
#236 0 comments 0 reactions 0 assignees View on GitHub

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 :

image

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.