Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Divide and Conquer - Merge/Tangent Function

Posted on 2010-11-19
12
Medium Priority
?
2,102 Views
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
  l3-1.gif
0
Comment
Question by:warhero
[X]
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
12 Comments
 
LVL 27

Expert Comment

by:aburr
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.
0
 
LVL 1

Author Comment

by:warhero
ID: 34180602
@aburr

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

thank you
0
 
LVL 27

Expert Comment

by:aburr
ID: 34180769
Not likely to be helpful
I am most fluent in Fortan, which I doubt if you would find helpful
0
The top UI technologies you need to be aware of

An important part of the job as a front-end developer is to stay up to date and in contact with new tools, trends and workflows. That’s why you cannot miss this upcoming webinar to explore the latest trends in UI technologies!

 
LVL 37

Expert Comment

by:TommySzalapski
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.
0
 
LVL 37

Expert Comment

by:TommySzalapski
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.
0
 
LVL 84

Expert Comment

by:ozo
ID: 34182624
What seems more complicated when you try them?
0
 
LVL 1

Author Comment

by:warhero
ID: 34182662
@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

by:
TommySzalapski earned 1500 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.
0
 
LVL 1

Author Comment

by:warhero
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;
		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++;
			}
		}
	}

Open in new window


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

Expert Comment

by:TommySzalapski
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.
0
 
LVL 1

Author Comment

by:warhero
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
0
 
LVL 1

Author Closing Comment

by:warhero
ID: 34201492
thanks man....
0

Featured Post

The top UI technologies you need to be aware of

An important part of the job as a front-end developer is to stay up to date and in contact with new tools, trends and workflows. That’s why you cannot miss this upcoming webinar to explore the latest trends in UI technologies!

Question has a verified solution.

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

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

715 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