# Lat/Long grid points covered by projecting rectangle onto sphere

Before my question proper, a little background: I'm wanting to optimise some computer rendering by eliminating the drawing of things that aren't visible given the current view.

Suppose we have a sphere. Consider a grid of points on its surface, lying on longitude and latitude lines, equally divided around the sphere. (i.e. think of a grid of points, but instead of X and Y, we have longitude and latitude.) There are points at A unique longitudes and B unique latitudes, and therefore A(B - 2) + 2 points on the sphere.

Suppose your eye is positioned right at the centre of the sphere. Your eye has a looking 'through' a rectangular aperture with horizontal field of view M and vertical field of view N. It is looking at a point on the sphere of longitude G and latitude H (such that -90 <= H <= 90).

Which of the aforementioned points on the sphere are visible in this situation? Looking for a reasonably quick computation of this (i.e. runtime efficient).

(The harder part of this problem is the variance in latitude, rather than longitude -- for all intents and purposes, we could assume the eye is looking at longitude 0 if we want.)

-

First you solve the problem by any means at all, and then you see how to optimize the solution for computation. I can do the first part, and I’ll leave the second part to @occulus.

This is a simple problem in spherical trigonometry, once you look at it close enough, and I managed to find a kind of a solution by that method. But since @occulus seemed to want a criterion to decide whether a point on the sphere was or was not within the equiangular quadrilateral (not a rectangle!) that’s gotten by projecting the rectangular window onto the sphere from a point (the eye) at the center of the sphere, it seems to me that a nontrigonometric approach is called for.

The first first thing to observe is that we can always turn a (long,lat) pair of numbers into the Cartesian coordinates of a point in space, say at unit distance from the origin. So, if the $(0,0)$-point of the sphere is on the $x$-axis and the poles are on the $z$-axis, the Cartesian coordinates of $(\theta,\rho)$ are $(\sin\rho\cos\theta,\sin\rho\sin\theta,\cos\rho)$, where $\rho$ is the “colatitude”, namely $\pi/2-$ lat., and $\theta$ would be the longitude measured counterclockwise through the polar axis viewed from the north.

I’m assuming, though @occulus did not make it explicit, that the rectangular window is positioned so that its center is the closest point to the eye. Call the width of the rectangle $2w$, and the height $2h$, and suppose that it’s a distance of $d$ from the eye. Then the apparent half-width $\omega$ has $\tan\omega=w/d$, and the apparent half-height $\eta$ has $\tan\eta=h/d$.

Now let’s do as @occulus suggests, and put the center of the rectangle on the meridian of longitude $0$, I’ll call this great circle $g$ (for Greenwich), and suppose, as I think the poster does, that the rectangle is “level with respect to the equator”, so that its vertical axis of symmetry coincides with $g$. Let’s suppose also that the horizontal axis of symmetry of the rectangle crosses the meridian $g$ at the point of colatitude $\rho$. In the discussion that follows, I’m thinking of everything interesting happening in the northern hemisphere, and my own mental pictures are based on this, so that $0<\rho<\pi/2$. In the drawing below, I’m thinking of looking at the sphere from a point outside it, on the $x$-axis, so above the equator and the meridian $g$.

We have six great circles: the unlabeled horizontal axis of symmetry, the vertical axis of symmetry $g$, the “upper horizontal edge” $h_1$, the lower horizontal edge $h_2$, and the vertical edges $v_1$ and $v_2$. One sees that $h_1$ crosses $g$ orthogonally at colatitude $\rho-\eta$, and $h_2$ crosses similarly at colatitude $\rho+\eta$. The efficient way to describe a great circle is by its pole (there are actually two!). I’ll use $G=(0,1,0)$ as the pole of $g$, so that a point $P$ is on $g$ if and only if $P\cdot(0,1,0)=0$. And $P$ is to the left of $g$ if and only if the dot product is negative. Similarly, you see that the pole $H_1$ of $h_1$ has longitude $\pi$ and colatitude $\pi/2-\rho+\eta$, while the pole $H_2$ of $h_2$ is at long. $=\pi$, colat. $=\pi/2-\rho-\eta$. The corresponding Cartesian coordinates are $H_1=(\cos(\rho-\eta),0,-\sin(\rho-\eta))$, and of $H_2$ the same, with $\eta$ replaced by $-\eta$. So you see that for a point $P$ to be in our rectangle, it must at least have $P\cdot H_1\le0$, $P\cdot H_2\ge0$.

But what are the poles $V_1$ and $V_2$ of $v_1$ and $v_2$, respectively? You see that you get $v_2$ by rotating $g$ counterclockwise by an amount of $\omega$, only not with respect to the north pole, but with respect to the pole of the horizontal axis of symmetry, whose coordinates are just $(-\cos\rho,0,\sin\rho)$. If I did the computations correctly, we get $V_1=(\sin\omega\sin\rho,\cos\omega,-\sin\omega\cos\rho)$, and $V_2=(-\sin\omega\sin\rho,\cos\omega,\sin\omega\cos\rho)$. Then the remaining inequalities are $P\cdot V_1\ge0$, $P\cdot V_2\le0$. The simultaneous satisfaction of the four inequalities should be equivalent to $P$ being visible through the window.

-
Hi Lubin, thanks for your reply, going to have a close look at it when I get time (I've only just noticed your answer now!) – occulus Jan 23 '13 at 12:08

Here is one way to do it, in general terms.

Think of the rectangular viewport as having four 3-dimensional arcs instead of four lines on a side, each arc is on the sphere's surface, and each arc is on the great circle between endpoints of the viewing rectangle, or viewport.

If the width of the viewport is h degrees at the equator, take an arc of h degrees at the equator and rotate it up (or down) to the top of the viewport, rotating it about a line through the center of the sphere and parallel to the endpoints of the arc. Do the same for the bottom of the viewpoint.

The rotated arcs make up the top and bottom of the viewport on the surface of the sphere, and lie on the great circle between the points. The left side of the viewport lies along the great circle connecting the left endpoints of the arcs, right side lies along the great circle connecting the right endpoints of the arcs.

Find the intersection of each of the longitudinal grid lines with the top and bottom arcs, and then select the grid points along the grid line that lie in between the arcs. Then do the same for the great circle arcs on the sides of the viewport.

Grid points that lie on both the vertical and horizontal grid lines are inside the viewport. (It may be possible to shortcut this part.)

-
Hi xpda, thanks for your answer. When you say "Find the intersection of each of the longitudinal grid lines with the top and bottom arcs", do you mean "latitudinal" instead of longitudinal? – occulus Dec 20 '11 at 11:45
Your general approach sounds correct, but the problem is doing how to do it efficiently while taking into the account the curvature when the north and south poles are in view - where entire loops (whole great lines) of latitude may be within view. – occulus Dec 20 '11 at 16:47