Greiner-Hormann clipping with degeneracies

问题:

I'm trying to understand the paper "Clipping of Arbitrary Polygons with Degeneracies" by E. L Foster and J. R. Overfelt [1], which claims to extend the classic Greiner-Hormann polygon clipping algorithm by handling of degeneracies.

However, I ran into some difficulties with the procedure they describe. Consider the situation depicted on Figure 6(c) and suppose the polygons are oriented in the same way. Start the labeling phase from the I5 (as opposed from I1, as they do): for both subject polygon S and clipping polygon C, I5 has previous and next labels (on, on). Therefore, according to Table 1, first remove the intersection flag (1), then label current and neighbor nodes as "in/in" (2). This agrees with the Example. Next, I6 has (in/out) for S, and (in/on) for C. Table 1 says "en/en" (or "ex/ex", not clear whether "prev" applies to columns or rows). Then, Table 2 says, remove intersection "en/en" and label "in" (presumably "in/in") [2]. But the example states "ex/en", and not "in/in".

Please, can anyone explain to me why is this happening? How to arrive at "ex/en"? Does it really matter, where I start the labeling phase?

[1] https://github.com/erichlf/PolyClipping/blob/master/Paper/PolyClip.pdf
[2] They also say "the entry/exit flag is set to be equal to the previous node’s entry/exit flag" which by luck also happens to be "in/in" but it is not very clear how does the Table 2 relates to this rule.

回答1:

It appears that this is a mistake in the paper. Labeling based on Table 1 would first give ex/ex and then based on table 2 would produce out/out. The case where we go in->on or even ex->on is more complicated than the explanation in the paper.

What appears to work would be if the intersection is in->on check the neighbor and if the neighbor is not in->on then label the current as the opposite of the neighbor. So in the case of I6 we would label it as ex/en. Now if we had a case where both the neighbor and current were in->on we would want to check the next point in the sequence, i.e. I2 and S2. If both points in the sequence are on then remove this intersection and label as (in,in). Otherwise the label should be en if this next point is in and ex if the next point is out.

The case where we go from out->on would be the opposite.

I hope this answers your question.