Ist ein Punkt innerhalb oder außerhalb eines Polygons, der sich auf der Oberfläche eines Globus befindet?

Question

Wie kann ich feststellen, ob ein Punkt innerhalb oder außerhalb eines Polygons liegt, das auf der Erdoberfläche liegt?

Das Innere des Polygons kann über die rechte Handregel bestimmt werden, dh. Die Innenseite des Polygons befindet sich auf Ihrer rechten Seite, wenn Sie um das Polygon herumgehen.

Das Polygon kann

1. Kreis entweder pole
2. Kreuz die 180 Längen-
3. decken mehr als 50% des Erdballs

Da die Kugel eine Kugel crossing die Normalstrahl ist Algorithmen funktionieren nicht richtig.

Answer 1

Tatsächlich funktionieren die normalen Raytracing- und Wicklungsregelansätze mit einer kleinen Anpassung auf der Oberfläche einer Kugel gut.

Auf der Oberfläche einer Kugel ist eine "gerade Linie" ein großer Kreis und Entfernungen werden in Winkeleinheiten statt in Metern oder Zoll gemessen. Um einen Strahl von einem willkürlichen Punkt auf der Oberfläche der Kugel zu zeichnen, bilden Sie einfach einen großen Kreis durch diesen willkürlichen Punkt und irgendeinen anderen Punkt auf der Oberfläche der Kugel. Um die Mathematik sauber zu halten, wählen Sie einen zweiten Punkt über pi/2 weg von dem Punkt, an dem Sie gerade testen. Wenden Sie die übliche gerade-ungerade Regel auf den Großkreis und Ihr Testpolygon an.

Die Winderegel übersetzt sich auch direkt von geraden Linien in der Ebene zu (Segmenten von) Großkreisen auf einer Kugel.

Sie benötigen jetzt nur Java-Implementierungen von grundlegenden sphärischen Geometrieoperationen. Ich habe diesbezüglich keine Empfehlungen, aber ich denke, das Internet wird helfen. Für die Mathematik starten Sie mit Mathworld. Ein anderer Ansatz wäre, Ihre Punkte und Polygone von der Oberfläche der Kugel auf die Ebene zu projizieren - was die Kartenprojektionen tun - die topologische Beziehung der Innerlichkeit wird durch eine solche Transformation nicht beeinflusst.

Oh, und Sie haben zu entscheiden, was zu tun ist, wenn Ihr Polygon einen großen Kreis beschreibt

Answer 2

Verwenden Sie Ebenen statt Strahlen. Eine "Linie" auf der Oberfläche einer durch zwei Punkte definierten Kugel ist ein Bogen eines großen Kreises (Kreis, dessen Mittelpunkt der Mittelpunkt der Kugel ist) und ist auch in einer Ebene enthalten, die diese zwei Punkte und das Zentrum der Kugel enthält .

Testen Sie, ob der Punkt "größer" oder "kleiner" als die entsprechende Ebene für jede Kante des "Polygons" ist, um zu bestimmen, auf welcher Seite der "Linie" er sich befindet.