Re: [Talk-de] Polygon aus Node-Haufen?
Gary G: schrieb: kennt jemand einen Algorithmus, der aus einem Punktehaufen ein begrenzendes Polygon zaubern kann? Am besten in PERL? kein triviales problem, aber das hast du ja sicherlich schon bemerkt... stichworte sind konvexe oder konkave hülle ich habe den eindruck, dass aus den guten algorithmen auch ein ziemliches geheimnis gemacht wird. als startpunkt habe ich bisher das hier ausgemacht: http://forum.manifold.net/forum/t76235.30 dort findet man auch einige weiterführende links. und dann gibt's natürlich auch noch das problem der löcher, also innere begrenzende hüllen in der äußeren hülle. interessant ist aber, wie schwierig manchmal algorithmische lösungen für dinge sind, die uns menschen relativ leicht fallen. grüße frank ___ Talk-de mailing list Talk-de@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-de
Re: [Talk-de] Polygon aus Node-Haufen?
Gary G: schrieb: Hallo, kennt jemand einen Algorithmus, der aus einem Punktehaufen ein begrenzendes Polygon zaubern kann? Am besten in PERL? Tnx Gerhard gary68 Das ist -so glaube ich- nicht ganz so einfach, da Du da noch mehrere Randbedingungen beachten musst: Die einfachste Variante wäre eine rechteckige BoundingBox. Du könntest aber auch einen Kreis/Ellipse darum legen. Wenn es ein Polygon sein soll, stellt sich die Frage, ab wann ein Punkt noch zur Hülle gehört oder aber nur innen drin liegt. Vielleicht müsste man das iterativ lösen, indem man mit einem Rechteck beginnt und dann die Ecken so lange abschneidet, bis der erste Punkt auf der neuen Schnittkante liegt (und kein anderer außerhalb) usw. Gruß, Stefan ___ Talk-de mailing list Talk-de@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-de
Re: [Talk-de] Polygon aus Node-Haufen?
Gary G: schrieb: kennt jemand einen Algorithmus, der aus einem Punktehaufen ein begrenzendes Polygon zaubern kann? Am besten in PERL? Es kommt darauf an, was Du machen willst. Konvexe und konkave Hüllen wurden Dir ja schon vorgestellt. Wenn sich allerdings zwei Hüllen nicht überschneiden sollen, musst Du mit Theissen bzw. Voronoi arbeiten, das ist aber sehr performancelastig, gibt jedoch sehr gute Ergebnisse. Das hier könnte Dir aber insgesamt helfen: http://livarot.sourceforge.net/ http://sourceforge.net/project/showfiles.php?group_id=74523 Lässt sich sicherlich zu PERL portieren. ___ Talk-de mailing list Talk-de@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-de
Re: [Talk-de] Polygon aus Node-Haufen? // Nachtrag
Sorry, ich meinte: http://www.qhull.org/ ___ Talk-de mailing list Talk-de@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-de
[Talk-de] Polygon aus Node-Haufen?
Hallo, kennt jemand einen Algorithmus, der aus einem Punktehaufen ein begrenzendes Polygon zaubern kann? Am besten in PERL? Tnx Gerhard gary68 ___ Talk-de mailing list Talk-de@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-de
