[VB.net] Langste lijn uit lijst met coordinaten bepalen

[skate master]

Ik heb een AutoCAD plugin wat van een in de tekening aanwezig leidingnetwerk de begin en eindpunten van de leidingen uitleest en dit omzet naar een lijn object.
De plugin leest de leidingen uit de database in de volgorde zoals deze zijn aangemaakt.
Zolang de leidingen netjes van punt A naar B zijn getekend is het geen probleem om een gesloten lijn te maken van de diverse leidingen. Echter komt het wel eens voor dat er een stuk leiding gewijzigd moet worden waardoor deze opnieuw aan de database wordt toegevoegd. Doordat dan bij het uitlezen de coordinaten niet doorlopen worden het meerdere afzonderlijke lijnstukken.

Uitdaging
De uitdaging is nu, hoe bepaal ik de langste aan een gesloten lijn uit een serie coordinaten.

voorbeeld
Hieronder een schematische weergave van het rioolsysteem, met de coordinaten van de leidingen.

De leidingen uit het voorbeeld worden op dit moment ingelezen als 5 losse lijnen.
Lijn 1: (1, 2, 3)
Lijn 2: (4)
Lijn 3: (5)
Lijn 4: (6)
Lijn 5: (7, 8 )

Het zou wenselijk zijn om het systeem als 3 lijnen in te lezen.
Lijn 1: (6, 5 , 1, 2, 3)
Lijn 2: (4)
Lijn 3: (7, 8 )

Alle coordinaten van het rioolsysteem sla ik op in een Dictionary.

Visual Basic .NET:

Dim dictPoints As Dictionary(Of Integer, Point3d)

Wie kan mij vertellen waar ik moet beginnen om uit de lijst van coordinaten de langste aan een gesloten lijn te genereren.

[pagani]

Klinkt als de klassieke Longest Path: Wikipedia: Longest path problem

(Klik vooral ook door naar Dijkstra's algoritme, daar kom je qua theorie al een heel eind mee, het komt er op neer dat je brute force alle paden bekijkt)

[ Voor 37% gewijzigd door pagani op 26-03-2020 14:22 ]

[skate master]

pagani schreef op donderdag 26 maart 2020 @ 14:06:
Klinkt als de klassieke Longest Path: Wikipedia: Longest path problem

(Klik vooral ook door naar Dijkstra's algoritme, daar kom je qua theorie al een heel eind mee, het komt er op neer dat je brute force alle paden bekijkt)

Dank voor de input, deze had ik zelf niet gevonden.
Ga er eens induiken.

[EfBe]

Je serie lijnen is een directed graph. Wanneer je daar een topological sort op loslaat krijg je de lijnstukken in de juiste volgorde en kun je ook tijdens het sorten bepalen of de graph connected is of dat je meerdere onderdelen hebt. De transitive closure van de graph geeft je alle paden (met lengte als je wilt) tussen 2 punten.

Je kunt dit alles makkelijk bepalen mbv mijn Algorithmia library. Zie https://github.com/SolutionsDesign/Algorithmia. Zie https://github.com/Soluti...wiki/Features-at-a-glance voor een korte toelichting en de tests voor voorbeelden.

[ Voor 12% gewijzigd door EfBe op 27-03-2020 08:50 ]

[skate master]

@EfBe bedankt voor je toevoeging.
Jou Algorithmia library komt op mij erg complex over. Ik zie even niet goed hoe ik deze het beste kan gebruiken. Zelf ben ik geen programmeur maar tekenaar en gebruik het programmeren om het leven van een tekenaar wat gemakkelijker te maken.

Zou je mij kort op weg kunnen helpen in het sorteren van mijn Dictionary middels jou Library?
De dictionary is alsvolgt opgebouwd: Dictionary(Of Integer, Point3d)
Point3d is hierbij een AutoCAD entity waarvan voormij slechts de x, y en z van belang zijn.
Mocht het voor het sorteren beter zijn om de x,y, z waarden op een andere manier op te slaan dan hoor ik dit graag.

[EfBe]

Je uiteindelijke figuur is een 'directed graph'. Een graph bestaat uit 'vertices' (de punten) en de 'edges' (de lijnen tussen de punten). Een edge is een verbinding tussen vertex A en vertex B en in een directed graph heeft die edge een righting (dus bv van A naar B of van B naar A).

Jij hebt in je plaatje de edges een nummer gegeven ipv de vertices. Als je het andersom doet, dus de punten nummers geeft, kun je de edges (verbindingen) tussen de punten aangeven middels bv 2->3 of: (2, 3).

Welnu, in Algorithmia kun je een directed graph maken en daar dan edges en vertices en stoppen. Als je bv naar dit voorbeeld kijkt: https://github.com/Soluti....Tests/GraphTests.cs#L383
dan zie je dat daar een directed graph wordt opgebouwd met vertices met een richting (van A naar B, van A naar C etc.), net als in jouw tekening. Je kunt dan een topological sort uitvoeren op die graph (https://github.com/Soluti....Tests/GraphTests.cs#L392) die de vertices (de punten dus) in de juiste volgorde zet, dus als ik heb:

A->B->C->D
|
v
E

en A->B betekent B volgt op A dan komt daar uit als volgorde: A, E, B, C, D.

Als ik de edges/lijnstukken nu in willekeurige volgorde uit een database lees, dus eerst C->D, dan A->E, dan B->C etc. en ik stop ze in de graph dan krijg ik toch exact de volgorde A, E, B, C, D eruit.

Dat lost volgens mij jouw volgorde probleem op wanneer er een lijnstuk is gewijzigd.

[skate master]

@EfBe bedankt voor je heldere uitleg, dit heeft mij goed op weg geholpen.
Toch loop ik ergens vast waardoor de resultaten niet zijn zoals ik eigenlijk verwacht.

Bij het uitlezen van de Database komen de riool strengen er in onderstaande volgorde uit.

P1 	- P4 	- 256437.16,470813.698 	=== 256348.604,470756.369
P4 	- P21 	- 256348.604,470756.369 === 256298.953,470723.6
P20 	- P11 	- 256370.268,470717.868 === 256361.293,470741.441
P11 	- P4 	- 256361.293,470741.441 === 256348.604,470756.369
P1 	- P12 	- 256437.16,470813.698 	=== 256464.5,470823.2
P12 	- P2 	- 256464.5,470823.2 	=== 256471.583,470824.378
P22 	- P12 	- 256460.286,470831.510 === 256464.5,470823.2

Verwachte uitkomst na Sorteren (langste aaneengesloten lijn)
P2, P12, P1, P4, P21

Uitkomst na Sorteren

P22 	256460.286,470831.510
P20 	256370.268,470717.868
P11 	256361.293,470741.441
P1 	256437.16,470813.698
P12 	256464.5,470823.2
P2 	256471.583,470824.378
P4 	256348.604,470756.369
P21 	256298.953,470723.6

Hieronder het deel van de code waarin ik de knooppunten aan een Graph toevoeg en er een Sort op los laat. In jou voorbeeld geef je bij het sorteren een Expected result mee, maar dit weet ik dus vooraf niet.

Visual Basic .NET:

Dim algGraph As Graphs.DirectedGraph(Of String, Graphs.DirectedEdge(Of String)) = New Graphs.DirectedGraph(Of String, Graphs.DirectedEdge(Of String))

For Each oPipeID As ObjectId In ocPipeIds
    Dim bobStart As String = pipe.StartPoint.X.ToString & "," & pipe.StartPoint.Y.ToString
    Dim bobEnd As String = pipe.EndPoint.X.ToString & "," & pipe.EndPoint.Y.ToString

    'Algoritmia
    algGraph.Add(New Graphs.DirectedEdge(Of String)(bobStart, bobEnd))
Next

Dim sorter As Graphs.Algorithms.TopologicalSorter(Of String, Graphs.DirectedEdge(Of String)) = New Graphs.Algorithms.TopologicalSorter(Of String, Graphs.DirectedEdge(Of String))(algGraph, True)
sorter.Sort()

'Dim expectedResults As List(Of String) = New List(Of String) From {}
For i As Integer = 0 To sorter.SortResults.Count - 1
    'Onderstaande Regel wordt niet herkend, daarom als commentaar vermeld
    'Assert.AreEqual(expectedResults(i), sorter.SortResults(i))
    Dim sPNT as String = sorter.SortResults(i).ToString.Split(",")
    Dim pntNw As Point3d
    'X en Y combineren tot AutoCAD Punt
    pntNw = New Point3d(CDbl(sPNT(0)), CDbl(sPNT(1)), 0)
    'punt toevoegen aan collection om later een lijn van te maken
    pointCol.Add(pntNw)
Next i

Wat doe ik fout bij het gebruiken van Library?
Hieronder nog een plaatje van het netwerk waar bovenstaande coordinaten bij horen.