Ich werde jetzt keinen Code posten, weil ich die Hausaufgaben nicht lösen will. Ich werde jedoch einige Hinweise veröffentlichen.
Schauen Sie sich das folgende Bild:
Wie können wir wissen, dass C
zwischen den Rändern ist OA
und OB
und D
draußen ist? Es ist einfach: Wir vergleichen einige Winkel: Wenn der Winkel zwischen OC
und OA
kleiner ist als der Winkel zwischen OB
und OA
dann ist C deutlich näher an OA
als OB
ist.
Nun, wie bekommen wir den Winkel, der nur einige Vektoren kennt? Wir können den Kosinus verwenden, der monoton ist: Er nimmt mit zunehmendem Argument ab. Somit ist der Kosinus des Winkels zwischen OC
und OA
größer als der Kosinus des Winkels zwischen OB
und OA
, der wiederum größer ist als der Kosinus des Winkels zwischen und OA
.
Der nächste Schritt ist herauszufinden, wie man den Kosinus berechnet. Das vektorielle Punktprodukt hilft: sein Wert ist Kosinus des Winkels mal größer als das Produkt der Operandenlängen. Das heißt:
cos(OC; OA) = dotproduct(OC; OA)/(length(OA) * length(OC))
Die dotproduct in 2D ist einfach:
dotproduct(OC; OA) = (C.x - O.x) * (A.x - O.x) + (C.x - O.x) * (A.x - O.x)
alle der oben genannt Sie Kombinieren soll einen einfachen Test müssen zu prüfen, ob die in der gleichen Situation wie C
ist oder als D
: näher an einer Kante als die vorherige Kante oder nicht.
Jetzt müssen Sie dies für jede Kante des Polygons wiederholen, und Sie sind fertig. Sie können dies mit einem fold
tun, wenn der Test ein Prädikat ist.
Hinweis: Dies funktioniert nur, wenn das Polygon konvex ist. Für ein konkaves Polygon müssen Sie weitere Tests hinzufügen.
Zweite Anmerkung: In der Figur, was passieren wird, wenn D
oder C
oder beide unter der Leitung OA
sind?Denken Sie darüber nach und prüfen Sie, ob es weitere Änderungen an der obigen Methode fold
bedeutet.
Letzte Anmerkung: In ein paar Wochen werde ich einen vollständigen Code dafür, vorausgesetzt, die Zuordnung ist vorbei. Außerdem werde ich zu der Zeit die Frage in der obigen Anmerkung beantworten.
Ist es ein konvexes oder ein konkaves Polygon? Oder ist es nur ein einfaches Rechteck? –
Sie sind alle konkave Polygone, tut mir leid, ich habe nicht einmal daran gedacht. – AdamMc331