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

Tree traversals, There are three kinds of tree traversals, namely, Postorde...

There are three kinds of tree traversals, namely, Postorder , Preorder and Inorder. Preorder traversal: Each of nodes is visited before its children are visited; first the roo

The number of different directed trees with 3 nodes, The number of differen...

The number of different directed trees with 3 nodes are ?? The number of disimilar directed trees with three nodes are 3

Program to implementing stack using linked lists, include include i...

include include include /* Definition of structure node */ typedef struct node { int data; struct node *next; } ; /* Definition of push function */

Write an algorithm outputs number of books using psuedocode, A shop sells b...

A shop sells books, maps and magazines. Every item is identified by a unique 4 - digit code. All books have a code starting with a 1, all maps have a code which starts with a 2 and

Explain the memory function method, Explain the Memory Function method ...

Explain the Memory Function method The Memory Function method seeks to combine strengths of the top  down and bottom-up approaches  to  solving  problems  with  overlapping  su

Compound interest, Write the algorithm for compound interest

Write the algorithm for compound interest

Explain the bubble sort algorithm, Explain the bubble sort algorithm. ...

Explain the bubble sort algorithm. Answer This algorithm is used for sorting a list. It makes use of a temporary variable for swapping. It compares two numbers at an insta

Write stream analogues of list processing functions, (a) Write (delay ) as...

(a) Write (delay ) as a special form for (lambda () ) and (force ), as discussed in class. (b) Write (stream-cons x y) as a special form, as discussed in class. (c) Write

Define the internal path length, Define the Internal Path Length The In...

Define the Internal Path Length The Internal Path Length I of an extended binary tree is explained as the sum of the lengths of the paths taken over all internal nodes- from th

Write Your Message!

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