Re: AW: Sortieren von geschlossenen Konturen

[Patrick Scheibe <patrick@XXXXXXX.de>]

Moin,

nehmen wir an du hast eine wilde Liste mit solchen Punktpaaren, die
jeweils ein Liniensegment darstellen und du weisst, dass die Punkte
einen Zyklus bilden. Sie sind eben nur nicht sortiert:

points = RandomSample[#, 
    Length[#]] &[{{20 Sin[#1], 20 Cos[#1]}, {20 Sin[#2], 
      20 Cos[#2]}} & @@@ 
   Partition[Table[N@Mod[phi, 2 Pi], {phi, 0, 2 Pi, Pi/10}], 2, 1]]
ListPlot[points, AspectRatio -> Automatic]

Dann koennte man doch zuerst mal die Punkte "eindeutig" umbenennen. Bei
den Liniensegmenten gibt es ja immer 2 wo bei dem einen ein Punkt am
Ende genau der Anfangspunkt des anderen Liniensegments ist. Diese Punkte
kriegen dann die selbe ID:

renameRule = (Thread[# -> Range[Length[#]]] &@
    DeleteDuplicates[Flatten[points, 1]]);
unsrtEdges = points /. renameRule

Dabei eraehaelt man dann sowas der Art {{1, 2}, {3, 4}, {5, 6}, {7, 8},
{9, 5}, {10, 11}, {2, 12},... wobei die Zahlen die IDs der Punkte sind.
Tja und dann haette ich an sowas wie

<< Combinatorica`
g = FromUnorderedPairs[unsrtEdges];
cycl=FindCycle[g]
Graphics[Line[cycl /. (Reverse /@ renameRule)]]

gedacht. Funktioniert bei mir auch bei 1000 Liniensegmenten innerhalb
von Sekunden. Wenn du mehrere Zyklen drin hast, dann schau dir die
Funktion ExtractCycles an, die gibt dir alle moeglichen Zyklen aus.
Ich hoffe das gibt dir einen Ansatzpunkt,

Cheers
Patrick



On Mon, 2010-07-26 at 17:16 +0200, Stefan Fuhrer wrote:
> Es wurde nicht der ganze Eintrag abgedruckt. Hier der fehlende Teil.
> 
> Der komplette Datensatz selbst {Liniensegment 1, Liniensegment 2....}.
> 
> Gestern Abend habe ich folgenden Lösungsansatz versucht, welcher aber noch
> nicht ausgereift ist.
> Ich probiere folgendes: Es werden bereits die Triangel Kante an Kante
> (welche in der Schnittebene enthalten sind) sotiert. Dies realisiere ich mit
> folgenden Code, welcher ich in ähnlicher weise hier im Forum gefunden habe:
> 
> side3D[{a_, b_, c_}] := {{a, b, c}, {a, c, b}, {b, a, c}, {b, c, 
>    a}, {c, a, b}, {c, b, a}}
> 
> SortPolygones[T_] := Module[{edge, data, ii},
>   edge = Flatten[Map[side3D, T], 1];
>   data = Union[Map[Sort, edge]];
>   ii = Dimensions[data][[1]];
>   Table[Polygon[data[[i]]], {i, 1, ii}]
>   ]
> 
> T ist der komplette Datensatz. Leider habe ich noch keinen Ansatz wie ich
> das Problem lösen kann wenn mehrere Konturen in dem Datensatz vorhanden
> sind.
> 
> Besten Dank
> Grues Stefan
> 
>