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.)
 A: 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.
A: 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.)
