Scan line

Search for valid area through the use of scan line

The process to search for the biggest area is done through the analysis of all possible candidate areas. These areas are defined according to the geometry and localization of defects. A defect that is located in the center of the coil generates four areas that can be analyzed: one at the left, other on the right, another on the upper part and last an area below the defect as shown in figure 1:

Figure 1: Valid areas existent according to the defect.

The search for biggest area consist of a scan line (SL) from left to right stopping at each beginning and end of each defect. During this process the routine maintain a set of valid areas (SVA) that are growing together with the SL.

The beginning and the end of the coil, as well as the beginning of each defect, are stop points to the SL. At the beginning of the algorithm the SL passes through the beginning of the coil and creates into the SVA an area that starts with the beginning of the coil width, assuming value zero, the end equals the total width of the coil and the beginning matching value zero, representing the beginning of the coil (it is being assumed that the superior left of the coil is the origin of the width and length counting). This area will stay valid into the SVA until if is found a defect that has any coordinate in between the initial width and the final width of the defect.

The SC is moved from the beginning of the coil to the left most possible position. As the SL was at the beginning of the coil than the next coordinate will be the beginning of a defect or the end of the coil (if there are no defect). In both cases the area existent into the SVA will be blocked, being compared with the biggest area already found by the algorithm. If it is bigger or if it does not exist an area already identified as the biggest than the current one becomes the bigger.

Each time the SL stop at the beginning of a defect than it is necessary to verify if all the areas into the SVA to verify which ones have intersection in the width with the defect being analyzed. The ones that intercept must be compared with the bigger area encountered, substituting it in the case it is bigger. After verifying the size of valid areas, it is necessary to insert into the SVA the new areas generated by the beginning of the defect found. These areas consist basically in two areas: one above the defect A and the other below B, as represented in figure 2.

Figure 2: Creation of valid areas based on the analysis of the beginning of defects.

Each time that the SL stop at the end of a defect, there is necessary to insert into the SVA the new valid areas generated by the end of the defect being considered. These areas consists basically in a superior area above the defect, an inferior area below the defect (this one can be joined with the superior in the case that there are no overlapping defects) and all the intermediary areas in case there are some overlapping defects. The figure C show the creation of four defect, one superior, one inferior and two intermediary generated because of the existence of overlapping defects.

Figure 3: Creation of valid areas based on the analysis of the end of defects.

At the end, it is necessary to verify if the biggest area found is sufficient to allocate the customer request. If so than return the area, if not return null.

I developed a tinny executable that I did to demonstrate the algorithm to search for valid areas by using scan line approach: Valid area by Scan Line

·Concepts· ·Objectives· ·Matrix· ·Scan line·