in reply to Data visualisation.

I suppose this is a follow-up to the Travelling Salesman discussion we had.

Are you even sure that the data is euclidian or even metric, i.e. projectable into a plane???

In general thats not solvable, if not!!!

(first imagine the problems from projecting distances from a spheric surface like the globe (which is still possible) and then think about randomly generated distances...)

Algorithm derived from school geometry

If they are metric euclidean you can start choosing freely point A, then B in a circle surrounding A, then C on one of the two crosspoints of the circles surrounding A and B.¹ From there on all other points are determined by the distances from A,B and C.³

After this you just need to transform the points (moving, rotating) to fit into a desired window.²

Then you are free to plot with the technology of your liking (Tk, SVG, graphviz,...)

HTH!

Cheers Rolf

( addicted to the Perl Programming Language)

updates
¹) Thats how a triangle is constructed with a pair of compasses, if only the length of three sides are given. Surprisingly I couldn't find an image in the net describing this. (update: watch animation here)

²) see Clipping_(computer_graphics)

³) and at least now it should be obvious why random distances to other points will fail.

Replies are listed 'Best First'.
Re^2: Data visualisation. (updated)
by roboticus (Chancellor) on Jan 02, 2014 at 13:00 UTC

    LanX:

    Update 2: I've got an updated program in Re: Data visualisation..

    Update: I was thinking you meant TSP wasn't solveable. I didn't read this thread before replying, I just picked the subject out of the list and thought it was a discussion on that.

    I'm curious about your assertion that the general case isn't solveable in the general case if the data doesn't correspond to a planar map. I just don't see how that follows. Can you elaborate on that?

    Anyway, I don't believe the data was planar. A few days ago, I was twiddling with the problem, and I wanted to see the graph, so I decided to graph it and find the point coordinates (modulo translation and rotation). My test/demo data would always come up fine, but the TSP data wouldn't resolve.

    If time and interest permits, I'm thinking of a way to integrate force-driven layout into the code to try to get a reasonable layout with errors and residual "forces" along each edge listed. I haven't started that yet. But just in case anyone wants to play with the code, I'm including it in readmore tags below.

    Read more... (13 kB)

    ...roboticus

    When your only tool is a hammer, all problems look like your thumb.

[reply]
[d/l]
[select]
      > I'm curious about your assertion that the general case isn't solveable in the general case if the data doesn't correspond to a planar map.

      It depends on the criteria you have on "displayable".

      If it's defined such that each edge-length has to be congruent to the distance in the matrix, you can simply follow the algorithm I sketched to see how each point's position is determined by the distance to 3 other points.

      I.e. the distance to all other points can't be randomly chosen.

      Since I had differential geometry at university I know that there are "distance-true"¹ projections originating from non-plane spaces like spheres².

      This is no contradiction, since this data still has to fit into aforementioned algorithm.

      The projection won't be "angle"¹ or "surface"¹-true, which is a problem for maps but not for graphs. I.a.W. the origin of the data doesn't need to be from a planar geometry but the graph needs to be planar euclidean!

      I will try to update some WP links...

      Cheers Rolf

      ( addicted to the Perl Programming Language)

      ¹) not sure about the appropriate English terminology.

      ²) remembered it wrong sorry, see Map_projection#Metric_properties_of_maps, and in hindsight it's obvious that projections can only preserve distances if the Pythagorean theorem holds. Though preserving size of areas and angles are no problem.

[reply]
A reply falls below the community's threshold of quality. You may see it by logging in.

In Section Seekers of Perl Wisdom