rajesh puppala
 

5.Convex Hull

Problem Description

Computer graphics deals with representation of graphical constructs into mathematical models. A point is represented by its coordinates (x, y). One of very popular algorithm is called "convex hull" where you are given a set of points in a plane. You have to find a smaller set of points such that all the other points are inside this smaller set of points. See below image for a convex hull idea by imagining an elastic band which engulfs the set of points.


You can use any algorithm of your choice to solve the convex hull problem, though we will suggest an algorithm which uses divide and conquer technique. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly.

In divide and conquer algorithm for convex hull problem,

  1. Divide the points into two equal sized sets L and R such that all points of L are to the left of the most leftmost points in R.
  2. Recursively find the convex hull of L (left hull) and R (right hull).
  3. Merge the left hull and the right hull to get the final hull. (Hint: merging may have to do with looking for the topmost points and the bottom most points in each hull).

Instructions to use Open PBT Client:

  1. Specify the work directory path in the 'Work Directory Path' field. The path should correspond to your solution work directory.
  2. Download the Support files by clicking the Get Support Files.
  3. You will find the problem directories containing:
    • problem.h file
    • problem.c file

in your work directory.

  1. Write your solution in .c file

Step 1:

In your Solution File:
Add a function struct convexhull* getConvex(int points[][2], int noofcoord).

Step 2:

Pass the following parameter to the function getConvex().

  • int    points[][2] :points represents coordinates of the points in the set.
  • int    noofcoord: noofcoord represents number of coordinates of the points.

Step 3:

Write the appropriate code for the given problem on below given Constraints.

  1. Here you have to write a code for a very popular algorithm is called "convex hull" where you are given a set of points in a plane. You have to find a smaller set of points such that all the other points are inside this smaller set of points.
  2. You can use any algorithm of your choice to solve the convex hull problem.
  3. We will suggest an algorithm which uses divide and conquer technique.
  4. In divide and conquer algorithm for convex hull problem,
    Divide the points into two equal sized sets L and R such that all points of L are to the left of the most leftmost points in R.
    Recursively find the convex hull of L (left hull) and R (right hull). Merge the left hull and the right hull to get the final hull. (Hint: merging may have to do with looking for the topmost points and the bottom most points in each hull)
  5. In easy words you have to find the smallest bourdary around all the points.(where points should lie on the boundary or inside the boundary )
  6. The Number of Coordinates should be greater than 3 else return NULL.
  7. Please read the exapmle carefully.

The Prototype of the Function is :

struct convexhull* getConvex(int points[][2], int noofcoord); Where points represents coordinates of the points in the set, noofcoord represents number of coordinates of the points and the function returns the set of the points that makes the convex hull.

Constraint

  • The Number of Coordinates should be greater than 3 else return NULL.

Example 1

Input


double points[][2] = {{3,1},{2,3},{1,2},{3,2},{2,4},{4,3},{4,4},{5,2}};
int noofcoord = 8;

Output


The function getConvex returns {{3,1},{1,2},{2,4},{4,4},{5,2}}.

Explanation: The points {{3,1},{1,2},{2,4},{4,4},{5,2}} which forms the convex hull of the outer most points in which all other points present inside. Hence the function returns the position of these points.

Example 2

Input


double points[][2] = {{2,1},{2,2},{1,3},{3,3}};
int noofcoord = 4;

Output


The function getConvex returns {{2,1},{1,3},{3,3}}.

Example 3

Input


double points[][2] = {{2,1},{2,2}};
int noofcoord = 2;

Output


The function getConvex returns NULL.

For C solutions

Header File

:

convexhull.h

Function Name

:

struct convexhull* getConvex(int points[][2], int noofcoord)

Directory Name

:

convexhull

File Name

:

convexhull.c

For C++ solutions

Header File

:

convexhull.h

Class Name

:

ConvexHull

Function Name

:

struct convexhull* getConvex(int points[][2], int noofcoord)

Directory Name

:

convexhull

File Name

:

convexhull.cpp

General Instructions

    *

The file / class names, functions, method signatures, header files to be used are mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.

    *

Do not forget to mention the file extension, either .c or .cpp as the case maybe.

    *

For C solutions, change the value of "C_OR_CPP" macro in header file to 1 and for C++ solutions change the value to 2.

    *

Incase of iostream.h specify as iostream only.



Rajesh
7306947200
pedana
krishna dt

JOKES CORNER:
Some Good "Poor Jokes"...
Here are some really bad pj's...Read on if u like some...


Lion Roaring...
what happens when the lion roars???
...
TOM & JERRY Begins......



Hights of Optimism:r
Soldier: "Sir we are surrounded by enemies on all sides!!!"
Sardar Major" Excellent!!! we can attack in any direction"



Flirt like this
What is the height of Flirting?
Its When your love letter starts with "TO WHOMSOEVER IT MAY CONCERN"
..
BRILLIANT WAYS GIRLS TURN GUYS DOWN!!
HE: I'm a photographer I've been looking for a face like yours!
SHE: I'm a plastic surgeon. I've been looking for a face like yours!!!
HE: May I have the pleasure of this dance?
SHE: No, I'd like to have some pleasure too!!!

the sardar...
Q: Why did the Sardar take a pair binoculars with him to a funeral?
A: It was a distant relative's funeral.

gabbbar...
Gabber: Kitne Aadmi they.
Sambha: Sardar Do,
Gabber: Mujhe ginti nahi aati. Do kitne hotey hain?
Sambha: Sardar Do Ek ke baad aata hai.
Gabber : Aur Do ke pehle?
Sambha: Do ke pehle Ek aata hai.
Gabber: To beech mein kaun aata hai?
Sambha: Beech mein koi nahi aata.
Gabber: To fir Dono ek saath kyon nahi atey?
Sambha: Do Ek ke baad hi aa sakta hai, kyonki Do ek se bada hai.
Gabber: Do ek se bada hai? Kitna bada hai?
Sambha Do ek se Ek bada hai?
Gabber: Agar Do ek se ek bada hai to ek ek se kitna bada hai?
Sambha: Sardar, Maine tumhara namak khaya hai, mujhe goli mar do

ek ladki...
A Lady is standing up on top of the hill and she is going to push her Father down from the hill top.....
SO what is the name of this lady ???
... Well her Name is PUSH-PA!!!!!!!!!!

HE: How did you get to be so beautiful?
SHE: I must have been given your share!!!
HE: Will you come out with me this Saturday?
SHE: Sorry! I'm having a headache this weekend!!!
HE: Go on, don't be shy. Ask me out!
SHE: Okay, get out!!!
HE: I think I could make you very happy
SHE: Why? Are you leaving?
HE: What would you say if I asked u to marry me?
SHE: Nothing. I can't talk and laugh at the same time!!!
HE: Can I have your name?
SHE: Why, don't you already have one?
HE: Shall we go and see a film?
SHE: I've already seen it!!!
HE: Do you think it was fate that brought us together?
SHE: Nah, it was plain bad luck!!!
Today, there have been 1 visitors (7 hits) on this page!
This website was created for free with Own-Free-Website.com. Would you also like to have your own website?
Sign up for free