[algogeeks] Re: Area of Intersection between Oriented Rectangles
Some ideas: - Divide each of the rectangles into 2 triangles, then calculate each 2 triangles intersection(from opposing rectangles). - Use line sweep method. - Ucse convex-polygon intersection method mentioned in almost every computational geometry book.(or find some on the internet) Good Luck. On Tue, Jun 3, 2008 at 12:29 AM, Vasant [EMAIL PROTECTED] wrote: Greetings! As the subject line specifies, am trying to compute the area of overlap between two rectangles that can have any arbitrary orientation. I plan to go about this by finding vertices of Rectangle1 contained in Rectangle2 and vice versa. Then, I will find the points of intersection between the rectangles. Finally, I intend to compute areas of individual triangles from a source vertex and add them to calculate the final area of intersection. I wanted to know if there is an easier way of doing this. Any pointer to a more effective method (if any) will be very useful. Hope to hear from you soon. Thanks! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Plannar graph
what's the problem?! K4 does not contain K3,3 or K5 = K4 is planar! On Tue, Mar 25, 2008 at 5:42 PM, Karthik Singaram Lakshmanan [EMAIL PROTECTED] wrote: K4 is planar http://en.wikipedia.org/wiki/Planar_graph --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Plannar graph
A graph is planar iff it does not contain K5 and K3,3 . read chapter 6 (Planar Graphs) from Introduction to Graph Theory, Douglas B. West 2008/3/24 kunzmilan [EMAIL PROTECTED]: On 17 Bře, 10:38, sp1 [EMAIL PROTECTED] wrote: How to test an given graph is plannar? The answer gives its distance matrix. When distances between vertices of the graph are squared, the distance matrix of a plannar graph has only 4 nonzero eigenvalues. kunzmilan --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding the subtree with the largest weight
int maxw(node root)
{
if(root == null) return (0);
int L = maxw(root.lchild);
int R = maxw(root.rchild);
return max( (max(R,L,R+L)+root.value), R, L, root.value );
}
-Original Message-
From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On
Behalf Of Debajit Adhikary
Sent: Tuesday, January 29, 2008 12:40 PM
To: Algorithm Geeks
Subject: [algogeeks] Re: Finding the subtree with the largest weight
On Jan 29, 2008 3:07 PM, Debajit Adhikary [EMAIL PROTECTED] wrote:
Lets say I have a weighted tree (with positive, zero and negative
weights for each node).
How could I best find the subtree having the maximum weight?
On Jan 29, 3:55 am, Yingjie Xu [EMAIL PROTECTED] wrote:
A rooted tree or a general tree?
It is a rooted weighted tree, where each node is assigned a weight
which can be positive, zero or negative.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Finding the subtree with the largest weight
what do you mean by subtree?
A node with its all descendents? Or possibly a node with for example its
left subtree?
Anyway that's a simple task. Recursively compute for childs then check
wether it worths to have L+R+root.value or simply just R or L.
If you mean subtree to be a node with possibly one of its childs, then check
also R+root.value and L+root.value.
-Original Message-
From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On
Behalf Of Debajit Adhikary
Sent: Tuesday, January 29, 2008 1:18 PM
To: Algorithm Geeks
Subject: [algogeeks] Re: Finding the subtree with the largest weight
Well, we need to return the *node* which is at the root of the subtree
with the largest weight.
On Jan 29, 4:40 am, Nima Aghdaie [EMAIL PROTECTED] wrote:
int maxw(node root)
{
if(root == null) return (0);
int L = maxw(root.lchild);
int R = maxw(root.rchild);
return max( (max(R,L,R+L)+root.value), R, L, root.value );
}
-Original Message-
From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On
Behalf Of Debajit Adhikary
Sent: Tuesday, January 29, 2008 12:40 PM
To: Algorithm Geeks
Subject: [algogeeks] Re: Finding the subtree with the largest weight
On Jan 29, 2008 3:07 PM, Debajit Adhikary [EMAIL PROTECTED] wrote:
Lets say I have a weighted tree (with positive, zero and negative
weights for each node).
How could I best find the subtree having the maximum weight?
On Jan 29, 3:55 am, Yingjie Xu [EMAIL PROTECTED] wrote:
A rooted tree or a general tree?
It is a rooted weighted tree, where each node is assigned a weight
which can be positive, zero or negative.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: subset with maximum sum.
read Kadane's http://www.algorithmist.com/index.php/Kadane%27s_AlgorithmAlgo. On 10/13/07, kannan [EMAIL PROTECTED] wrote: hellow! here is the problem statement. you have to find the subset having the maximum sum in the given array of +ve and -ve numbers. try not to follow brute force method. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
use the cross product to examine whether they're collinear. points A,B,C: AB*BC =? 0 On 5/27/07, Feng [EMAIL PROTECTED] wrote: Hi all! Given 3 points in 3D, what is the fast and numerically stable way to test if they form a triangle? I am thinking computing the determinant of the square matrix formed by the 3 points and testing if the determinant is nonzero. But I am not sure. What about the case for high dimensions, i.e. 4D, 5D ... Thanks! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
