Algorithmus für die Übereinstimmung von Position und Größe von zwei Rechtecken

Question

Ich bin auf der Suche nach einem Algorithmus, der Folgendes berechnet: Ich habe ein Bild mit einem vordefinierten Bereich (der grüne auf dem angehängten Bild). Der Benutzer zeichnet das rote Rechteck und der Algorithmus sollte berechnen, ob das rote Rechteck in etwa dem grünen Rechteck entspricht. Zum Beispiel wäre die Position des roten Rechtecks ​​auf dem angehängten Bild in Ordnung.

Was ist eine gute Möglichkeit, dies zu berechnen? Gibt es einen Best-Practice-Algorithmus?

Meine Idee ist es, die Mitte des roten Rechtecks ​​zu berechnen und dann zu bestimmen, ob die Mitte innerhalb des grünen Rechtecks ​​ist. Außerdem würde ich berechnen, ob die Länge und Höhe ungefähr der Länge und Höhe des grünen entsprechen (25% mehr oder weniger).

Ist das eine gute Idee? Irgendwelche anderen Vorschläge?

Answer 1

Berechne die Fläche des Kreuzungs und dividieren durch den Mittelwert der Flächen der beiden Rechtecke (arithmetischer oder geometrischer). Sie werden einen Bruchteil bekommen. Je näher an 1, desto besser das Spiel.

Answer 2

• Den durchschnittlichen Abstand zwischen Scheitelpunkten als Kriterium für die Nichtübereinstimmung nehmen.
• Lets erste Rechtecke Eckpunkte [x1,y1], [x2,y2], [x3,y3], [x4,y4] annehmen und für zweite sind [a1,b1],[a2,b2],[a3,b3],[a4,b4]
• euclidiean distance zwischen diesen Punkten bekommen würde
• Lower Abstand bessere Übereinstimmung bedeutet, zum Beispiel genaue Überlappung geben 0, eine Form Verschiebung oder Offsetverschiebung eines Rechtecks Erhöhen Sie die durchschnittliche Entfernung der Scheitelpunkte.

Answer 3

das Problem Untersuchung, neige ich dazu, über die Bedingungen, zu denken, die den Vergleich der grünen und die roten Rechtecke scheitern, zusammen mit Argumentation über die fehlerhaften Bedingungen, getrennt über jede Bedingung machen sollte.

Was ich oben meine, praktisch ist, dass ich aus dem Algorithmus die folgenden Antworten mochte, machen klar, was Aspekt des Vergleichs fehlschlägt:

1. Ihr Rechteck Breite Art und Weise ausgeschaltet ist.
2. Die Höhe Ihres Rechtecks ​​ist weit entfernt.
3. Die horizontale Platzierung Ihres Rechtecks ​​ist weit entfernt.
4. Die vertikale Platzierung Ihres Rechtecks ​​ist weit entfernt.

Lassen Sie uns die oben genannten Bedingungen "failing conditions" nennen. Diese versagenden Bedingungen lassen meinen Blick auf den Vergleich erahnen, der unweigerlich meinen Ansatz bestimmt. Man könnte es anders sehen ("Der Bereich Ihres Rechtecks ​​ist weit weg."). Der Benutzer könnte natürlich allgemeinere Antworten wie die folgenden erhalten:

• Die Abmessungen Ihres Rechtecks ​​sind weg.
• Die Platzierung Ihres Rechtecks ​​ist weit entfernt.
• Ihr Rechteck ist weg. Versuch es noch einmal.
• Alter, bist du betrunken?

Im Folgenden verwende ich green zum grünen Rechteck als ein Objekt Bezug zu nehmen und red als Objekt auf das rote Rechteck zu verweisen. Alle Bedingungen basieren auf relativen Fehlern, d. H. Absoluten Fehlern, die in Bezug auf die tatsächlichen Werte normalisiert sind, d. H. Die Werte des grünen Rechtecks.

Eine Sache, die angegeben werden muss, ist, was "weg" für horizontale und vertikale Platzierung bedeutet. Dies bedeutet, dass eine Divergenz zwischen der Position eines Schlüsselpunkts des grünen Rechtecks ​​und der Position des entsprechenden Schlüsselpunkts des roten Rechtecks ​​besteht. Lassen Sie uns die Mitte eines Rechtecks ​​als Schlüsselpunkt für Vergleiche wählen (man könnte die obere linke Ecke des Rechtecks ​​wählen).

Eine andere Sache, die spezifiziert werden muss, ist, wie Sie zwei Punkte in einer relativen Weise, getrennt für jede Achse, vergleichen können. Sie benötigen einen Referenzwert. Sie können den absoluten Versatz zwischen den beiden Punkten in jeder Achse berechnen. Dann können Sie den relativen Versatz in Bezug auf die entsprechende Dimension des grünen Rechtecks ​​berechnen. Zum Beispiel können Sie den relativen horizontalen Versatz als absoluten Versatz zwischen den Mittelpunkten auf der x-Achse dividiert durch die Breite des grünen Rechtecks ​​berechnen. Alles in allem, damit ein Vergleich gelingt, möchte ich, dass die Rechtecke fast dieselben Abmessungen und fast denselben Mittelpunkt haben. Wo "fast" sollte als Prozentsatz quantifiziert werden.

Bezüglich andernfalls Zustand (1), unter der Annahme, dass der maximale relative Fehler für das Rechteck der Breite erlaubt 25% ist, die Boolesche Wert, den wir berechnen müssen, ist:

| green.width - red.width |/green.width > 0.25 

Wenn über dem Wert true ist, dann geht die Fehlerbedingung (1) aus. Der Typ ist vielleicht betrunken. Wir können beenden und benachrichtigen.

Bezüglich andernfalls Zustand (2), unter der Annahme, dass die maximale 30 relative Fehler für das Rechteck in der Höhe erlaubt% ist, die Boolesche Wert, den wir berechnen müssen, ist:

| green.height - red.height |/green.height > 0.30 

Wenn über dem Wert true ist, dann geht die Fehlerbedingung (2) aus. Wir können beenden und benachrichtigen.

Bezüglich andernfalls Zustände (3), unter der Annahme, dass die maximalen horizontalen relativen Fehler für das Rechteck des Offset erlaubt ist 15%, der Boolesche Wert, den wir berechnen müssen, ist:

| green.center.x - red.center.x |/green.width > 0.15 

Wenn über den Wert true ist , dann geht die Fehlerbedingung (3) aus. Wir können beenden und benachrichtigen.

Bezüglich andernfalls Zustand (4), unter der Annahme, dass die maximale vertikale relative Fehler für das Rechteck des Offset beträgt 20% erlaubt, der Boolesche Wert, den wir berechnen müssen, ist:

| green.center.y - red.center.y |/green.height > 0.20 

Wenn über dem Wert true ist , dann geht die Fehlerbedingung (4) aus. Wir können beenden und benachrichtigen.

Wenn mindestens eine fehlgeschlagene Bedingung ausgeht, schlägt der Vergleich fehl. Wenn keine Fehlerbedingung true ist, ist der Vergleich erfolgreich, das grüne und das rote Rechteck sind fast gleich.

Ich glaube, dass der obige Ansatz viele Vorteile hat, wie die Begründung für einzelne Aspekte des Vergleichs, sowie die Definition verschiedener Schwellenwerte für die fehlerhaften Bedingungen. Sie können die Schwellen auch nach Ihrem Geschmack einstellen. In extremen Fällen müssen jedoch möglicherweise mehr Parameter berücksichtigt werden.