Assignment 4

[Irwin Williams]

I was still too glazed over in the eyes, by exams to pay attention to the assignment, anybody wrote it down?
________________________
*I am a software solutions developer.*
Do you see a man skilled in his work?
He will serve before kings; he will not
serve before obscure men.
Proverbs 22:29

[Akash Harriram]

The convex hull problem

 

You must implement 3 solutions to solving the convex hull problem.

 

Input: n, the number of points followed by the (x, y) coordinates of each of the n points. Assume n <= 1000. Sample data:

 

9

3 3 3 2 3 4 2 1 2 2

2 3 5 2 4 2 1 3

 

Output: the name of the method, the number of points, h, in the convex hull, followed by the coordinates of the h points in counter-clockwise order, starting with the “lowest” point. For the above data and the Graham scan, you should print

 

Graham scan

4

(2,1) (5, 2) (3, 4) (1, 3)

 

Also print the time taken for the method to find the convex hull.

 

Your main routine must call each of your methods for finding the convex hull.

[Irwin Williams]

Thanks Akash, did he give method names?

--
Irwin Williams
785-1268

[Akash Harriram]

This was in the original assignment but he didn't specify for this one:

You may implement solutions using at least two of the Jarvis march, Graham scan or Quickhull.

[Irwin Williams]

It feels strange that he told us of these ways of finding the convex hull.
Anyway, lemme get down to it and see what is what

[Irwin Williams]

lame question,
how do you find the interior angle of three points?
http://stackoverflow.com/questions/1211212/how-to-calculate-an-angle-from-three-points

[Irwin Williams]

I can't find my test data, anyone has test data they care to share?

[Kyle E. deFreitas]

lol...u trying to put the rest of us to shame...lol

:) I ain't reach any where for test data.

lol

--
Kyle deFreitas
St Vincent and the Grenadines
Contact #: 1-784-454-4037
or
1-868-722-5346

[Irwin Williams]

LOL. Graham givin me rell beans!

[Rachel Yen Chong]

Here's some test data:
_____________
Test 1

8
7 7 7 -7 -7 -7 -7 7 9 0 -9 0 0 9 0 -9

Test 2

16
7 7 7 -7 -7 -7 -7 7 9 0 -9 0 0 9 0 -9
0 0 1 2 -2 1 -1 -1 3 4 4 3 -5 4 6 5

Test 3

72
0 0 1 2 -2 1 -1 -1 3 4 4 3 -5 4 6 5
7 7 7 -7 -7 -7 -7 7 9 0 -9 0 0 9 0 -9
-8 0 8 0 -7 0 7 0 -6 0 6 0 -5 0 5 0
-4 0 4 0 -3 0 3 0 -2 0 2 0 -1 0 1 0
0 -8 0 8 0 -7 0 7 0 -6 0 6 0 -5 0 5
0 -4 0 4 0 -3 0 3 0 -2 0 2 0 -1 0 1
1 1 2 2 3 3 4 4 5 5 6 6
1 -1 2 -2 3 -3 4 -4 5 -5 6 -6
-1 1 -2 2 -3 3 -4 4 -5 5 -6 6
-1 -1 -2 -2 -3 -3 -4 -4 -5 -5 -6 -6

All answers are the same:
8
(0, -9) (7, -7) (9, 0) (7, 7)
(0, 9) (-7, 7) (-9, 0) (-7, -7)

______________
Rachel

@Irwin let me know if your monotone chain works on these

[Irwin Williams]

Ok, quickly, my mono chain works, my jarvis doesnt

[Irwin Williams]

i hacked my jarvis into working. that can't be good. on to the next one (Graham)

[Kyle E. deFreitas]

Did everyone get the same result for test case three?

[Akash Harriram]

I did

[Kyle E. deFreitas]

GRRR....and i was hoping is something with the data lol

[kris manohar]

Hey All,

I know it real late but here are some if not all the links i used in solving the Convex hull problem. Hopefully it will be of use to those who did not get time to start the assignment as yet!

http://www.chrisharrison.net/projects/convexHull/index.html

http://stackoverflow.com/questions/1560492/how-to-tell-wether-a-point-is-right-or-left-of-a-line

http://www.ahristov.com/tutorial/geometry-games/convex-hull.html

http://www.ahristov.com/tutoriales/geometry-games/point-line-distance.html

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/jarvisMarch.htm

http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/GrahamScan/grahamScan.htm

Kris

--
If you want it, then  go get it!

[Aneisha Le Platte]

hi,

See attached for the user responses. 

let me know if you all prefer to split the task from here on out. 

---

Date: Tue, 30 Nov 2010 19:42:05 -0400
Subject: Re: Assignment 4
From: justkri...@gmail.com
To: design-and-analy...@googlegroups.com

[Aneisha Le Platte]

hi, sorry please ignore :) 

---

From: anei...@live.com
To: design-and-analy...@googlegroups.com
Subject: RE: Assignment 4
Date: Tue, 30 Nov 2010 19:45:55 -0400