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
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Optimize your web performance

What's in the eBook?
- Full list of reasons for poor performance
- Ultimate measures to speed things up
- Primary web monitoring types
- KPIs you should be monitoring in order to increase your ROI

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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
This video teaches viewers about errors in exception handling.

636 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