I have been developing a dynamic, aesthetic map layout system as a web application for users of Eve Online. I am using Graph::Layout::Aesthetic in order to ensure that map coordinates remain as true to the original as possible.

However, I am running into issues with intersections which I am ill prepared to handle. The code initially takes a map similar to this and translates it into this

As you can see, there are several node placements which result in edge intersections which I have highlighted. Graph::Layout::Aesthetic has forces to combat this but they seem to assume the graph is planar which it often isn't. The only solution I have been able to devise so far is the following:

  1. Iterate through every edge
  2. When an intersection is detected determine if any nodes have a degree of 1
  3. If so, move said node to half the distance from it's connected node to the edge it intersected with
  4. If not, iterate through the connected nodes and determine if there is any movement which could reduce intersections.

I came up with a reasonably viable recursive algorithm but could envision no manner of intelligently moving nodes to reduce intersections (anything I tried went crazy).

Essentially what I am looking for is the most efficient way to reduce the number of intersections while keeping the nodes in as close to their original positions as possible. Thanks for your advice!

In reply to Aesthetic map layout using Graph::Layout::Aesthetic and problems with intersections. by e^n

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.