FARSITE can create very complex fire perimeters due to spotting, barriers, and fuel models with significantly different spread rates under the same conditions. Resolving these perimeters "bumping" into each other can demand the bulk of the computational resources available and easily bog down the simulation.
After a fire has burned for a given time step the fire perimeter is processed for crossovers. Crossovers are formed when locally concave portions of the fire perimeter intersect during a given time step (Sanderlin and Sunderson 1975, Richards 1990, Knight and Coleman 1993, Wallace 1993, Richards and Bryce 1995). This happens because the spread directions of points in a concavity are oriented inward; spread from unburned fuel to burned fuel is not automatically detected by the perimeter expansion algorithms. These crossovers must be removed to preserve the meaningful exterior portions of the fire front. Sometimes, an enclave or island is formed by a crossover. This represents a region of the perimeter in which the points are ordered in an opposite rotation. These enclaves essentially become separate fire fronts burning inward as a natural result of their orientation in Richards' (1990) differential equation.
Regardless of the methods chosen, the process of crossover removal is expensive in terms of time and computing power. A number of ways of removing illogical artifacts of the perimeter expansion have been proposed. Richards (1990) used a clipping strategy that excised the illogical portions of the fire perimeter from the fire polygon. Knight and Coleman (1993) and Wallace (1993) describe similar methods. Most recently, Richards and Bryce (1995) describe an algorithm that leaves intact the offending perimeter vertices but renders them inert. The methods described below are more similar to the clipping routines. This approach is used in FARSITE because it enables orderly storage of only meaningful fire perimeter information and facilitates export of fire polygons for GIS uses.
The algorithm used for clipping loops and crossovers in FARSITE versions 1.X, processes the order of segment crosses to find enclaves and correct the outer fire front.
Five examples of crossovers occurring along concave portions of a fire front. Enclaves are formed by crossovers in the last four configurations.
The simplest example is the first diagram in Figure 10.2. that involves crossing of segments 2 and 11 (identified by the first vertex on the span). If crosses are computed for each span with each other span on the fire perimeter, the number of crosses would be 2, resulting in the order of intersections listed below the diagram (segment 2 crosses segment 11, and segment 11 crosses with 2). Knowing the number of intersections to be 2, and finding the match between segment 2 as Span A for the first intersection and segment 2 as Span B for the second intersection, the algorithm would clip all points from 3 through 11, replacing them with the intersection point.
Other general types of crossovers have a pattern that is recognizable regardless of other crosses within the bounds of these intersections. Some of these are shown above. Enclaves are identified in each of these patterns and written to separate arrays as separate fires. These enclaves may still contain crossovers themselves and must be processed through the same algorithm to clean these perimeters. This process may again result in enclaves being divided to form separate inward burning perimeters.
A limitation of this technique involves the spread distance possible within any given time step. Too much spread relative to the resolution of the fire perimeter will produce a spaghetti-like fire front or create complex knots that cannot be resolved logically by the above algorithms. Hence the need for a dynamically adjustable distance check that depends on the average resolution of a given fire. This feature attempts to limit the spread so that the crossovers fall within the limits of complexity solvable by the algorithms.
A new algorithm was developed for version 2.0 to process crossovers on fire perimeters. It appears to more accurately determine enclaves. It is also tolerant of complex fire perimeter knots or "spaghetti ignitions" that are input by the user or arise naturally on complex landscapes.
The new algorithm corrects a fire polygon by following the outer edge starting from an extreme point. An extreme point is defined as one of the polygon vertices that is the farthest west, east, north, or south, and thus determines the bounding rectangle of the polygon. For an outward burning fire it proceeds with each perimeter segment (pair of vertices) counterclockwise until an intersection with another segment is encountered (clockwise if processing an inward fire). Vertices are written to a separate array containing the corrected fire polygon. If the process finds an intersection, the algorithm decides the rotation direction produced by the intersection with the new perimeter segment and whether the intersection produces a locally convex or concave region. These criteria are used to determine the next vertex to be processed (either in the original direction around the fire polygon or in the reverse direction). The intersection point is written as the next point on the new fire polygon. The process is continued until the algorithm arrives back at the starting point. This determines the vertices that now define the outermost fire perimeter.
After processing the vertices for the outermost fire polygon, the algorithm looks for perimeter segments that have crossed but not yet been processed. These will occur if an enclave is formed. If one of these intersections is found, the new intersection serves as the starting point for the same algorithm to again follow the edge of the fire polygon. This process determines if a new inward fire has been created within the original fire perimeter polygon (an enclave). Each enclave is written as a separate fire if it has more than 2 vertices and is oriented clockwise. This process is repeated until there are no more unprocessed crosses on the original fire perimeter polygon.
Searching for fire mergers is accomplished at the end of a time step after all fires have spread and crossovers removed. This is a computationally intensive process that first compares the bounding rectangles for each fire. If rectangles for two fires overlap, it examines within the overlapping region, segments of the first fire for intersections with those of the second fire.
As with crossovers, the intersection coordinates and average fire characteristics of the intersecting segments are stored, as well as the order of segments in each fire that cross.
Examples of fire mergers. Mergers "B" and "C" form enclaves and thus one outward burning fire and one that burns inward.
This information is used by one of two algorithms. If there are only 2 crosses between fires, then no enclaves can be formed and the simpler, faster algorithm merges these fires (diagram "A" in Figure 10.3). Merging fires with more than two intersections uses the comparatively complex algorithm to write segments alternately from each fire between intersection points. There can be only one outward burning fire perimeter, so all subsequent fire perimeters must be inward burning enclaves (diagrams "B" and "C" above).
The algorithms for merging fires will perform mergers between 1) two separate outward burning fire polygons, and 2) between an inward burning fire polygon and an outward burning polygon. The latter situation develops where spot fires are burning within an inward burning polygon (that defines the fire front around an enclave). The spot fires will burn as independent fires until they merge with each other or with the wall of the enveloping inward burning fire. No situation can logically develop where two inward burning fire polygons could merge.
The process of merging fires proceeds first with mergers among all outward burning fires, and then for mergers between enclaves and outward burning perimeters. This sequence eliminates illogical overlaps between outward burning fires that could influence how enclaves are processed when they contain spot fires.