Explain the method of overlapping and intersecting, Data Structure & Algorithms

Assignment Help:

Overlapping or Intersecting

A polygon overlaps or intersects the current background if any of its sides cuts the edges of the viewport as depicted at the top right corner of the viewport.

The extent of a polygon overlapping the viewport is only a necessary but not sufficient condition, because even if the extent overlaps, the polygon may be disjoint, as illustrated at the top left corner of the viewport. It may be seen that only the surrounding and contained cases (a) and (b) may be decided on the basis of the simple rules of relationship between the x-y extents of the polygon and the viewport. All other cases need further investigation, as follows : 

We start with the entire viewport, and examine all the polygons for surrounding or containment. Whatever polygons can be classified as Case (a) or Case (b) can be stored or not depending on whether they are visible or not.

For any remaining polygons, the viewport is divided into four quarters, and each quarter representing a viewport segment is evaluated against the polygon portions in that quarter for cases (a) and (b). The quarter or quarters in which such determination cannot be made will again be subdivided into four further quarters each, and each quarter (which may be termed a "viewport segment") examined for the same kind of relationship decisions.

This procedure is applied with successive subdivisions until all the polygons and sub-regions can be resolved as (a) or (b). Frequently, the procedure may have to be repeated until the last quartering reduces to a single pixel. Because of the four branches formed with each quartering step, the method is also called the Quad tree method. Finally, the method illustrates the difference between hidden-line and hidden-surface algorithms. In a particular viewport segment, it may happen that there are no edges at all, but two or more surfaces are surrounding the viewport segment. Here, hidden line has no relevance, but hidden surface has. 

 


Related Discussions:- Explain the method of overlapping and intersecting

Compound interest, Write the algorithm for compound interest

Write the algorithm for compound interest

Array and two-dimensional array, Q. Describe the term array.  How do we rep...

Q. Describe the term array.  How do we represent two-dimensional arrays in memory?  Explain how we calculate the address of an element in a two dimensional array.

Tree, application of threaded binary treee

application of threaded binary treee

Example which cause problems for hidden-surface algorithms, Example which c...

Example which cause problems for some hidden-surface algorithms Some special cases, which cause problems for some hidden-surface algorithms, are penetrating faces and cyclic ov

Binary tree, A binary tree is a tree data structures in which each node hav...

A binary tree is a tree data structures in which each node have at most two child nodes, generally distinguished as "right" and "left". Nodes with children are called parent nodes,

What do you understand by structured programming, What do you understand by...

What do you understand by structured programming Structured Programming  This term is used for programming design that emphasizes:- (1) Hierarchical design of programmi

Algorithm to delete node from binary search tree, Normal 0 fals...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Define big oh notation, Big oh notation (O) : The upper bound for the funct...

Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real

Recurrence relation, solve the following relation by recursive method: T(n...

solve the following relation by recursive method: T(n)=2T(n^1/2)+log n

Abstract data type-list, It is a useful tool for indicating the logical pro...

It is a useful tool for indicating the logical properties of data type. It is a collection of values & a set of operations on those values. Methodically, "a TYPE is a set, & elemen

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd