Main Branches Of Computational Geometry

There are two main branches of computational geometry:

1. Combinatorial Computational Geometry.

2. Numerical Computational Geometry.

Combinatorial Computational Geometry:

The main goal of this study is to develop effective algorithms that could solve problems in terms of the basic geometrical objects like polygons, points, line segments, polyhedral etc.

There are several problem classes under Computational. Geometry one of which is Boolean Operations on Polygons:

Boolean Operations on Polygons:

In simple words it is the collection of the Boolean Operations (AND, OR, NOT, XOR and others) that are operating on one or more sets of the polygons in Computer Graphics. That operations are used in the Computer Graphics, CAD and in ECAD, whether they are integrated circuit physical designs or just the verification soft wares.

Algorithms that have been developed so far are as follows:

1. Greiner–Hormann clipping algorithm.

2. Vatti clipping algorithm.

3. Sutherland–Hodgman algorithm (special case algorithm).

4. Weiler–Atherton clipping algorithm (special case algorithm).

Usage in the soft wares includes the algorithms for Boolean Operations on Polygons based upon the use of bitmaps, however, it have several drawbacks.

Boolean Operations on convex and monotone polygons are performed in linear time in the Algorithm.

USES:

Computer-aided design (CAD) is the use of computer systems (or workstations) to aid in the creation, modification, analysis, or optimization of a design.

Electronic design automation (EDA) also referred to as electronic computer-aided design (ECAD) is a category of software tools for designing electronic systems such as integrated circuits and printed circuit boards.

Algorithms:-

Greiner-Hormann algorithm:

The Greiner-Hormann algorithm is used in computer graphics for polygon clipping. It performs better than the Vatti clipping algorithm, but cannot handle degeneracies. It can process both self-intersecting and non-convex polygons. It can be trivially generalized to compute other Boolean operations on polygons, such as union and difference.

The algorithm is based on the definition of the 'inside' of a polygon based on the winding number. It considers regions with odd winding number to be inside the polygon; this is known as the even–odd rule. It takes two lists of polygons as input.

In its original form, the algorithm is divided into three phases:

· In the first phase, pairwise intersections between edges of the polygons are computed. Additional vertices are inserted into both polygons at the points of intersection; an intersection vertex holds a pointer to its counterpart in the other polygon.

· In the second phase, each intersection is marked as either an entry section or an exit intersection. This is accomplished by evaluating the even–odd rule at the first vertex, which allows you to know whether the first vertex is inside or outside the other polygon. Then, following the polygon's borders, the intersections are marked with alternating flags (the next intersection after an entry intersection must be an exit intersection).

· In the third phase, the result is generated. The algorithm starts at an unprocessed intersection and picks the direction of traversal based on the entry/exit flag: for an entry intersection it traverses forward, and for an exit intersection it traverses in reverse. Vertices are added to the result until the next intersection is found; the algorithm then switches to the corresponding intersection vertex in the other polygon and picks the traversal direction again using the same rule. If the next intersection has already been processed, the algorithm finishes the current component of the output and starts again from an unprocessed intersection. The output is complete when there are no more unprocessed intersections.

The algorithm is not restricted to polygons and can handle arbitrary parametric curves as segments, as long as there is a suitable pairwise intersection procedure.

A major shortcoming of the original Greiner–Hormann algorithm is the fact that it cannot handle degeneracies, such as common edges or intersections exactly at a vertex. The original paper suggests perturbing the vertices to remove them

Vatti clipping algorithm:-

The Vatti clipping algorithm is used in computer graphics. It allows clipping of any number of arbitrarily shaped subject polygons by any number of arbitrarily shaped clip polygons. Unlike the Sutherland–Hodgman and Weiler–Atherton polygon clipping algorithms, the Vatti algorithm does not restrict the types of polygons that can be used as subjects or clips. Even complex (self-intersecting) polygons, and polygons with holes can be processed. The algorithm is generally applicable only in 2D space.

Clipping is defined as the interaction of subject and clip polygons. While clipping usually involves finding the intersections (regions of overlap) of subject and clip polygons, clipping algorithms can also be applied with other boolean clipping operations: difference, where the clipping polygons remove overlapping regions from the subject; union, where clipping returns the regions covered by either subject or clip polygons, and; xor, where clipping returns the regions covered by either subject or clip polygons except where they are covered by both subject and clip polygons.

The Vatti algorithm involves processing both subject and clipping polygon edges in an orderly fashion, starting with the lowermost edges and working towards the top; this is conceptually similar to the Bentley–Ottmann algorithm. This sweep line approach divides the problem space by scanlines, imaginary horizontal lines that pass through every vertex of the participating polygons.

These scanlines outline scanbeams – the spaces between adjacent scanlines. These scanbeams are processed in turn, starting with the lowest scanbeam, with the algorithm adding points of intersection within these scanbeams into the solution polygons.

Sutherland–Hodgman algorithm:-

Save your time!
We can take care of your essay

• Proper editing and formatting
• Free revision, title page, and bibliography
• Flexible prices and money-back guarantee

Place Order

The Sutherland–Hodgman algorithm is used for clipping polygons. It works by extending each line of the convex clip polygon in turn and selecting only vertices from the subject polygon that are on the visible side.

The algorithm begins with an input list of all vertices in the subject polygon. Next, one side of the clip polygon is extended infinitely in both directions, and the path of the subject polygon is traversed. Vertices from the input list are inserted into an output list if they lie on the visible side of the extended clip polygon line, and new vertices are added to the output list where the subject polygon path crosses the extended clip polygon line.

This process is repeated iteratively for each clip polygon side, using the output list from one stage as the input list for the next. Once all sides of the clip polygon have been processed, the final generated list of vertices defines a new single polygon that is entirely visible. Note that if the subject polygon was concave at vertices outside the clipping polygon, the new polygon may have coincident (i.e., overlapping) edges – this is acceptable for rendering, but not for other applications such as computing shadows.

All steps for clipping concave polygon 'W' with a 5-sided convex polygon

The Weiler–Atherton algorithm overcomes this by returning a set of divided polygons, but is more complex and computationally more expensive, so Sutherland–Hodgman is used for many rendering applications. Sutherland–Hodgman can also be extended into 3D space by clipping the polygon paths based on the boundaries of planes defined by the viewing space.

Weiler–Atherton:

The Weiler–Atherton is a polygon-clipping algorithm. It is used in areas like computer graphics and games development where clipping of polygons is needed. It allows clipping of a subject or candidate polygon by an arbitrarily shaped clipping polygon/area/region.

It is generally applicable only in 2D. However, it can be used in 3D through visible surface determination and with improved efficiency through Z-ordering.

CONDITIONS:

Before being applied to a polygon, the algorithm requires several preconditions to be fulfilled:

· Candidate polygons need to be oriented clockwise.

· Candidate polygons should not be self-intersecting (i.e., re-entrant).

· The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes, after which merging of the polygons can be performed using a variant of the algorithm.

ALGORITHM:

Before being applied to a polygon, the algorithm requires several preconditions to be fulfilled:

· Candidate polygons need to be oriented clockwise.

· Candidate polygons should not be self-intersecting (i.e., re-entrant).

· The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes, after which merging of the polygons can be performed using a variant of the algorithm.

Given polygon A as the clipping region and polygon B as the subject polygon to be clipped, the algorithm consists of the following steps:

1. List the vertices of the clipping-region polygon A and those of the subject polygon B.

2. Label the listed vertices of subject polygon B as either inside or outside of clipping region A.

3. Find all the polygon intersections and insert them into both lists, linking the lists at the intersections.

4. Generate a list of 'inbound' intersections – the intersections where the vector from the intersection to the subsequent vertex of subject polygon B begins inside the clipping region.

5. Follow each intersection clockwise around the linked lists until the start position is found.

If there are no intersections then one of three conditions must be true:

1. A is inside B – return A for clipping, B for merging.

2. B is inside A – return B for clipping, A for merging.

3. A and B do not overlap – return None for clipping or A & B for merging.

CONCLUSION:-

One or more concave polygons may produce more than one intersecting polygon. Convex polygons will only have one intersecting polygon.

The same algorithm can be used for merging two polygons by starting at the outbound intersections rather than the inbound ones. However this can produce counter-clockwise holes.

Some polygon combinations may be difficult to resolve, especially when holes are allowed.

Points very close to the edge of the other polygon may be considered as both in and out until their status can be confirmed after all the intersections have been found and verified; however, this increases the complexity.

Various strategies can be used to improve the speed of this labeling, and to avoid needing to proceed further. Care will be needed where the polygons share an edge.