Unknown mathematical symbols

Question

First of all, pardon my ignorance.

I've searched long and hard to decipher these symbols, got to a point I thought to understand them but the implementation gives me unexpected results.

In a paper I found this function (excerpt from source):

intersect(P1,P2,Q1,Q2,alphaP,alphaQ)
  WEC_P1 = <P1 - Q1 | (Q2 - Q1)⊥>
  WEC_P2 = <P2 - Q1 | (Q2 - Q1)⊥>
  if (WEC_P1*WEC_P2 <= 0)
    WEC_Q1 = <Q1 - P1 | (P2 - P1)⊥>
    WEC_Q2 = <Q2 - P1 | (P2 - P1)⊥>
    if (WEC_Q1*WEC_Q2 <= 0)
      alphaP = WEC_P1/(WEC_P1 - WEC_P2)
      alphaQ = WEC_Q1/(WEC_Q1 - WEC_Q2)
    return (1); exit
  end if
end if
return (0)
end intersect

As a non-mathematician I didn't know what WEC stands for, but it's pretty easy to find out it stands for Window-Edge-Coordinate (GUESS 1). I didn't know what <u|v> means, wolfram-alpha says it is the dot product (GUESS 2):

<u|v> := u.x * v.x + u.y * v.y

I don't know what the upside-down T (⊥) is. An online search lead me to believe it is the perpendicular (\perp) symbol. The perpendicular vector is in my understanding the non-normalized normal vector, just the same but magnitude is not 1 (GUESS 3):

$$\begin{pmatrix} x \\\ y \end{pmatrix}⊥ = \begin{pmatrix} -y \\\ x \end{pmatrix}$$

I've already implemented a simple clipping algorithm where the determinant is computed up-front and checked to be greater than zero (to prevent a potential division by zero).

Now what I see in the above intersect() function is that the determinant is never computed. But as a computer scientist I understand that it is implicit, there's no way it gets actually thrown out of the window. And to avoid divisions by zero there are two if(), like this one (GUESS 4):

if (WEC_P1*WEC_P2 <= 0)
    WEC_Q1 = <Q1 - P1 | (P2 - P1)⊥>
    WEC_Q2 = <Q2 - P1 | (P2 - P1)⊥>

What I tried to do was take the simple clipping algorithm (which I understand thoroughly, computing determinant, alphas and using standard vector representations), GUESS 1-4 and implement the pseudo-code above in C#.

Through comparison (mutatis mutandis) I got the the following implementation:

public static bool AlphaClip(Vertex p1, Vertex p2, Vertex q1, Vertex q2, out float alphaP, out float alphaQ)
{
    float WEC_P1, WEC_P2, WEC_Q1, WEC_Q2;

    WEC_P1 = (p1.y - q1.y) * (q2.x - q1.x) - (p1.x - q1.x) * (q2.y - q1.y);
    WEC_P2 = (p2.y - q1.y) * (q2.x - q1.x) - (p2.x - q1.x) * (q2.y - q1.y);

    if (WEC_P1 * WEC_P2 <= 0f)
    {
        WEC_Q1 = (q1.y - p1.y) * (p2.x - p1.x) - (q1.x - p1.x) * (p2.y - p1.y);
        WEC_Q2 = (q2.y - p1.y) * (p2.x - p1.x) - (q2.x - p1.x) * (p2.y - p1.y);
        if (WEC_Q1 * WEC_Q2 <= 0f)
        {
            alphaP = WEC_P1 / (WEC_P1 - WEC_P2); // <--
            alphaQ = WEC_Q1 / (WEC_Q1 - WEC_Q2);

            return true;
        }
    }

    alphaP = 0f; // implemetation artifact, can be ignored
    alphaQ = 0f;

    return false;
}

Through testing I know for a fact that it works, almost.

The problem is this: under circumstances (on edge cases) alphaP turns out to be NaN because WEC_P1 and WEC_P1 - WEC_p2 are zero (at the line with the <-- comment.

I thought the if (WEC_P1 * WEC_P2 <= 0f) would protected against this, being the equivalent of checking that the determinant is greater than zero.

I thought it may require a stricter condition (< instead of <=) but I don't really know what the WECs signify, they are too far removed from my vector/matrix comprehension, and reading about them doesn't help at all. I've found them only here (page 8, slides) in the Liang-Barsky algorithm, but these slides and the Liang-Barsky itself is insufficient to gain insight at the level required to debug the code.

My real suspicion is that I didn't understand correctly the meaning of the pseudo-code and my implementation is simply wrong. Something is missing. Maybe a sign is inverted or the WECs are computed wrong.

I'm shrugging my head over this for three days now, what is wrong?

Answer 1

Short answer: relevant excerpt from the paper

So far, we tacitly assumed that there are no degeneracies, i.e.,
each vertex of one polygon does not lie on an edge of the other
polygon

Right after that they describe a way to detect degeneracies, to which I'll add some amendment: their solution only handles three collinear points, but not four. Maybe that particular case is handled in some other way, but I don't feel like reading the whole thing. But as a standalone, that pseudo-code doesn't handle every cases.

---

The long version

I'm not familiar with the expression WEC, but guess 1 is reasonable, guess 2 and 3 are fine, guess 4 is wrong. I'm basing this judgement on the computation of these window edge coordinates.

A necessary, but not sufficient, condition for (line) segment $\overline{P_1P_2}$ to intersect segment $\overline{Q_1Q_2}$, is that segment $\overline{P_1P_2}$ must intersect the (infinite) line $(Q_1Q_2)$. To figure that out, you can pick one point of line $(Q_1Q_2)$, say $Q_1$, and a normal vector of the line, say $\vec n= (Q_2-Q_1)^\perp$. Then $\text{WEC}(P) = \langle P-Q_1|\vec n\rangle$.

For any point $P\in\mathbb R^2$, its WEC can be interpreted as how far "above" or "below" it is from line $(Q_1Q_2)$, based on the direction of $\vec n$. In particular you have \begin{align*} (Q_1Q_2) &= \left\{ P\in\mathbb R^2 : \langle P-Q_1| \vec n\rangle = 0 \right\} \\ \mathscr H_+(\vec n) &= \left\{ P\in\mathbb R^2 : \langle P-Q_1| \vec n\rangle > 0 \right\} \\ \mathscr H_-(\vec n) &= \left\{ P\in\mathbb R^2 : \langle P-Q_1| \vec n\rangle < 0 \right\} \end{align*} where $\mathscr H_+(\vec n)$ is the half-space above $(Q_1Q_2)$, and $\mathscr H_-(\vec n)$ is below.

With that said, the condition WEC_P1*WEC_P2 <= 0 is equivalent to either

• $P_1$ and $P_2$ are on either sides of line $(Q_1Q_2)$, when both WEC_P1 and WEC_P2 are non-zero, or
• $P_1$ and/or $P_2$ belongs to the line $(Q_1Q_2)$, when WEC_P1 and/or WEC_P2 is zero.

If you change the test to a strict inequality, it will solve your NaN problem, but your code won't detect every type of segment intersection.

If WEC_P1-WEC_P2 is non-zero, this means line $(P_1P_2)$ is not parallel to $(Q_1Q_2)$, which in turn implies that WEC_Q1-WEC_Q2 is non-zero. In this case, you can safely compute alphaP and alphaQ without triggering NaN.

If WEC_P1-WEC_P2 is zero, then the two lines are parallel and you either have:

• the two lines are distinct, the intersection is empty and alphaP/Q is +/-inf,
• the two lines are identical, but the intersection is empty,
• the two lines are identical, and the segments intersect in exactly one point, which is a shared vertex,
• the two lines are identical, the intersection is itself a segment, and contains infinitely many points.

For the three last cases, you have WEC_P1 = WEC_P2 = WEC_Q1 = WEC_Q2 = 0, and alphaP/Q is NaN. If those three cases are of no importance for you, you can just check for NaN (or test four equalities) and be done with it. Otherwise, you need to add a new conditional branch, and compute a new measure to distinguish the 3 cases. (Say, something like $\text{Not-Really-A-WEC} (M) = \langle M-P_1\mid P_2-P_1\rangle$.)

Answer 2

I don't see $\perp$ anywhere in that equation. Properly typeset it becomes $\langle u|v\rangle := u_x v_x + u_y v_y$, the LaTeX being \langle u|v\rangle := u_x v_x + u_y v_y. The $=$ sign has picked up a colon to mean "is defined as", so the expression is a definition, not a claim about the relationship between previously defined things. The left-hand side is certainly not the high-school $u\cdot v$ notation for a dot product, but it is the usual dot product. it's bra-ket notation, for a general inner product.