क्रोशे आकार : चौकोन

 [Enter Post Title Here]

Lecture 1

Contents:

·         Algorithm and Examples

·         Flowcharts and Examples

·          Importance of Indentation

·         Structured Programming

Algorithm:

Definition 1:

An algorithm is a well-ordered collection of unambiguous and effectively computable operations that when executed produces a result and halts in a finite amount of time

Definition 2:

A finite set of instructions having the following characteristics:

·         Precision: Steps are precisely stated.

·         Uniqueness: Results of each step uniquely defined.

·         Input:  Algorithm receives input.

·         Output: Algorithm produces output.

·         Generality: Algorithm applies to a set of inputs.

Characteristics of algorithms:

1.     Algorithms are well-ordered.

2.     Algorithms have unambiguous operations.

3.     Algorithms have effectively computable operations.

4.     Algorithms produce a result.

5.     Algorithms halt in a finite amount of time.

An Example Algorithm

Let’s look at a very simple algorithm called find_max().

Problem: Given a list of positive numbers, return the largest number on the list.

Inputs: A list L of positive numbers. This list must contain at least one number. (Asking for the largest number in a list of no numbers is not a meaningful question.)

Outputs: A number n, which will be the largest number of the list.

Algorithm:

1.       Set max to 0.

2.       For each number x in the list L, compare it to max. If x is larger, set max to x.

3.       max is now set to the largest number in the list.

An implementation in Python:

def find_max (L):

    max = 0

    for x in L:

        if x > max:

            max = x

    return max

Does this meet the criteria for being an algorithm?

·         Is it unambiguous? Yes. Each step of the algorithm consists of primitive operations, and translating each step into Python code is very easy.

·         Does it have defined inputs and outputs? Yes.

·         Is it guaranteed to terminate? Yes. The list L is of finite length, so after looking at every element of the list the algorithm will stop.

·         Does it produce the correct result? Yes. In a formal setting you would provide a careful proof of correctness. In the next section I’ll sketch a proof for an alternative solution to this problem.

Flowchart:

Flowcharting is a tool developed in the computer industry, for showing the steps involved in a process.

A flowchart is a diagram made up of boxes, diamonds and other shapes, connected by arrows - each shape represents a step in the process, and the arrows show the order in which they occur.

Flowcharting combines symbols and flowlines, to show figuratively the operation of an algorithm.

Flowcharting is the first step towards process understanding.

Flowcharting Symbols:

There are 6 basic symbols commonly used in flowcharting of assembly language

1.       Process

2.       Terminal,

3.        input/output,

4.       Decision,

5.        Connector and

6.       Predefined Process.

Process: Indicates any type of internal operation Inside the Processor or Memory  

Input/output: Used for any Input / Output (I/O) operation. Indicates

 that the computer is to obtain data or output results

Decision:  Used to ask a question that can be answered in a binary

format (Yes/No, True/False)

 

Connector:  Allows the flowchart to be drawn without

intersecting lines or without a reverse flow.

Predefined Process:  Used to invoke a subroutine or an interrupt program.

Terminal : Indicates the starting or ending of the

 program, process, or interrupt program.

 Flow Lines: Shows direction of flow.          

Importance of Indentation

Programming style and indentation can be defined as the way you follow to organize and document your source code. Code indentation is a part of style and it is more of aesthetic interest.  A proper code indentation will make it:

·         Easier to read

·         Easier to understand

·         Easier to modify

·         Easier to maintain

·         Easier to enhance

We refer the code again during

·         Reading an understanding the program

·         Code debugging

·         Adding new code to the existing program

·         Updating the existing program

Indentation:

Indentation is done with SPACES not TABS. SPACE is of fixed length in all types of system. But TAB is not of fixed length. The matching braces should be in the same column.

 Spacing:

It also makes the code more readable if properly maintained. So we should follow proper spacing throughout our coding and it should be consistent.

Following are some examples showing the usage of spacing in code indentation.

1.        Left parenthesis should start immediately after the method name.

// NOT Recommended

 Function   (i, j);

 // Recommended

Function (i, j); 

2.        All array names should be immediately followed by a left square bracket.

// NOT Recommended

         arr   [0];

// Recommended

         arr[0]; 

3.       All binary operators should maintain a space on either side of the operator.

                  // NOT Recommended

                                  a=b-c;         

  a = b-c;       

                                  a=b - c;       

            

               // Recommended

         a = b - c;     

 // NOT Recommended

                      z = 6*x + 9*y;        

                  // Recommended

                 z = 6 * x + 9 * y;    

                   z = (7 * x) + (9 * y);

  

4.       All unary operators should be written immediately before or after their operand.

    // NOT Recommended

    count ++;

                 // Recommended

                    count++;

5.        All commas and semicolons must be followed by single whitespace.

       // NOT Recommended

             for (int j = 0;j < 10;j++)  

       // Recommended

             for (int j = 0; j < 10; j++)

       // NOT Recommended

             getDetails(id,age);

      // Recommended

       getDetails(id, age);

6.       All casts must be written without any space

     // NOT Recommended

        (ClassA) m.get(3); 

        ( ClassA )m.get(3);

   

      // Recommended

         (ClassA)m.get(3);  

7.       All keywords like if, while, for, switch, and catch should be followed by a single space.

     // NOT Recommended

     if(true) 

     // Recommended

     if (true)

     // NOT Recommended

     while(conut < 7)

     // Recommended

     while (count < 7)

     // NOT Recommended

     for(int j = 0; j < 10; j++) 

     // Recommended

     for (int j = 0; j < 10; j++)

    

     // NOT Recommended

     catch(Exception e) 

     // Recommended

     catch (Exception e)

Maximum Line Length:

    Maximum line length should not exceed 120 characters. 

 

Self Documenting Code:

The best practice is to write the code in a way so that it can explain itself without any comment.

 // NOT recommended

if ( (a == Good) && ( (b == better) || (b == best) ) )

 // Recommended

boolean isbetterbest = ( (b == better) || (b == best) );

 if ( (a == Good) && isbetterbest )

 

Structured Programming:

A method of writing a computer program that uses:

1.       Top-down analysis for  problem solving

2.       Modularization of program structure and organization and

3.       The structured code for the individual modules

Advantages of structured Programming:

1.       Programs are more easily and more quickly written. Big programming tasks are broken down far enough that each subtask is easy to program as a separate unit.

2.       Programs have greater readability. Fewer organizational and logical errors occur in the initial stages of program development and writing.

3.       Programs require less time to debug and test. Because fewer errors are made in the programs. However, modularity also makes it much faster to localize and correct those that do occur.

4.       Programs are easier to maintain. The logic of well organized, modular program is much easier to follow. Therefore, one can easily discover how and where to make necessary changes.

a.        Since modules are separate, independent units, an old module is simply replaced by a new module.

b.      Adding new features of capabilities to a program becomes as easy as adding new modules to a superstructure already available.

Structured Programming and Programming languages:

Three statements can be made about structured programming and programming languages:

1.       Programmer can apply a method of structured programming in any language

2.       Some languages have been designed in such a way that one virtually has to write a modular program.  E.g. ALGOL, Pascal, PL/I, Ada. These languages are sometimes said to be Block Structured Languages.

3.       The ease with which one can write structured code depends o some extend on the language used.

Hello World!

Hi all,

Just came across this link...check out Hello World program in different languages....

http://www.mycplus.com/featured-articles/hello-world-programs-in-300-programming-languages/

Have a nice day!

Dear Student,

PL refer to the following link for FPL-II unit -I

Microprocessor book for Pune university, First Year Engineering, FPL-II reference:

https://docs.google.com/file/d/0BwBMbY_2VMQsTkp3VUVxLU9XY0k/edit?usp=sharing


Best Luck

Turbo C

1987 – Version 1.0 of the Turbo C programming language is released. It offers the first integrated edit-compile-run development environment for the C programming language for IBM-compatible personal computers. Turbo C was developed by Bob Jervis as “Wizard C”. It runs on just 384KB of memory and is capable of inline assembly with full access to C symbolic names and structures.

Steve Yegges Blog about Why compilers matter?

Principles of Compiler Design

This semester I will be helping my B.E Computer Students to understand Compilers and its working.

OVERVIEW


A compiler or interptreter for a programminning language is often decomposed into two parts:

1. Read the source program and discover its structure.
2. Process this structure, e.g. to generate the target program.


Why to learn it?

To enhance understanding of programming languages


• To have an in-depths knowledge of low-level machine executables

• To write compilers and interpreters for various programming languages and domain-specific languages
   Examples: Java, JavaScript, C, C++, C#, Modula-3, Scheme, ML, Tcl/Tk, Database Query Lang., Mathematica, Matlab, Shell-Command-Languages, Awk, Perl, your .mailrc file, HTML, TeX, PostScript, Kermit scripts, .....

• To learn various system-building tools : Lex, Yacc, ...

• To learn interesting compiler theory and algorithms.

• To learn the beauty of programming in modern programming lang.

Index Sequential Search

#include


#define MAX 24

void createIndex(int index[],int isize,int arr[],int asize)
{
int i,j;

for(i=0,j=0;i
{
index[j]= arr[i];
}
index[j] = arr[asize-1];
}

int indexSeqSearch(int val, int index[], int isize, int arr[], int asize)
{
int i=0,j=0,pos=0;
int high=0,low=0;
if(val > index[isize-1] && val < index[0])
return -1;

while(i
{
if(val == index[i])
{
pos = 8 * i;
return pos;
}

if(val < index[i])
{
low = 8 * (i-1);
high = 8 * i;
break;
}

else
{
low = 8 * i;
high = 8 * (i+1);
}
i++;
}

while(low < high)
{
if(val == arr[low])
return low;
else
low++;
}
return -1;
}



int main()
{
int arr[MAX]={ 8,14,26,38,72,115,306,321,329,387,409,512,540,567,583,592,602,611,618,741,798,811,814,876};

int index[(MAX/8)+1]={0};
createIndex(&index[0],(MAX/8)+1,&arr[0],MAX);
int opt=0,pos=0;
while(opt < MAX)
{
pos = indexSeqSearch(arr[opt],&index[0],(MAX/8)+1,&arr[0],MAX);
if( pos != -1)
{
printf("\n%d found at position %d",arr[opt],pos);
}
else
printf("\n%d not found.",arr[opt]);
opt++;

}
return 0;
}

PL Practical Exam Variation List

1. Perform Set operations using arrays


2. Perform Set operations using linked list

3. String operations without using standard library functions

4. Matrix operations : Add, Sub, Multiply, Saddle Point

5. Matrix operations : Add, Sub, Multiply, Transpose

6. Matrix operations : Add, Sub, Transpose, Check for Magic Square

7. Matrix operations : Multiplication, Transpose, Check for magic Square

8. Create a Database using array of structures and perform following operations

a. Add

b. Delete

c. Modify

d. Display

e. Search and

f. Sort

9. Create a Database using text files and perform following operations

a. Add

b. Delete

c. Modify

d. Display

e. Search and

f. Sort

10. Implement Sorting methods using functions

a. Bubble

b. Selection

11. Implement Sorting methods using functions

a. Bubble

b. Insertion

12. Implement Sorting methods using functions

a. Insertion

b. Selection

13. Implement Sorting methods using functions

a. Shell Sort

b. Bubble Sort

14. Implement Sorting methods using functions

a. Shell Sort

b. Selection

15. Implement Sorting methods using functions

a. Shell

b. Insertion

16. Implement sorting methods using recursion

a. Quick Sort

b. Merge Sort

17. Implement Searching Methods

a. Sequential Search

b. Binary Search

18. Implement Searching Methods

a. Indexed Sequential Search

b. Binary Search

19. Implement Searching Methods

a. Sequential Search

b. Fibonacci Search

20. Represent Polynomial using structures and write a menu driven program to perform addition, Multiplication and Evaluation

21. Represent Sparse matrix using array and perform matrix addition, simple and fast transpose

22. Create SLL and Write a menu driven program to perform operations on it like

a. insert an element: at start, In between, At end

b. Search

c. Delete

d. Reverse

e. Display

23. Create CLL and Write a menu driven program to perform operations on it like

a. insert an element : at start, In between, At end

b. Search

c. Delete

d. Reverse

e. Display

24. Create DLL and Write a menu driven program to perform operations on it like

a. insert an element: at start, In between, At end

b. Search

c. Delete

d. Reverse

e. Display

25. Create CDLL and Write a menu driven program to perform operations on it like

a. insert an element: at start, In between, At end

b. Search

c. Delete

d. Reverse

e. Display

26. Create two SLLs, sort one after creation and one while creation using pointer manipulation. Merge these two lists into one list without creating a new node or swapping of the data

27. Create two DLLs, sort one after creation and one while creation using pointer manipulation. Merge these two lists into one list without creating a new node or swapping of the data

28. Represent Polynomial using CLL and write a menu driven program to perform addition, Multiplication and Evaluation

29. Implement stack as an ADT using array. Use this ADT to perform expression conversion and evaluation- Prefix to postfix

30. Implement stack as an ADT using array. Use this ADT to perform expression conversion and evaluation- Postfix to Prefix

31. Implement stack as an ADT using array. Use this ADT to check the correctness of parenthesized expression e.g. (a))-wrong, (a+b)+c-correct

32. Represent a circular queue using linked list and write a program to perform operations like Insert, Delete, finding front and rear element

33. Create a Database using linked list and perform following operations

a. Add

b. Delete

c. Modify

d. Display

e. Search and

f. Sort

DSL Practical Exam Variation List From Anil Bhadgale Sir

 DATA STRUCTURES LABORATORY


ASSIGNMENTS LIST

Group A (C++ programming)

• Create binary search tree and perform recursive traversals (Preorder, Inorder and Postorder)

• Create binary search tree and perform non recursive traversals (Preorder, Inorder and Postorder)

• Create a binary expression tree for any expression (infix/prefix/postfix) and perform non recursive traversals.

Eg. A+B

+AB

+

/ \

A B

• Create a binary expression tree for any expression (infix/prefix/postfix) and perform recursive traversals.

• Create a binary expression tree for any expression(infix/prefix/postfix) and perform non recursive Inorder and Preorder traversals and recursive Postorder traversal( any combination can be asked in examination)

• For any of above tree assignment perform deletion of node operation, The tree should be updated after deleting the node( assume different cases like lea, non leaf node with single child/double child)

• Create binary search tree and find height of the tree, print leaf nodes.

• Create binary tree for string as information and find height of the tree, print leaf nodes and display siblings of each other, find the number of subtrees that can be generated.

• Create binary tree by asking the user to insert (left/right).Find mirror image, print original and mirror image using level-wise printing

• Create in-order threaded binary tree and perform traversals(also deletion of node)

• Represent graph using adjacency list (Adjacency matrix) and perform DFS(Non recursive/recursive )

• Represent graph using adjacency list (Adjacency matrix) and perform BFS (Non recursive/recursive )

• Represent graph using adjacency list or matrix and generate minimum spanning tree using Prism’s algorithm

• Represent graph using adjacency list or matrix and generate minimum spanning tree using Kruskal’s algorithm (prims and kruskals having same minimum weight)

• Represent graph using adjacency list or matrix and find shortest distance and path using Dijkstra’s Algorithm

• Implementation of AVL tree

• Implementation of direct access file using different collision resolution techniques(using linear probing/chaining)

• Different File operations using command line arguments on sequential file.

Group B (STL implementation)

• Write a program to add binary numbers (assume one bit as one number)

• Implement Dqueue (Double ended queue)

• Use STL for Sorting and searching with user-defined records such as Person Record

(Name, birth date, telephone no), item record (item code, item name, quantity and cost)

• .Implementation of SLL , DLL and CLL

• Implementation of stack & queue using SLL

Group C

• Write a C++ program to implement a small database mini project to understand persistent objects and operations on sequential files (eg library information, inventory systems, automated banking system, reservation systems etc.) For example, write a program to create a database for reservation

system using information such as Name, sex, age, starting place of journey and destination. Program should have following facilities

a) To display entire passenger list

b) To display particular record

c) To update record

d) To delete and sort record

Use Exception Handling for data verification



(Subject I/c)

Object Oriented Design

This chapter from Jalote gives us insight into the object oriented design and analysis.
The OO concepts which are learned from C++ point of view, will be much more clear and their applications in real world projects and thier relevancy will be clear too.

in reference to: An integrated approach to software ... - Google Books (view on Google Sidewiki)

OOP Variations

1. Write a C++ program to generate the fibonacci series for n terms


2. Write a C++ program to find the factorial of a given number using Function

3. Write a C++ program using SWITCH CASE structure to display the given number in words. (enter number between 1 and 9).

4. Write a C++ program to check whether the given string is palindrome or not

5. Write a C++ program to find the number of Odd and Even numbers in a given array.

6. Write a C++ program to transpose a 3x3 matrix.

7. Write a C++ program to add two 3x3 matrices

8. Write a C++ program using function to determine whether the given number is prime or not

9. Write a C++ program to define a class employee with the following specification

private members of class employee

empno – integer

ename - 20 characters

basic – float

Netpay, hra, da, float

calculate() - A function to find the basic+da+hra with float return type





public member functions

havedata() - A function to accept values for empno, ename, basic,hra,da and call

calculate() to compute netpay

dispdata() - A function to display all the data members on the screen

10. Write a C++ program that uses function overloading to do the following tasks

a) find the maximum of two numbers (integers)

b) find the maximum of three numbers (integers)

11. Write a C++ program to find the sum and difference of two numbers using inheritance

ADD SUBTRACT



public add(), accept(), plus() subtract(), minus()

private sum() sub()

protected num1, num2

12. Write a C++ program to get the following output

C

CO

COM

COMP

COMPU

COMPUT

COMPUTE



13. Animal insurance



Write a program that prints the insurance fee to pay for a pet according to the following rules:

• A dog that has been neutered costs $50.

• A dog that has not been neutered costs $80.

• A cat that has been neutered costs $40.

• A cat that has not been neutered costs $60.

• A bird or reptile costs nothing.

• Any other animal generates an error message.

The program should prompt the user for the appropriate information, using a code to determine the kind of animal (i.e. D or d represents a dog, C or c represents a cat, B or b represents a bird, R or r represents a reptile, and anything else represents some other kind of animal).

After printing the insurance fee, the program should ask the user if (s)he wants to insure another animal.



Remember to write the program in a clear style with indentation.





14. Pupils' heights

The health visitor at a school is going to measure the heights of all pupils. For each class she makes a statistics giving the number of pupils of each height and the average height.

Make a C++ program that helps the health visitor making the statistics.

Example:

In a class with 20 pupils the heights of the individual pupils, in centimeters, are:

175, 167, 160, 164, 183, 187, 188, 179, 176, 175,

169, 175, 176, 178, 165, 160, 173, 165, 187, 178

The program should read in all the numbers and make a table like this:

height number of pupils

160 2

164 1

165 2

167 1

... ...

... ...

188 1

average height 174.0

15. Pocket calculator

The program should read in a text string containing a list of numbers separated by + or - and output the sum. The program should also tell how many positive numbers and how many negative (subtracted) numbers there are.

Example:

input: 8.4 + 2.6 - 3.5 + 1

output: result = 8.5, positive numbers: 3, negative numbers: 1.

The input cannot contain any other operators than + and -. Spaces are allowed.

The program should be organized so that main reads the input as a single text string and outputs the results. The interpretation of the text string and calculation of results should be in a separate sub-function. Do not use global variables.

Tip: the function atof can read a number from a text string. Anything that comes after the number is ignored by atof.

16. The political oracle

In the year 2097, the president of the United States of Europe doesn't have the time to write his own political speeches because he is busy hosting a lottery show on TV. His secretary has asked you to make a computer program which can write political speeches by combining popular clichés randomly. A statement is generated by combining randomly selected phrases from each of the categories G, A, S, and V below according to the scheme G - A - S - V - G - A - S. For example:

"My improved freedom benefits our common responsible national security."

Hint: The function random(n) will give you a random number in the interval from 0 to n-1. Use this function to choose a cliché from a category containing n clichés. The function randomize() must be called in the start of the main program before the first call to random(n).

Write #include at the top of your program to get access to these functions.

Category G

my, our common, the party's, my family's, our children's, my fellow Europeans', the government's, the industry's, the consumers', the immigrants', the only truly

Category A

improved, responsible, peacekeeping, free, pro-life, politically correct, integrated, federal, progressive, anti-crime, drug-addicted, gradual, democratic, genetically engineered, racial

Category S

freedom, national security, abuse, opportunity, tax cut, congress, task force, Europe, decision, dialogue, future, community, answer, environment, set of family-values, legislation, discrimination

Category V

benefits, improves, decreases, supports, is built on, is the best guarantee for, creates an opportunity for, forms, is necessary for, will be established to combat



17. Matrix operations

Write a program that can do the following:

• addition of two matrices

• subtraction of two matrices

• multiplication of a matrix by a scalar

• multiplication of a matrix by a matrix

• transpose a matrix

The order of the matrices could be 3 x 3, or variable if you want.

Equations



18. Make a function that can solve two linear equations with two unknowns. The solution should be returned through pointer parameters or reference parameters. Make a program that inputs the six coefficients, calls the function, and outputs the solution.







19. Make a function that solves a quadratic equation, and a program that uses this function. The function should return the number of solutions as well as the solutions (if any) to the calling program.



In case you've forgotten everything you've learned in math, here are the formulae:

Discriminant







20. Bit manipulation



Write a function that prints out an integer in binary representation.

Write a function that finds the parity of an integer. The parity is 1 if there is an odd number of 1-bits in the binary representation of the integer, and 0 if there is an even number of 1-bits.

Write a program that reads in an integer and outputs the number in binary representation and the parity of the number, using the functions above.

21. Primes

A prime number is a positive integer which is not divisible by any other number, except by 1. The first ten prime numbers are:

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, ...



Write a program that finds all prime numbers below 1000.

The program should determine if a number is prime by trying if it is divisible by any of the prime numbers found so far. If it is not divisible by any prime number, then it is a prime. There is no need to test even numbers.

22. Telephone directory

Make a program that can sort a list of names and telephone numbers alphabetically. Persons are sorted alphabetically by their last names. Persons with the same last name are sorted by their first names.

Input: names and telephone numbers,

Output: list of names and telephone numbers ordered alphabetically.

Define a structure named person that contains a person's first name, last name, and telephone number.

Define a function that compares two structures of type person according to the following prototype:

int compare(person * a, person * b);

This function should return a negative value if person a comes before b, and a positive value if b comes before a. (You may use the function stricmp(name1,name2) to compare two strings).

Define a function that swaps the contents of two structures of type person:

void swap(person * x, person * y);

Use the following function to sort an array of structures of type person:

void sort(person * list, int NumberOfPersons)

{ // sort list using bubble sort method (page 96):

int a, b;

for (a=1; a

{

for (b=NumberOfPersons-1; b>=a; b--)

{

if (compare(list+b-1, list+b) > 0)

{

swap(list+b-1, list+b);

}

}

}

}

23. Ohm's law

Make a class describing a resistor with the following members:

• a private data member for the resistance, R

• a public member function to set the value of R

• a public member function to calculate the current I from the voltage E

• a public member function to calculate the voltage E from the current I

• a public member function to calculate the power dissipation P from the current I using the formula P = I•E, where E is calculated using the previous member function.

Make a program to test this class.

24. Pendulum

Make a C++ class describing a simple pendulum with appropriate data members and member functions for setting the values of the length , mass m, and energy E, calculating the time period



and the velocity in the lower position

.

25. Parabola as object

Make a class defining a polynomial of second degree y = A x2 + B x + C

The coefficients A, B, C should be private. The class should contain the following member functions:

• a function that sets the coefficients to desired values

• a function that calculates y for a given value of x

• a function that tells how many roots there are and returns the roots (if any)

• a function that tells whether the polynomial has a maximum, a minimum, or no extremum, and gives x and y for the extremum (if any)

Make a program to test an object of this class.

In case you've forgotten everything you've learned in math, here are the formulae:

Discriminant

Complex Number Class

Complex Number Class
A complex number is a number that has two components; the real component and the imaginary component.


a + bi

Arithmetic is defined as follows:

(a + bi) + (c + di) = (a + c) + (b + d)i

(a + bi) - (c + di) = (a - c) + (b - d)i

(a + bi) * (c + di) = (ac - bd) + (ad + bc)i

(a + bi) / (c + di) = (ac + bd) / (c**2+d**2) + [ (bc -ad) /(c**2+d**2)]i

Class Declaration

class complex


{

public:

complex();

complex(double,double);

double getReal() const;

void setReal(double);

complex operator+(complex) const;

complex operator-(complex) const;

complex operator*(complex) const;

complex operator/(complex) const;

private:

double real, imag;

};

complex::complex():real(0),y(0)


{ //default constructor

}



complex :: complex(double r, double im)

{

real = r;

imag = im;

}

complex complex::operator+(complex c) const


{

complex temp;

temp.real = real + c.real;

temp.imag = imag + c.imag;

return temp;

}

complex complex::operator/(complex c) const


{

complex temp;

temp.real = (real*c.real + imag*c.imag)/

( pow(c.real,2) + pow(imag,2) );

temp.imag = (imag*c.real - real*c.imag)/

( pow(c.real,2) + pow(imag,2) );

return temp;

}

complex complex::operator*(complex c) const


{

complex temp;

temp.real = real*c.real – imag*c.imag;

temp.imag = real*c.imag + imag*c.real;

return temp;

}

Scan line poly fill

#include


#include

#include



main()

{



int n,i,j,k,gd,gm,dy,dx;

int x,y,temp;

int a[20][2],xi[20];

float slope[20];





clrscr();

printf("\n\n\tEnter the no. of edges of polygon : ");

scanf("%d",&n);

printf("\n\n\tEnter the cordinates of polygon :\n\n\n ");



for(i=0;i

{

printf("\tX%d Y%d : ",i,i);

scanf("%d %d",&a[i][0],&a[i][1]);

}



a[n][0]=a[0][0]; // polygon

a[n][1]=a[0][1];





detectgraph(&gd,&gm);

initgraph(&gd,&gm,"c:\\bgi");





/*- draw polygon -*/



for(i=0;i

{

line(a[i][0],a[i][1],a[i+1][0],a[i+1][1]);

}



getch();





for(i=0;i

{

dy=a[i+1][1]-a[i][1];

dx=a[i+1][0]-a[i][0];



if(dy==0) slope[i]=1.0;

if(dx==0) slope[i]=0.0;



if((dy!=0)&&(dx!=0)) /*- calculate inverse slope -*/

{

slope[i]=(float) dx/dy;

}

}



for(y=0;y< 480;y++) // find x intersections

{

k =0;

for(i=0;i

{

if( ((a[i][1]<=y)&&(a[i+1][1]>y))

((a[i][1]>y)&&(a[i+1][1]<=y)))

{

xi[k]=(int)(a[i][0]+slope[i]*(y-a[i][1]));

k++;

}

}



for(j=0;j

for(i=0;i

{

if(xi[i]>xi[i+1])

{

temp=xi[i];

xi[i]=xi[i+1];

xi[i+1]=temp;

}

}



setcolor(35);

for(i=0;i

{

line(xi[i],y,xi[i+1]+1,y);

getch();

}



}

return 0;

}

FTP access

Who deleted SECOMP folder from ftp?

This is very serious!!!

Definately some one from your class....

Practical Examination tips

1. Use C++ only in OOP paradigm
2. All Graphics program must work in k/b mode as well as mouse interfacing mode
3. As far as possible try using function and operator overloading for all classes
4. << and >> needs to be overloaded for classes for input and output
5. Using formatted IO from iostream and iomanip is compulsory
6. Try other possible variation in problem statement

Start practicing now, so that you will be comfortable with all the c++ constructs.

The Sutherland-Hodgeman Polygon Clipping Algorithm

 

 

1. Introduction

It is often necessary, particularly in graphics applications, to "clip" a given polygon with another. Figure 1 shows an example. In this article we'll look at the particular case where the clipping polygon is a rectangle which is oriented parallel with the axes. For this case, the Sutherland-Hodgeman algorithm is often employed. This is the algorithm that we will explore.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 1

 

 

 

2. The Sutherland-Hodgeman Algorithm

The Sutherland-Hodgeman polygon clipping algorithm is relatively straightforward and is easily implemented in C. It does have some limitations, which we'll explore later. First, let's see how it works.

For each of the four sides of the clipping rectangle, consider the line L through the two points which define that side. For each side, this line creates two planes, one which includes the clipping rectangle and one which does not. We'll call the one which does not the "clipping plane" (Figure 2).

 

 

 

 

 

 

 

 

 

 

 

 

 

L

 

 

 

 

 

 

 

 

 

 

 

Figure 2

 

 

For each of the four clipping planes, we must remove any vertices of the clipped polygon which lie inside the plane and create new points where the segments associated with these vertices cross the line L (Figure 3).

 

 

 

 

 

 

 

 

 

 

 

L

 

 

 

 

 

 

 

 

 

 

 

Figure 3

 

 

After clipping each of the four planes, we are left with the clipped polygon.

 

 

3. Limitations

This algorithm always produces a single output polygon, even if the clipped polygon is concave and arranged in such a way that multiple output polygons might reasonably be expected. Instead, the polygons will be linked with overlapping segments along the edge of the clipping rectangle (Figure 4). This may or may not be the desired result, depending on your application.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 4

 

 

 

4. Practical Implementation

 

#include <math.h>

#include <assert.h>

 

 

#define CP_MAXVERT 32

#define CP_LEFT 0

#define CP_RIGHT 1

#define CP_TOP 2

#define CP_BOTTOM 3

 

struct rect{

double t; /* Top */ double b; /* Bottom */ double l; /* Left */ double r; /* Right */

};

 

struct point{ double x; double y;

};

 

To determine the correct course of action in the main algorithm, we'll need to be able to check if a given point is "inside" or "outside". In this sense, we take "outside" to mean "within the clipping plane". This function takes the point in question, the clipping rectangle, and a number indicating which side of the rectangle is forming the clipping plane.

 

 

 

int cp_inside( struct point p, struct rect r, int side )

{

switch( side ){

case CP_LEFT:

return p.x >= r.l;

case CP_RIGHT:

return p.x <= r.r;

case CP_TOP:

return p.y <= r.t;

case CP_BOTTOM:

return p.y >= r.b;

}

}

 

When one of the two points defi ning a line segment is "inside" and the other is "outside", we will need to create a new vertex where the segment intersects the clipping rectangle.

This function takes the "inside" point (p), the "outside" point (q), the clipping rectangle, and again the side in question.

It first finds the slope (a) and y-intercept (b) of the line segment pq. Now, depending on the side under consideration, either the x or y component of the new point is set equal to that of the bounding side and the remaining component is computed using the slope and intercept previously found. When considering the top or bottom sides, it is possible that the segment pq is vertical. This condition can be recognized when the slope (a) is infinite. In this special case, the x component of the new point will be the same as the x component of

p or q.

 

struct point cp_intersect( struct point p, struct point q, struct rect r, int side )

{

struct point t;

double a, b;

 

/* fi nd slope and intercept of segment pq */

a = ( q.y - p.y ) / ( q.x - p.x );

b = p.y - p.x * a;

 

switch( side ){

case CP_LEFT:

t.x = r.l;

t.y = t.x * a + b;

break;

case CP_RIGHT:

t.x = r.r;

t.y = t.x * a + b;

break;

case CP_TOP:

t.y = r.t;

if( isfi nite(a) )

t.x = ( t.y - b ) / a;

 

else

 

break;

 

t.x = p.x;

 

case CP_BOTTOM:

t.y = r.b;

if( isfi nite(a) )

t.x = ( t.y - b ) / a;

else

 

 

 

 

 

 

 

}

 

return t;

}

 

break;

t.x = p.x;

 

 

 

This function clips the clipped polygon against the clipping plane for a particular side of the clipping rectangle. Starting with the fi rst vertex in the clipped polygon, we consider each vertex (p) along with the one before it (s).

 

There are four ways that these two points may be arranged:

Both s and p are "inside": The point p should be included in the output polygon.

The point s is "outside" while p is "inside": The intersection of sp and the line L defi ning the clip- ping plane should be included in the output, followed by p.

The point s is "inside" while p is "outside": The intersection of sp and the line L defi ning the clip- ping plane should be included in the output.

The points s and p are both "outside": nothing need be done on this step.

 

void cp_clipplane( int *v, struct point in[CP_MAXVERT], struct rect r, int side )

{

int i, j=0;

struct point s, p;

struct point out[CP_MAXVERT];

 

s = in[*v-1];

for( i = 0 ; i < *v ; i++ ){

p = in[i];

 

if( cp_inside( p, r, side ) ){

/* point p is "inside" */

if( !cp_inside( s, r, side ) ){

/* p is "inside" and s is "outside" */ out[j] = cp_intersect( p, s, r, side ); j++;

}

out[j] = p; j++;

}else if( cp_inside( s, r, side ) ){

/* s is "inside" and p is "outside" */ out[j] = cp_intersect( s, p, r, side ); j++;

}

 

s = p;

}

 

/* set return values */

*v = j;

for( i = 0 ; i < *v ; i++ ){

in[i] = out[i];

}

}

 

 

 

The actual clippoly function is very simple; it calls the previous function (cp_clipplane) once for each side of the clipping rectangle. First, though, it performs a few tests to make sure that the input data make sense and that there will be room to store the output polygon.

 

void clippoly( int *v, struct point p[CP_MAXVERT], struct rect r )

{

/* sanity checks */

assert( *v <= CP_MAXVERT / 2 );

assert( r.l < r.r );

assert( r.b < r.t );

 

cp_clipplane( v, p, r, CP_LEFT ); cp_clipplane( v, p, r, CP_RIGHT ); cp_clipplane( v, p, r, CP_TOP ); cp_clipplane( v, p, r, CP_BOTTOM );

}

 

 

 

From : http://www.aftermath.net/