• Status: Solved
• Priority: Medium
• Security: Public
• Views: 2154

# Divide and Conquer - Merge/Tangent Function

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...

thanks you
l3-1.gif
0
warhero
• 5
• 4
• 2
• +1
1 Solution

Commented:
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.
0

Author Commented:
@aburr

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

thank you
0

Commented:
I am most fluent in Fortan, which I doubt if you would find helpful
0

Commented:
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.
0

Commented:
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.
0

Commented:
What seems more complicated when you try them?
0

Author Commented:
@tommy

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 !

@ozo

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
0

Commented:
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.
0

Author Commented:
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;
while(done){
done = false;
while(left.get(i).x*right.get(j).y > (right.get(j).y*right.get(j).y)-1){
left.remove(i);
i--;
done = true;
}
while(left.get(i).x*right.get(j).y < left.get(j).x+left.get(j).x){
right.remove(j);
j++;
}
}
}
``````

can you tell what i did wrong and explain ... thank you
0

Commented:
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++
}
``````

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

Author Commented:
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
0

Author Commented:
thanks man....
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.