I'm having trouble understanding the correctness of the following algorithm: why is the choice of the $p_n$ coordinates correct? Also, in figure 3.8 $n$ is pointing left and up, so according to figure 3.7 the vertex we should choose is the bottom right one (instead of the top left one), isn't that right?
also, I don't understand how can $n$ lie in 4 quadrants, can't he only point up-right (if the slope of the line is negative) and up-left (if the slope is positive), meaning there are only 2 possible quadrants?
My guess is that the objective of the problem is to decide whether the rectangle is crossed by a given line or lies entirely on one side of that line. In the latter case, it is desirable to know on which side of the line the rectangle lies.
You are probably confused because of figure 3.8, which seems to contain a mistake. Let us start with formulas (3.6) and (3.7) on page 35. The normal in figure 3.8 is drawn correctly. Its $x$ component is negative, so according to (3.6) $x_n = x_{max}$ . The normal's $y$ component is positive, so according to (3.7) $y_n = y_{min}$ . So $p_n = (x_n , y_n)$ is the corner of the rectangle with maximum $x$ and minimum $y$. That's the bottom-right corner of the rectangle. Opposite to that corner, $p_{-n}$ is the upper-left corner of the rectangle. In figure 3.8 it seems that $p_n$ and $p_{-n}$ are mistakenly swapped.
If we suppose that this mistake is corrected, we see that the rest makes sense. Let's read the paragraph under figure 3.8 again. The correct $p_n$ (bottom-right) is not in the positive half-plane made by the line. So we do not yet have enough evidence to judge where the rectangle lies with respect to the line. Now we go ahead and check an additional point, $p_{-n}$ (upper-left). We see that both $p_n$ and $p_{-n}$ are in the negative half-plane made by the line. Therefore we have enough evidence to judge that the rectangle is entirely in the negative half-plane made by the line.