Jak narysować wykres z rozłącznymi krawędziami?

Mam macierz sąsiedztwa dla wykresu. Muszę wizualizować ten wykres bez przecinania krawędzi. Wierzchołki na wykresie można rozmieszczać losowo. Znam jedno rozwiązanie - wyliczenie wszystkich krawędzi dla skrzyżowań. Jeśli krawędzie przecinają się, a następnie przestawiają wierzchołek, ale jest on zbyt drogi dla dużej liczby wierzchołków (więcej niż 20). Jakieś inne pomysły, jak sprawdzić przecinające się krawędzie?Jak narysować wykres z rozłącznymi krawędziami?

Źródło

2014-05-06 mindw0rk

Czego szukasz to algorytm rysowania planarnego, np. Zaimplementowany przez [boost] (http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/planar_graphs.html). Oczywiście może to działać tylko wtedy, gdy wykres jest rzeczywiście planarny, który nie został określony. –

[Tutaj] (http://stackoverflow.com/questions/2751826/which-c-graph-library-ould-i-use) to lista bibliotek, które wykonują graficzne układy, w tym także doładowania. Jeśli chcesz zaimplementować własny, [tutaj] (http://www.csi.ucd.ie/staff/aquigley/home/downloads/aq-gd2000.pdf), jest algorytm, który wykonuje wykresy 2d. –

Bardzo łatwo jest zwizualizować dowolny wykres w płaszczyźnie 3D z rozłącznymi krawędziami.

1) Umieść wszystkie wierzchołki w dowolnym punkcie płaszczyzny 3D, tak aby żadne trzy wierzchołki nie były współliniowe, a żadne cztery wierzchołki nie były w tej samej płaszczyźnie.

2) Przejdź przez matrycę przyległości i narysuj linię/krzywą, aby połączyć wierzchołki.

Na płaszczyźnie 2D nie można zagwarantować istnienia rozwiązania. Na przykład weź najgorszy scenariusz, że istnieje około 10 wierzchołków i każdy wierzchołek jest ze sobą połączony.

Źródło

2014-07-03 09:16:52 cegprakash

Jak narysować wykres z rozłącznymi krawędziami?

Odpowiedz

Powiązane problemy