✔ html map (poly)

[Nob]

Hallo Zusammen

Ich stehe wieder einmal an.

Ich habe ein Array mit x und y coordinaten.

Array
(
    [0] => Array
            [x] => 6
            [y] => 4
    [1] => Array
            [x] => 1
            [y] => 6
    [2] => Array
            [x] => 3
            [y] => 4
    [3] => Array
            [x] => 2
            [y] => 3
    [4] => Array
            [x] => 3
            [y] => 2
    [5] => Array
            [x] => 5
            [y] => 5
    [6] => Array
            [x] => 5
            [y] => 1
)

Ich möchte jetzt eine html-map anhand dieses arrays generieren.
Wie muss ich das Array sortieren, damit ich am schluss so eine map bekomme:

<area shape="poly" coords="1,6,3,4,5,5,6,4,5,1,3,2,2,3">

und nicht z.b. so eine:

<area shape="poly" coords="6,4,1,6,3,4,2,3,3,2,5,5,5,1">

Im Anhang sieht man den Unterschied deutlich. Wenn ich die map so generiere, funktioniert es natürlich nicht wie gewünscht.

Hat jemand eine Idee?
Besten Dank

 

[ComFreek]

Welche Sortierreihenfolge willst du denn bzw. wie kommst du auf deine Lösung?

 

[Nob]

hmm gute Frage... ich möchte halt keine überschneidungen, damit die map die ganze Fläche abdeckt.
Von Auge sieht man es ja schnell... aber der Computer?

 

[ComFreek]

Hmm. Es kann erst ab 2 Linien (also die 3.) zu Überschneidungen kommen.
Zumindest theoretisch würde ich das somachen:

1. Ersten Vektor einlesen
2. Zweiten Vektor einlesen
3. Dritten Vektor einlesen
4. Alle übrigen Vektoren durchgehen und prüfen, ob
   • Die Linie von Vektor i und Vektor 3 sich überschneiden mit den vorherigen

Vielleicht ein Ansatz (die Funktionen müsstest du noch schreiben)

// Line(v1, v2) gibt eine Linie von zwei Vektoren zurück
// OverlappedLine(l1, l2) gibt true zurück, wenn Linie 1 und Linie 2 sich schneiden, sonst false

$coords = "";
for ($i=0; i<3; i++)
{
  $coords += $Vectors[i]['x'].",".$Vectors[i]['y'];
}
for ($i=3; $i<count($Vectors); $i++)
{
  $overlapped = false;
  for ($j=0; $j<$i; $j++)
  {
     if (OverlappedLine(Line($Vectors[i]['x'],$Vectors[i]['y']),  Line($Vectors[j]['x'], $Vectors[j]['y']))
     {
       $overlapped = true;
       break;
     }
  }
  if ($overlapped==false) $coords += $Vectors[i]['x'].",".$Vectors[i]['y'];
}

 

[Nob]

Erstmals Danke für deine Antwort.

Wohin gehe ich mit dem Vektor wenn er überlappt?

if ($overlapped==false) $coords += $Vectors[i]['x'].",".$Vectors[i]['y'];

Die ersten 3 Vektoren überschneiden sich nicht, das stimmt aber was wenn sie wie im Anhang gewählt werden?
Dann kann ich die anderen Punkte ohne eine Überschneidung nie mehr erreichen...

 

[ComFreek]

Wohin gehe ich mit dem Vektor wenn er überlappt?

if ($overlapped==false) $coords += $Vectors[i]['x'].",".$Vectors[i]['y'];

Gute Frage. Ich würde sagen, dass man diesen Vektor um eins nach hinten schiebt (im Array):

if ($overlapped==true)
{
  // $Vector[i] nach hinten schieben
}

 

[Nob]

Hmm trotzdem könnte der Fall im vorheriger Anhang auftreten... dann kann man ihn solange nach hinten schieben wie man möchte... ohne Erfolg

 

[ComFreek]

Mehr fällt mir leider nicht ein.

Ein Computer wird niemals den Menschen ersetzen können....

 

[Nob]

Trotzdem Danke

Sonst jemand?

 

[Sven Mintel]

Moin,

ich glaube nicht, dass es einen Algorithmus für "so eine map" geben kann....denn anhand deiner Punkte gäbe es mehrere Varianten, die sich nicht überschneiden.

Wieauchimmer, vielleicht bietet dies ja einen möglichen Lösungsansatz: http://www.inf.fh-flensburg.de/lang/algorithmen/geo/graham.htm