Area- filling algorithm and other graphics processes
often need to identify interior regions of objects. So far, we have discussed
area filling only in terms of standard polygon shapes. In elementary geometry,
a polygon is usually defined as having no self intersections. Examples of
standard polygons include triangles, rectangles, octagons and decagons. The
component edges of these objects are joined only at the vertices, and otherwise
the edges have no common points in the plane. Identifying the interior regions
of standard polygons is generally a straightforward process.

Determining the inclusion of a point in a 2D planar
polygon is a geometric problem that results in interesting algorithms. Two
commonly used methods are:

1.

**The Crossing Number****(cn) method**: It is also called**odd-even rule**or**odd parity rule**or**odd rule**. We apply this method by conceptually drawing a line from any position**P**to a distant point outside the coordinate extents of the object and counting the number of edge crossings along the line. If the number of polygon edges crossed by this line is odd, then**P**is an**interior**point. Otherwise,**P**is an**exterior**point. To obtain an accurate edge count, we must be sure that the line path we choose does not intersect any polygon vertices.**The Winding Number**

**(wn)/ nonzero winding number rule method**: This method counts the number of times the polygon edges wind around a particular point in the counterclockwise direction. This count is called the winding number. Here instead of just counting the intersections, we have to give directions to each boundary line crossed and we have to sum these direction numbers. The direction number indicates the direction the polygon was drawn relative to the line segment we have constructed for the test. Let a point (x

_{a}, y

_{a}) is a test point and line y = y

_{a }is a horizontal line runs from outside the polygon to point (x

_{a}, y

_{a}). The polygon edges crossed by this line could be drawn in two ways. If the edge crosses the positive ray from below to above, the crossing is positive (+1); but if it crosses from above to below, the crossing is negative (-1). One then simply adds all crossing values to get wn. For polygons or two dimensional objects, the point is said to be inside when the value of winding number is nonzero.

If a polygon is simple (i.e. it has no self
intersections), then both methods give the same result for all points. But for
non-simple polygons, the two methods can give different answers for some
points.

__SCAN - LINE FILL OF CURVED BOUNDARY AREAS__

In generally, scan-line fill of regions with curved
boundaries more work than polygon filling, since intersection calculations now
involve nonlinear boundaries. For simple curves such as circles or ellipses,
performing a scan-line fill is a straightforward process. We only need to
calculate the two scan-line intersections on opposite sides of the curve. This
is the same as generating pixel positions along the curve boundary, and we can
do that with the midpoint method. Then we simply fill in the horizontal pixel
spans between the boundary points on opposite side of the curve. Symmetries
between quadrants are used to reduce the boundary calculations.

**Scan Filling Curved Objects**

## No comments:

## Post a Comment