Patterns of Visitation
The unoptimized visit function uflood tends to require more storage than the optimized version flood. Using the Turbo C small memory model and an EGA display, during test 4 uflood actually runs out of storage space and terminates abruptly. The lower storage requirements of flood clearly have something to do with the fact that entire rows are processed at once, but there is more going on here than meets the eye. The manner in which flood chooses rows to visit also has a great influence.
Shadows get onto the pending list when child lines cast shadows. If child lines cast shadows on both sides of a row, then which row is visited next depends on the last shadow cast. If shadows are cast on only one side, that row will be visited next. If no shadows are cast, visiting has reached a dead end and will jump to the row of whatever shadow is at the head of the pending list.
When shadows are cast on both sides of a row, after the next row is chosen shadows on the other row remain on the pending list. They stay there until visiting either reaches a dead end or sweeps by their row while proceeding around an island in another part of the region. Which shadow will be at the head of the list when a dead end is reached?
flood makes this answer essentially unpredictable by reversing the relative order of shadows remaining in the pending list each time a row is selected. It is this characteristic that makes it possible for a child to have parent lines on both sides, because visiting can jump from one side of a pending shadow to the other without passing through its row.
Say, instead, that the relative order of shadows remaining in the pending list is maintained instead of reversed. After reaching a dead end, visiting will revert to the most recent row remaining in the pending list (more precisely, to the row that was not selected after the last time shadows were cast on both sides of a row). This prevents visiting from jumping from one side of a pending shadow to the other.
This leads to code simplification because overlapped shadows would then be found only at the head of the row and pending lists. Immediately upon detection overlapped shadows could be placed on the free list — the validity flags would no longer be necessary. These effects can be achieved in other ways, of course, but the possibility that the overlapped shadow is not at the head of its list makes the process somewhat messy. (The time savings are not great, but the quick placement of nodes on the free list leads to significant reductions in storage requirements for some complex regions.)
It turns out that maintaining relative order in the pending list is not a good thing to do. While with simple regions involving only a few islands there is little or no difference, as regions grow more complex the number of shadows in the pending list can increase enormously.
In test 4, for example, rows on the far side of islands cast shadows on both sides. The shadows cast onto islands (on the same side as the parents of the child lines) are all dead ends. If the last child on the row casts a shadow on an island, it will be detected immediately and the next row selected will contain all of the shadows cast away from the islands (on the side opposite the parents of the child lines). But if the last child casts only a shadow away from the islands, the shadows falling on islands remain in the pending list until visiting reaches the dead end at the bottom of the screen. With an EGA display, eventually over 400 shadows are in the pending list. Not only space but also time spent manipulating the pending list is increased.
The difference caused by reversing instead of maintaining the relative order of shadows in the pending list shows up whenever shadows cast on islands are discovered to be dead ends. List rearrangement means that the next row selected might not be the most recent one added to the list, but instead one from an earlier point. Because the shadows on such a row are usually dead ends themselves, they are removed from the pending list but not replaced. The net overall effect is to keep the pending list shorter than when maintaining relative order.
When maintaining relative order, test 6 also experiences a dramatic increase in the number of shadows required, to over 400. Test 8 has a moderate increase, to over 100. The random patterns of test 9 require about 50 shadows on average.
These results indicate that the code simplifications possible by maintaining the relative order of shadows in the pending list are not worth the increases in time and space required. Nearly all shadows that overlap lines are found to be at the head of the row and pending lists as it is. The few that are not are fairly easy to handle with simple loops and flags.
The code simplifications outlined above remain attractive, however. If another simple method could be found to guarantee that a child line never has parent lines on both sides of it, they may be achievable.
