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

Test whether a binary tree is a binary search tree, Q. Write down an algori...

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

Algorithm, Write an algorithm for compound interest.

Write an algorithm for compound interest.

Queues, what is the difference between data type and abstract data type

what is the difference between data type and abstract data type

Depth-First Traversal, With the help of a program and a numerical example e...

With the help of a program and a numerical example explain the Depth First Traversal of a tree.

Arrays, This unit discussed about data structure called Arrays. The easiest...

This unit discussed about data structure called Arrays. The easiest form of array is a one-dimensional array which may be described as a finite ordered set of homogeneous elements

Binary search tree, A binary search tree (BST), which may sometimes also be...

A binary search tree (BST), which may sometimes also be named a sorted or ordered binary tree, is an edge based binary tree data structure which has the following functionalities:

Disadvantages of the lifo costing method, The disadvantages or limitations ...

The disadvantages or limitations of the last in first out costing method are: The election of last in first out for income tax purposes is binding for all subsequent yea

Explain the term - branching, Explain the term - Branching There are t...

Explain the term - Branching There are two common ways of branching: case of ..... otherwise ...... endcase  if ..... then ..... else ..... endif   case of

Illustrate trivariate colour models, Illustrate Trivariate Colour Models ...

Illustrate Trivariate Colour Models Conventional colour models based on the tristimulus theory all contain three variables and so are called trivariate models. Let us now consi

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