Solved

# Divide and Conquer - Merge/Tangent Function

Posted on 2010-11-19
2,014 Views
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
Question by:warhero
• 5
• 4
• 2
• +1

LVL 27

Expert Comment

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

LVL 1

Author Comment

@aburr

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

thank you
0

LVL 27

Expert Comment

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

LVL 37

Expert Comment

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

LVL 37

Expert Comment

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

LVL 84

Expert Comment

What seems more complicated when you try them?
0

LVL 1

Author Comment

@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

LVL 37

Accepted Solution

TommySzalapski earned 500 total points
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

LVL 1

Author Comment

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

LVL 37

Expert Comment

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

LVL 1

Author Comment

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

LVL 1

Author Closing Comment

thanks man....
0

## Featured Post

Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.