Algorithm zum Polygonüberwachung

[Stasik]

Guten Tag,
habe ein Problem,
Möchte sowas wie Vectorgraphik in HTML/JS realisieren. Dazu möchte ich ein Bild mit einem Polygon (gegeben durch die Eckpunkte, relativ zur Ecke des Bildes) überlagern (gespeichert als Array, von Punkten). Ich möchte nun die Überschneidungen mit einem anderen Solchen "Polygon" überwachen (beim Bewegen). Nun, wie löse ich sowas algorithmisch? Ideen? Bücher? Oder soll ich ma einfach ein Lehrstuhl ansprechen?
Gruss und danke für die Hilfe
Sten

[rootnode]

also, ein einizges Polygon an sich liegt ja immer in ner Ebene. Also mach mittels der beiden Ebenen der Polygone erstma n groben Test ob sich die Überprüfung überhaupt lohnt. Wenn ja, dann Teste ob die Schnittgerade innerhalb beider Polygone liegt.

[oxygen]

Algorithmisch lösen? Das ist ja wohl einfachste Mathematik. Wenn du mal Googlen willst, such doch mal nach Kollisionserkennung.
In einfachen Fällen reicht es wohl auch wenn du eine Bounding Box benutzt, sprich ein einfaches Rechteck dass das Polygon enthält. Bei 2 Rechtecken lässt sich das ganze mit 2 if Abfragen abhandeln.

[Stasik]

nein, alle liegen in verschiedenen z-ebenen (ist ja html/dom) modell, also ebene ist nicht releveant

[Stasik]

Algorithmisch lösen? Das ist ja wohl einfachste Mathematik. Wenn du mal Googlen willst, such doch mal nach Kollisionserkennung.
In einfachen Fällen reicht es wohl auch wenn du eine Bounding Box benutzt, sprich ein einfaches Rechteck dass das Polygon enthält. Bei 2 Rechtecken lässt sich das ganze mit 2 if Abfragen abhandeln.

ja, mit den boundig Boxen habe ich ja schon will das ja html quasi erweitern. Also die linien zu ziehen ist schon nicht so trivial.. aber ich goggel mal

[Tempest]

Hast du schon in den Cormen nachgeguckt? Kapitel 33 - Algorithmische Geometrie
- Computational geometry
- Geometric algorithms
- Line segment intersection
- Sweep line algorithm

[Stasik]

danke für den tipp, irgendwas auch auf deutsch?

[Tempest]

Hab 2 Stück von dem Corman (Algorithmen - Eine Einführung, deutsche Ausgabe) im Lehrbuchsammlung gesehen.

Temp

[Coolcat]

Also wenn es nicht zu sehr auf Performance ankommt brauchst du doch nichts weiter tun, als jede Kante des Polygons mit jeder Kante des anderen Polygons auf Schnitt zu testen.

Polygon 1: Kante A -> B
Polygon 2: Kante C -> D

Code: Alles auswählen

// Geradengleichung aufstellen
p = A;
q = C;
d = B-A;
e = D-C;
// Gleichungssystem aufstellen

Code: Alles auswählen

if (det(M) == 0) {
    // Geraden sind parallel
    // teste ob A oder B auf q+et liegt
    // teste ob C oder D auf p+ds liegt
}
else {
    // geraden schneiden sich irgendwo, löse LGS
    // (vertausche Zeilen wenn d_y betragsmäßig größer als d_x ist. Frage den lieben Herrn Prof. Esser warum ;) )

Code: Alles auswählen

    if (0>=t && t<=1 && 0>=s && s<=1) {
        // Geraden schneiden sich bei p + ds
    }
    else {
        // Schnittpunkt außerhalb der Kanten
    }
}

Aufwand ist natürlich O(n^2), geht sicher besser. Aber ich nehme mal an das deine Polygone nicht aus hunderten von Kanten bestehen, daher sollte das doch kein Problem sein.
Möglicherweise macht ein BoundingBox-Test vor dem eigentlichen testen Sinn, wenn die Polygone häufig weit auseinander liegen.

Coolcat

[Stasik]

ja, ich teste es zwar anders, aber im prinzip geht genau so

[Ubik]

Oder benutzt das Separating Axis Theorem - wenn du nach SAT googelst findest du sicherlich genug Material dazu. Allerdings klappt das nur für konvexe Polygone, also müsstest du konkave Polygone in konvexe zerlegen ( dafür gibt's aber auch genug Algorithmen ).

[mirko]

wenn du nach SAT googelst

[p0llux]

wenn du nach SAT googelst findest du sicherlich genug Material dazu.

Und noch vieles mehr

[Stasik]

hab BuK schon hinter mir, aber danke