Divide and Conquer - Merge/Tangent Function

Posted on 2010-11-19
Last Modified: 2012-05-10
Hai there,

Currently i have finished implementing convex hull however i am having problems with developing merge function (for D&C Hull) where it should merge the left and right hulls. I have seen all the pseudo code but when i try them it seems it is more complicated.

For example; L be left hull and R be the right hull and it may have many point (which i should say that its x and y (2-D))

Psuedo code for finding lower tangent would be:

Finding the Lower Tangent
LowerTangent(HA ; HB ) :
(1) Let a be the rightmost point of HA .
(2) Let b be the leftmost point of HB .
(3) While ab is not a lower tangent for HA and HB do
(a) While ab is not a lower tangent to HA do a = a - 1 (move a clockwise).
(b) While ab is not a lower tangent to HB do b = b + 1 (move b counterclockwise).
(4) Return ab.

The image attached will give you better understanding of what i am looking for...

please reply asap
thanks you
Question by:warhero
  • 5
  • 4
  • 2
  • +1
LVL 27

Expert Comment

ID: 34180291
I am not sure just what your procedure is but I can suggest an alternative procedure which might work.
start with a guess ab. extend it in both directions. If it intersects a hull move a or b (or both) and try again.
When it does not penetrate that hull you have the desired points.

Author Comment

ID: 34180602

can you show me an example of code on what you propose....

thank you
LVL 27

Expert Comment

ID: 34180769
Not likely to be helpful
I am most fluent in Fortan, which I doubt if you would find helpful
Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

LVL 37

Expert Comment

ID: 34181464
If this isn't for a school project, just take the vector points from both polygons run the convex hull code on that. Assuming you used a good algorithm it will have the same time complexity as the merge anyway so it's just as good and no new code is needed.

If it is for a school project, they might not let you get away with that (or they might be impressed with the cleverness of the approach, worth an ask). In which case, post the code you have so far, and we'll help you get there.
LVL 37

Expert Comment

ID: 34181465
It's still technically divide and conquer because you're removing all the points in the interior of the hulls. I think it's a really good recursive solution.
LVL 84

Expert Comment

ID: 34182624
What seems more complicated when you try them?

Author Comment

ID: 34182662

its not a school project but am writing an article explicitly on divide and conquer i want the program to work so i can show its advantages and disadvantages against other algorithms out there....

as what i hav done, i have finished implementing convexHull (and i know that it can used to derive the same output as dive and conquer outputs but for the sake of the article i can't reference my findings like that).

for the merge operation, as you said that it should be don recursively - i agree and i have already tried several attempts to develop the function but i am keep failing on finding edge (lower and upper tangent between two hulls) and removing the interior points. I cannot say that am failing, i honestly think that i don't understand the concept of how to find the lower and upper tangent ? as i have said before i have researched through internet and seen many pseudo code however i couldn't get the hands on a example code !


hai, its complicated or hard when - merge function i don't know what type of if statement or while statements i should use to find lower and upper tangent and also after finding that i would have to  remove the interior points or how to remove them in the process of finding tangents of hulls.

hop this helps u understand my problem... thanks
LVL 37

Accepted Solution

TommySzalapski earned 500 total points
ID: 34183017
Removing the interior points is easy, you just remove all the points between the endpoints of the two 'tangent' lines.

Let's say yo are looking at points Px from the first polygon and Qy from the second (assuming the points are indexed increasingly in clockwise order). If the slope of PxQy > slope of QyQy-1 , then it is not a lower tangent to Q's polygon. Likewise if the slope of PxQy < slope of Px+1Px then it's not a lower tangent of P's polygon. And similarly for the top.

Author Comment

ID: 34183536
so based on your instruction i sampled up some code... it doesn't really work and probably its because of some stupid mistake...

public static void lowerTangent(ArrayList<Point> left, ArrayList<Point> right){
		boolean done = true;
		//right most in left hull
		int i = left.indexOf(left.get(left.size()-1));
		//left most in right hull
		int j = 0;
			done = false;
			while(left.get(i).x*right.get(j).y > (right.get(j).y*right.get(j).y)-1){
				done = true;
			while(left.get(i).x*right.get(j).y < left.get(j).x+left.get(j).x){

Open in new window

can you tell what i did wrong and explain ... thank you
LVL 37

Expert Comment

ID: 34185445
Two issues I can see right off the bat. If your points are stored clockwise or counterclockwise, why would the leftmost point be point 0 and why would the rightmost be size-1?

Your slope function is way off. The slope of PQ is (P.y - Q.y)/(P.x - Q.x). I would suggest making a slope function
double slope(Point p, Point q)
  return (p.y - q.y)/(p.x/q.x);
  //of course if your x and y are ints you'll have to cast one
  //return (p.y - q.y)/(double)(p.x/q.x);
  //or however you do it in Java, I use C++

Open in new window

One more thing, since you already have the main loop, I'd just make the other two if blocks, but it shouldn't matter.

Author Comment

ID: 34201474
ok, i can see that i misunderstood the meaning of slope, i thought its just an expression.

Choosing the right most and left most of the hulls, give you the better chance of executing the algorithm in best case scenario. i am not the one who said it, from my research i gathered that info.

Either way, now it works but when you split dataset (for recursion), it has to be at least require 6 points for each hull (left and right).

Anyway thanks for the help, helpd me a lot

Author Closing Comment

ID: 34201492
thanks man....

Featured Post

Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Should localization be done inside spring controller 5 25
eclipse apache tomcat admin console 52 96
jboss wildfly 10.1 10 81
Glassfish admin console not working 1 10
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

786 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question