2013-12-24 12 views
7

Ich arbeite ein Projekt, das, gegeben eine bestimmte Breite und Länge Koordinate, die Nachbarschaft ausgibt, dass der Punkt residiert. Ich habe die Breiten- und Längenkoordinaten, die machen die Grenzen mehrerer Stadtteile innerhalb einer Stadt. Ich muss die Nachbarschaftsdaten aus einer Datei lesen und auch die Testpunkte aus einer Datei lesen. Ich verwende die Racket-Programmiersprache.Wie finde ich einen Punkt innerhalb eines Polygons mit Racket

Bis jetzt konnte ich die Dateien lesen und eine Liste von Punkten für jede Nachbarschaft erstellen, und jetzt bin ich fest. Ich wollte ein Polygon für jede Nachbarschaft erstellen und dann eine Methode verwenden, die überprüft, ob ein Punkt innerhalb dieses Polygons liegt. Ich kann jedoch nicht herausfinden, wie man das mit Racket macht.

Kann mir jemand helfen, herauszufinden, wie man löst, wenn ein Punkt innerhalb dieses Vielecks ist, oder vielleicht ein besserer Weg, um das Problem zu lösen?

+1

Ist es ein konvexes oder ein konkaves Polygon? Oder ist es nur ein einfaches Rechteck? –

+0

Sie sind alle konkave Polygone, tut mir leid, ich habe nicht einmal daran gedacht. – AdamMc331

Antwort

9

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:

Some vectors

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.

+0

Das ist ausgezeichnet, vielen Dank. Ich werde das nach den Ferien genauer unter die Lupe nehmen, aber ich verstehe die Tests und habe einen Plan. Zur Veranschaulichung, hier ist ein Bild der Nieghborhood-Karte, um Ihnen die Arten von Formen zu zeigen, mit denen ich arbeiten werde. http://imgur.com/eZRa1fD – AdamMc331

+0

Sie müssen die Poligons in konvexe aufteilen, damit dies funktioniert. Sie können ein Dreiecksnetz verwenden. –

Verwandte Themen