Algorithmen zum Schraffieren von Objekten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Algorithmen zum Schraffieren von Objekten

    Hallo zusammen,

    da ich z. Z. keine drängenden Programmier-Probleme habe, ist der Kopf wieder frei für Grundsätzliches ... und prompt ergeben sich allgemeine Fragen: Nicht zu konkreten Umsetzungen oder Code-Beispielen, sondern mehr zum Konzeptionellen.

    Ich grüble schon seit langem (!) darüber, nach welchem Algorithmus man einen geschlossenen Pfad schraffieren kann. Idealerweise sollte diese Schraffur nicht aus mehreren parallelen Linien bestehen, sondern aus einer Zickzack-Linie.
    • Ein einfaches Beispiel: Gegeben ist ein geschlossener Pfad, nehmen wir einmal ein Rechteck, und ich möchte dieses "in einem Zug" schraffieren. Hierzu lege ich Anfangspunkt und -richtung fest, dazu einen Winkel und den Maximalabstand zwischen den "Eckpunkten" (o. ä.) ... wie könnte man die notwendigen Eckpunkte der Schraffur bestimmen (die auf dem Rechteckpfad liegen sollten)?
    • Komplexeres Beispiel: Ich habe den Umriss (-pfad) eines schlanken Objektes, z. B. ein Buchstaben. Wie fülle ich diesen quer zur Schreibrichtung mit einer Zickzacklinie?
    Ich bin nicht sicher, ob ich die Problemstellung klar machen konnte, vielleicht schiebe ich nachher noch ein paar Skizzen nach. Frage an Euch: Kennt Ihr Literatur oder auch nur gute Stichworte, die sich mit dieser Thematik beschäftigen. Algorithmen wäre natürlich klasse, aber auch für Recherche-Hinweise bin ich dankbar. Mein Google-fu scheitert leider, da Suchbegriffe wie "path fill hatch" zwar zu einigen interessanten Grundsatzartikeln führen, mir aber noch keine Code-Idee liefern ... irgendwie fehlt mir der Ansatz.

    Ob aus dem Ganzen jemals ein Programmierprojekt wird, weiss ich noch nicht, aber es reizt mich schon seit Jahren :rolleyes:

    Ciao, Mattes
    Diese Seite bleibt aus technischen Gründen unbedruckt.

  • Das ist ein relativ komplexes Thema, was sich wahrscheinlich nicht so einfach in einem Forum beantworten lässt. Zum Thema Füllalgorithmus findest Du relativ viele Tutorials, Vorlesungen u. Ä. bei Google. Als einfache Möglichkeit in Cocoa böte sich der Clipping-Algorithmus von CoreGraphics an: Du verwendest den Polygonzug als Clipping-Pfad und zeichnest dann in einem größeren Bereich Deine Zickzacklinien.
    „Meine Komplikation hatte eine Komplikation.“

  • Der Trick ist, wie Moon schon sagte, das du erstmal definierst was ist Füllfläche und was nicht. Wenn Du das nicht weißt, weil du es nicht selber gezeichnet hast, dann geht das relativ zuverläßig (bei extrem komplexen Formen versagt die Methode schonmal), indem du einen Zeilenweisen Scan machst und immer den Zustand wechselst wenn du auf ein Randpixel triffst. Da sollte es im INET genug einfach Algorytmen geben.
    Danach suchst du dir die Min/Max Werte und zeichnest in einen Buffer Deine Füll-ZickZackinie oder was auch immer. Danach composed du dies nur an den stellen in Dein Bild wo du füllpixel gefunden hast.

    Gruß

    Claus
    2 Stunden Try & Error erspart 10 Minuten Handbuchlesen.

    Pre-Kaffee-Posts sind mit Vorsicht zu geniessen :)

  • Danke für's Mitdenken! Ich werde mich nach und nach einmal in die Materie einlesen, bisher bin ich auch gedanklich beim "zeilenweisen Scannen", so in der Art:
    • Objekt an "Schraffierungswinkel" ausrichten
    • Bei "Startpunkt" beginnen und
    • immer um "Maximalabstand" versetzt suchen, wo ein Schnittpunkt mit dem Objekt-Pfad vorliegt.
    Interessant wird es dann bei Kurven, Öffnungen und ähnlichem. Aber wie gesagt nichts, was ich morgen lösen muss ... mehr eine Art Gehirn-Jogging.

    @entwickler: CoreGraphic Pattern sind ja nur eine Methode der graphischen Darstellung. Die ist mir ehrlich gesagt egal (besser: zweitrangig). Mir geht es darum, einen Algorithmus zu finden, der mir zu einem gegebenen Objekt die Schraffurlinie mit ihren Koordinaten liefert.

    Der Praxisbezug: Ich möchte auf Basis eines (Vektor-) Elementes "Befehle" erzeugen, mit denen eine Stickmaschine dieses Objekt mit vielen Stichen füllen würde, vergleichbar einem Plotter, der eine Fläche ausmalt. Das o. g. Problem ist dabei nur der erste Schritt, es kommen noch viele spezifische hinzu (Underlay, Fadenspannungsausgleich, ...). Aber irgendwo muss man gedanklich ja mal anfangen :)

    Mattes
    Diese Seite bleibt aus technischen Gründen unbedruckt.

  • Ein Strickmuster schon, ein Stickmuster (ohne "r") ist eher Vektorgrafik. Dennoch ist der Anspruch auf Genauigkeit nicht soooo hoch, jedoch im Bereich von Zehntelmillimeter. Aber das Thema ist auch an anderen Stellen komplex und ich weiß noch nicht, ob meine Zeit und Kenntnisse ernsthafte Versuche zulassen ... Aber ein interessantes Gebiet zum Forschen und Probieren.

    Mattes
    Diese Seite bleibt aus technischen Gründen unbedruckt.

  • Wäre es da nicht einfacher, als Ausgabe das Format zu wählen, was die Maschine bzw. die Software, die die Maschine ansteuert, importieren kann?
    Heutzutage können die doch eps, svg importieren, sicher, wenn Du besondere Sticheffekte mit hinneinnehmen möchtest, wird es wahrscheinlich nur über
    ein entsprechendes Dateiformat gehen (gut, wenn es ein Herstellerübergreifendes Format geben würde, was man benutzen könnte -> ich vermute mal jeder hat sein eigenes Süppchen)

    Aber ich stelle mir vor, das man mit so einer Softare für Stickmaschinen „einfach“ ein bestimmtes Pattern vorgibt (Zickzacklinie oder was auch immer) und dann die Fläche auswählt (wie bei Illustrator)
    Dann kümmert sich entweder die Maschine darum und wird über die Software auf dem Desktop angesteuert, somit würde das genaue Berechnen der zu stickenden Linien entfallen.
    Und es wäre vermutlich kompatibler als alles selbst zu berechenen und dann unter Umständen für jede Maschine die entsprechenden Steuerbefehle herauszufinden.

    Stickmaschinen sind ein feines Spielzeug (oder Werkzeug, für die, die damit Geld verdienen). :)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von entwickler ()

  • entwickler schrieb:

    Und es wäre vermutlich kompatibler als alles selbst zu berechenen und dann unter Umständen für jede Maschine die entsprechenden Steuerbefehle herauszufinden.

    Die Maschinen können "nichts", sie erwarten Steuerbefehle wie x/y-Bewegungen, Farbwechsel und Sprungstiche ... zwar in unterschiedlichen, herstellerspezifischen Dateiformaten, aber inhaltlich sehr vergleichbar. Die meisten Maschinen erhalten diese Befehle per USB-Stick oder Direktverbindung, und es liegt bei der erstellenden Software bzw. der Fähigkeit des Benutzers, aus graphischen Objekten diese Steuerbefehle zu erstellen. Und genau das möchte ich mit einer Software machen, zum Beispiel auf Basis von Fonts.

    Die Ausgabe ist für mich kein Problem, wenn ich erst einmal die Koordinaten der Stiche habe. Wenn man das Thema "Punchen" aber ernsthaft unterstützen möchte, spielen noch andere Dinge hinein: Die Muster müssen z. B. mit einem "Unterbau" versehen werden, damit sich der Stoff nicht verzieht, Füllungen müssen mit unterschiedlichen Mustern erfolgen, Stichlängen berücksichtigt werden, überdeckte Stiche entfernt werden ... das Thema kann mich noch lange beschäftigen und ich weiß nicht, ob da je etwas Sinnvolles herauskommt. Das perfekte Hobby eben :)

    Mattes
    Diese Seite bleibt aus technischen Gründen unbedruckt.

  • Zuerst hatte ich auch an NSColor colorWithPatternImage: gedacht, aber das passt nicht wenn Du die Koordinaten haben willst.

    Du kannst auch versuchen die Umrissline als Bezier-Pfad zu bekommen (NSStrings lassen sich glaube ich formatieren und umwandeln - NSFont?). Und dann die Stücke per Parameter (t=0...1) abfahren und daraus Linienendpunkte bilden. Etwas schwierig stelle ich mir vor die Schrittweite zu bestimmen und das dazugehörige (also irgendwie gegenüberliegende) Endpunktepartner-Bezier-Pfad-Segment. Evtl. hilft da aber eine Suche.

    Wenn die Striche nur horizontal sein sollen, dann ist es einfach. Suche mal nach Tesselation. Das ist ein Algorithmus der ein Polygon nach y-Koordinaten sortiert und dann stückweise Trapeze erzeugt die sich nicht überlappen, aber die Fläche füllen. Die Trapeze kann man dann mit einfachen Koordinatenrechnungen füllen. Und einen NEBezierPath kann man näherungsweise als Polygon darstellen.

  • macmoonshine schrieb:

    Auch ein Stickmuster ist ein Gitter, also im Prinzip eine Pixelgrafik. Du kannst ja die Stiche nicht an beliebigen Punkten setzen, sondern bist immer an die Maschen des Stoffes gebunden, oder?

    Nicht wirklich. Die meisten Muster speichern relative Nadelbewegungen in 1/10 mm, somit hat Du zwar ein rechtwinkliges Koordinatensystem, aber die Auflösung ist schon recht hoch. Pixelbasierte Algorithmen funktionieren dabei nur bedingt, vektororientierte Ansätze liegen dem ganzen näher ... wohlgemerkt rede ich hier nicht von irgendwelchen Kreuzstichmustern, da hättest Du recht.

    Ciao, Mattes
    Diese Seite bleibt aus technischen Gründen unbedruckt.

  • MyMattes schrieb:

    Die meisten Muster speichern relative Nadelbewegungen in 1/10 mm, somit hat Du zwar ein rechtwinkliges Koordinatensystem, aber die Auflösung ist schon recht hoch.

    Mit Pixeln meine ich nicht die Bildpunkte eines Monitors, sondern die Kästchen in einem Gitter, und dabei ist es egal, ob die Kästchen ein Millimeter oder ein Pikometer groß sind. Entscheidend ist doch nur, dass es diskrete Punkte sind. Oder anders ausgedrückt: Bei jeder Sticktechnik gibt es eine maximale Auflösung.
    „Meine Komplikation hatte eine Komplikation.“

  • Schon klar, aber wenn man einen Füllalgorithmus betrachtet, der z. B. rekursiv die Pixel auf Lage in einem Objekt prüft, funktioniert dies nur bedingt, da die gefüllte Fläche ja wieder als Summe vieler Vektoren darzustellen wäre. Die Pixelmenge hilft also nur teilweise, wenn es nicht um das Setzen von Bildpunkten geht. Aber wir wissen m. E. beide, was wir meinen... :)

    Mattes
    Diese Seite bleibt aus technischen Gründen unbedruckt.