Many questions have been raised about what the odd collection of if-then-elses means for PM1_Check and its counterpart SHARE_PM12_Vertex in Samet 229-230. I hope this manages to help those of you who are having difficulty with his algorithm interpret the psuedocode with greater ease. Read this at your own peril, though.

I have divided it into the 7 cases the code shows, and I try to give an English explanation of what is being done in each, followed by further comments in parentheses.

Remember you start the PM1_Check with a square representing a quadrant and a quadrant’s data dictionary (the q-edges present in the quadrant plus the q-edge you are adding into the quadrant if it intersects this quadrant). What occurs outside this quadrant is not important at this level.

The code uses true to signify that the PM1_check has determined that the quadrant is valid for a PM1. False is used to indicate invalid quadrants (quadrants that must be split).

1) When the quadrant is empty…
    THEN: true
(If you have nothing in a quadrant, you don't need to split it.)

else…
2) When the quadrant's data dictionary's first q-edge is an isolated vertex…
    THEN: If it is the only q-edge in the data dictionary --> true
                Else --> false
(If you have an isolated vertex in your data dictionary [stored as A <-> A for instance] then it must be the only vertex in your dictionary)

else…
3) When there is only one q-edge in the quadrant's data dictionary…
    THEN: If both vertices of the q-edge are inside the quadrant --> false
                Else --> true
(If you have a single q-edge, the only problem you face is the case where the vertices reside in the same quadrant. The other cases [either no vertices in the quadrant or only one vertex in the quadrant] are fine.)
(Here we have the three basic cases represented. Case A. is when two vertices of the only q-edge are in the quadrant. This is a failure case. The other two are where one vertex is in the quadrant (B.) and neither vertex of the q-edge is in the quadtree (C.).
A.                             B.                             C.

else…
4) When the quadrant's data dictionary's first q-edge has both endpoints (vertices) inside this quadrant…
    THEN: false
(As before, this case is a failure because you can only have vertex per quadrant. The reason we include this case even though it seems handled in the prior case is because that was for the situation when there is only one q-edge in the data dictionary. This covers the cases when there are more than one q-edges in the data dictionary.)
else…

5) When the quadrant's data dictionary's first q-edge has its vertex designated P1 in this quadrant...
    THEN: Check to see that every other q-edge in the data dictionary shares vertex designated P1. (by calling Share_PM12... on the next q-edge in the data dictionary)

else…
6) When the quadrant's data dictionary's first q-edge has its vertex designated P2 in this quadrant…
    THEN: Check to see that every other q-edge in the data dictionary shares vertex designated P2. (by calling Share_PM12... on the next q-edge in the data dictionary)

else…
7) When the quadrant's data dictionary's first q-edge has neither vertex in this quadrant (this is the only possibility left since all the others have been exhausted)…
    THEN: false
(This is always false because if you have a q-edge in a quadrant that does not have either vertex in the quadrant it must be the only q-edge present. We would only reach this case if we have more than one q-edge because of the if statement labelled 3))

The return command is divided as follows into if-then-else cases. When you move down from 1 - 7, cases in previous lines are no longer possible (that's why we passed by them). It might seem like a small vertex, but it is critical to understanding what is happening.
So after case 1) is passed there must be something in the quadrant
After case 2) is passed there is not an isolated vertex in the quadrant
After case 3) is passed there is more than one q-edge in the quadrant’s data dictionary
After case 4) is passed the first q-edge has less than two vertices inside this quadrant
After case 5) is passed the "first" vertex of the first q-edge is not in the quadrant
After case 6) is passed the "second" vertex of the first q-edge is not in the quadrant
This leads to case 7), which is always invalid (as explained in that case above)

Share_PM12_Vertex:

The purpose of this function is to tell whether or not a vertex in a quadrant is shared by all q-edges in the quadrant’s data dictionary. If it is, then true is returned. If it is not, then false is returned. True and false mean valid and invalid respectively as before.

It might seem odd that in the PM1_Check we only look at the first q-edge of the data dictionary, which seems to be an arbitrarily chosen q-edge. This is because there are only two cases that need to look at all the q-edges. These cases call the Share_PM12_Vertex. When we call Share_PM12_Vertex the situation is as follows:

We know that the first q-edge in this quadrant’s data dictionary has only one of its vertices in this quadrant. In order to be a valid PM1 quadrant, every other q-edge must share that same vertex.

Some specific examples might help in understanding this.

Below CASE I shows a valid quadrant. The q-edge labeled A was the first q-edge in the data dictionary, and its P2 is in the quadrant. As we run Share_PM12_Vertex on every other q-edge in the data dictionary, we see they all have an endpoint at P2 and none of them has another endpoint that is also in the quadrant.

CASE II shows an invalid quadrant. The q-edge labeled B was the first q-edge in the data dictionary, and its P1 is in the quadrant. As we run Share_PM12_Vertex on every other q-edge in the data dictionary, we see that one q-edge (labeled C) does not share this vertex as an endpoint. Therefore we return false and must split the quadrant.

CASE III shows an invalid quadrant. The q-edge labeled D was the first q-edge in the data dictionary, and its P1 is in the quadrant. As we run Share_PM12_Vertex on every other q-edge in the data dictionary, we see that one q-edge (labeled E) shares a vertex, but also has its other endpoint in this quadrant which is a violation of the PM1 quadtree rules. Therefore we return false and must split the quadrant.

CASE I                              CASE II                             CASE III

This function has four cases and takes in not only a quadrant/square and a data dictionary, but the vertex that is supposed to be shared.

1) If there are no more q-edges in the data dictionary…
    THEN: true
(if you get this far and there have been no problems, there ain't going to be any problems)

else...
2) The shared vertex equals the first vertex of the current q-edge of interest in the data dictionary…
    THEN: make sure the second vertex of the current q-edge is not in the quadrant too, and call Share_PM12... on the same shared vertex, same square, but the next q-edge of the data dictionary

else...
3) The shared vertex equals the second vertex of the current q-edge of interest in the data dictionary…
    THEN: make sure the first vertex of the current q-edge is not in the quadrant too, and call Share_PM12... on the same shared vertex, same square, but the next q-edge of the data dictionary

else...
4) Otherwise…
    THEN: false
(This happens when the current q-edge doesn't share one of its vertices with the passed in vertex. This violates the PM1 quadtree rules).