Determine relevancy and relative position of two polygons, Data Structure & Algorithms

Assignment Help:

Comparison Techniques

There are several techniques for determining the relevancy and relative position of two polygons. Not all tests may be used with all hidden-surface algorithms, and some of the are not always conclusive. Sometimes we can use simple tests for many of the cases and resort to more costly tests only when all else fails. 

One technique that is often useful is called the minimax test or boxing test. This test checks if two polygons overlap. The test provides a quick method to determine if two polygons do not overlap. It surrounds each polygon with a box by finding its extents (minimum and maximum x and y coordinates) and then checks for the intersection for any two boxes in both the X and Y directions. If two boxes do not intersect, their corresponding polygons do not overlap. In such a case, no further testing of the edges of the polygons is required.

If the minimax test fails (two boxes intersect), the two polygons may or may not overlap, as shown in Figure 3.10. Each edge of one polygon is compared against all the edges of the other polygon to detect intersections. The minimax test can be applied first to any two edges to speed up this process.

The minimax test can be applied in the Z direction to check if there is no overlap in this direction. In all tests, finding the extents themselves is the most critical part of the test. Typically, this can be achieved by iterating through the list of vertex coordinates of each polygon and recording the largest and the smallest values for each coordinate.

 

1477_data structure.png


Related Discussions:- Determine relevancy and relative position of two polygons

Array-based representation of a binary tree, Assume a complete binary tree ...

Assume a complete binary tree T with n nodes where each node has an item (value). Label the nodes of the complete binary tree T from top to bottom & from left to right 0, 1, ..., n

Boar corloring, Board coloring , C/C++ Programming

Board coloring , C/C++ Programming

EM13845162, Do you have a library solution for this problem?

Do you have a library solution for this problem?

Explain cam software, Explain CAM software CAD/CAM software has been re...

Explain CAM software CAD/CAM software has been recognized as an essential tool in the designing and manufacturing of a product due to its ability to depict the designs and tool

Sorted list using binary search technique, Write an algorithm for searching...

Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Program for binary search, Illustrates the program for Binary Search. P...

Illustrates the program for Binary Search. Program: Binary Search /*Header Files*/ #include #include /*Functions*/ void binary_search(int array[ ], int value,

In order post order, illlustraate the construction of tree of a binary tree...

illlustraate the construction of tree of a binary tree given its in order and post order transversal

State the output of avaerage value of numbers, Draw trace table and determi...

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

Adjacency list representation, Adjacency list representation An Adjacen...

Adjacency list representation An Adjacency list representation of Graph G = {V, E} contains an array of adjacency lists mentioned by adj of V list. For each of the vertex u?V,

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