Hallo, ich würde gerne ein zweidimensionales Polygon aus einem anderen "herausschneiden". Dabei möchte auch konkave Polygone behandeln können.
Ich habe mir gedacht, da ich die Polygone wahrscheinlich ohnehin triangulieren muss, das Problem auf Dreiecke zu reduzieren. (Es sei denn es gibt eine einfache Lösung für das gesamte Problem)

Ich hab mir mal über die Dreiecke Gedanken gemacht und herauskommen sind die drei möglichen Schnittsituationen, die ich angehängt habe.
Nur: Wie behandle ich die? Oder gibt es eine bessere Lösung für allgemeine Polygone?

€: Ich glaube Polygon Clipping ist so ziemlich genau der Begriff für das was ich tun möchte.
Das hier scheint mir nicht wirklich weiter zu helfen: http://de.wikipedia.org/wiki/Algorithmu ... nd-Hodgman

mfg

Du hast vergessen, dass sich die Dreiecke auch überlagern können wie bei einem Sechszackigen Stern, bei der der Mittelpunkte im jeweils anderen Dreieck liegt, aber keiner Der Eckpunkte im jeweils anderen Dreieck ist. Somit schneiden sich nur die Kanten.

Was du vor hast kenn ich übrigens als "carving", keine Ahnung ob das ein gebräuchlicher begriff ist, habs mal früher im Worldcraft(heute Valve Hamme) gelesen für eine ähnlich Funktion, di das selbe für 3d Objekte macht.

Leider kann ich dir nicht dabei helfen den Algorhitmus zu beschreiben... die einzige Idee wäre ähnlich wie bei der seperatet axis theorem herraus zu finden ob und wo sich die Dreiecke schneiden und diese Punkte als neue Eckpunkte zu verwenden, allerdings wüsste ich auch nicht wie man mathematisch garantiert, dass die richtigen Punkte zu einem Dreieck zusammen gefasst werden.

_________________
Klar Soweit?

genau da liegt das Problem. Das Ganze soll möglichst elegant über die Bühne laufen, am besten ohne jeden Sonderfall einzeln zu behandeln und als Output möchte ich halt gleich alle entstandenen Dreiecke bekommen, da es ja auch passieren kann, dass ein Polygon zerteilt wird.

Das Carve Feature aus Worldcraft / Hammer kenne ich, allerdings finde ich unter diesen Begriff nichts zu dem was ich suche

Moin,

ich habe den Code zu einem Polygon-Clipping Algorithmus auf der Platte liegen. Ich habe ihn mir noch nie angeschaut, und er ist in C++ geschrieben,
aber ich denke das sollte zum Verständnis kein Problem sein. Ich finde das Zeug im Internet gerade nicht mehr, deswegen lade ich mal hoch, was ich habe.

Ich hoffe das Hilft dir weiter.

Markus

Hi, vielen Dank, den Code hatte ich allerdings selber rumliegen, nur weiß ich nicht genau, wie er funktioniert und was er leistet. Wenn ich wüsste dass er genau das tut, was ich möchte, würde ich ja her gehen und ihn übersetzen, ansonsten schau ich lieber selbst was hinzubekommen oder einen Code zu finden, der meinen Bedürfnissen entspricht.

Es ist einfacher wenn man alle überlagerungen von den Kanten überprüft. Diese unterbricht man einfach an den Kreuzungen und erhällt unregelmäßig geformte poligone, die man mit einem anderem algoritmus wieder zu 3ecken tesselieren kann.

Der erste nötige algoritmus hat aber einequadratische laufzeit, wenn man die Kanten nicht in einen Quadtree Einsortiert...

_________________
Lumina plattform unabhängige GLSL IDE

Gibt es dazu nicht einen allgemein formulierbaren Algorithmus ?

Just some ideas:

You have 2 polygons (not triangulated/both winded in the same way)
Both polygons share a part of each other (intersection)
You can look into this as if the polygons have collided with each other (lines).
So you can determine if points are used in both polygons and where they collide with each other and get new points there.
This gives you a third polygon with existing/new points.
You can also add the new points to the existing polygons.
You can triangulate the (3) polygons now and render them (e.g. you can use glut functions for that)
I think subtracting the polygons is some more work, but with having the 3rd new polygon comes usefull for that.

_________________
http://3das.noeska.com - create adventure games without programming

einfach die beiden Schnittpunkte ( Verktorengleichungen gleichsetzen ) ermitteln + Polygon umformen !



Das ist jetzt aber höchstwahrscheinlich zu einfach - falsch ...

MfG

_________________
...GOD is wearing black...