[ Prev ]
2017-09-27

-- Sep 27 In-Class Exercise
For all points in set1:
 for all ponts in set2:
   find max dist.
For all points in set1: for all ponts in set2: find max dist.

-- Sep 27 In-Class Exercise
Resource Description for WhatsApp Image 2017-09-27 at 5.48.53 PM.jpeg
((resource:WhatsApp Image 2017-09-27 at 5.48.53 PM.jpeg|Resource Description for WhatsApp Image 2017-09-27 at 5.48.53 PM.jpeg))

-- Sep 27 In-Class Exercise
compute convex hull by seperating the two sets.
sort points by xcoordinates. the base case is when we are left with just 1 point. we can create the convex hull by taking the vector of the two connecting points that is greater in angle of the relative to the two sub connecting points.
compute convex hull by seperating the two sets. sort points by xcoordinates. the base case is when we are left with just 1 point. we can create the convex hull by taking the vector of the two connecting points that is greater in angle of the relative to the two sub connecting points.

-- Sep 27 In-Class Exercise
First split the set recursively in halves. The base case will be when there is only one point left in each set, i.e. you will have several sets (0,0), (1, -1/2)... etc.
Since the convex hull of a point is the point itself, the third step is complete. The same is true for 2 and 3 points.
When you are past 3 points, you will have to determine whether a point falls within the convex hull of the combined sets. If so, it should be removed.
The convex hull in this case is the points (0, 0), (2, -5), (2, 5), (3, 0)
First split the set recursively in halves. The base case will be when there is only one point left in each set, i.e. you will have several sets (0,0), (1, -1/2)... etc. Since the convex hull of a point is the point itself, the third step is complete. The same is true for 2 and 3 points. When you are past 3 points, you will have to determine whether a point falls within the convex hull of the combined sets. If so, it should be removed. The convex hull in this case is the points (0, 0), (2, -5), (2, 5), (3, 0)

-- Sep 27 In-Class Exercise
Algorithm outline:
1. Find the leftmost point in the graph (lowest x-coordinate). This will become the reference point p0.
2. Sort the points based on this reference point.
3. Go in a forward and reverse traversal of the list of points to form the lower and upper portions of the points, respectively. When a counter-clockwise turn occurs, add that point; otherwise, remove the last point added/explored. This forms the lower and upper hulls, which are sets of three points (geometrically, a triangle).
4. The clockwise and counter-clockwise directions can be determined by the cross product of the three points in question.
5. Return the lower and upper hulls as a combined list, omitting the last elements of each, since they are each other’s start and end points, respectively.
In the case of this example, the convex hull is [(x, y) = (2, -5), (x, y) = (3, 0), (x, y) = (2, 5), (x, y) = (0, 0)].
(Edited: 2017-09-27)
Algorithm outline: 1. Find the leftmost point in the graph (lowest x-coordinate). This will become the reference point p0. 2. Sort the points based on this reference point. 3. Go in a forward and reverse traversal of the list of points to form the lower and upper portions of the points, respectively. When a counter-clockwise turn occurs, add that point; otherwise, remove the last point added/explored. This forms the lower and upper hulls, which are sets of three points (geometrically, a triangle). 4. The clockwise and counter-clockwise directions can be determined by the cross product of the three points in question. 5. Return the lower and upper hulls as a combined list, omitting the last elements of each, since they are each other’s start and end points, respectively. In the case of this example, the convex hull is [(x, y) = (2, -5), (x, y) = (3, 0), (x, y) = (2, 5), (x, y) = (0, 0)].

-- Sep 27 In-Class Exercise
In the first division step we divide the points into two groups: G1 ={(0,0),(1,12),(1,−12)} G2 = {(2,5),(2,−5),(3,0).}
Subsequently we divide G1 into further groups until we reach: G3 = {(0,0)} G4 = {(1,1/2)} G5 = {(1,-1/2)}
G2 into two groups G6 = {(2,5)} G7 = {(2,-5)} G8 = {(3,0)}
G3, G4, G5 merge (two at a time) to form the left triangle G6, G7 and G8 merge (again two at a time) to form the right triangle
Then we find the point with the maximum coordinates in one of the dimensions. In our case lets take y. These points turn out to be (2,5) and (2,-5). Now we try to figure out the points form the left that triangle that these should connect to. Consider the vector from (2,5) to any of the points, lets say (1,1/2). As we are connecting from right to left and downwards (since it has max y), when we try to connect to the next point if the vector rotates clockwise we consider this as the new connection point . Hence we consider (2,5) to (0,0) as the new edge and discard (2,5) connection to (1,-1/2). Similarly we create the edge between (2,-5) to (0,0) but in this case we have to consider the rotation counterclockwise as we are y min. We draw a vector from (2,5) to
In the first division step we divide the points into two groups: G1 ={(0,0),(1,12),(1,−12)} G2 = {(2,5),(2,−5),(3,0).} Subsequently we divide G1 into further groups until we reach: G3 = {(0,0)} G4 = {(1,1/2)} G5 = {(1,-1/2)} G2 into two groups G6 = {(2,5)} G7 = {(2,-5)} G8 = {(3,0)} G3, G4, G5 merge (two at a time) to form the left triangle G6, G7 and G8 merge (again two at a time) to form the right triangle Then we find the point with the maximum coordinates in one of the dimensions. In our case lets take y. These points turn out to be (2,5) and (2,-5). Now we try to figure out the points form the left that triangle that these should connect to. Consider the vector from (2,5) to any of the points, lets say (1,1/2). As we are connecting from right to left and downwards (since it has max y), when we try to connect to the next point if the vector rotates clockwise we consider this as the new connection point . Hence we consider (2,5) to (0,0) as the new edge and discard (2,5) connection to (1,-1/2). Similarly we create the edge between (2,-5) to (0,0) but in this case we have to consider the rotation counterclockwise as we are y min. We draw a vector from (2,5) to

-- Sep 27 In-Class Exercise
for all points find the maximum distance among the points and separate them into two groups based on the distance.
for all points find the maximum distance among the points and separate them into two groups based on the distance.

-- Sep 27 In-Class Exercise
 Sort the points by ascending order of x value
 Divide the points into 2 groups until base case is reached (A single point)
 Merge the convex hulls
 Step to merge:
   -Draw vectors to points on the convex hulls to be merged
   -Make note of the angle the vectors have to rotate to move from one point on the hull 
    to another.
   -It should move outwards. If not, the point is removed
 At the end of the run, the remaining points after elimination constitute the merged 
 convex hull
 
Sort the points by ascending order of x value Divide the points into 2 groups until base case is reached (A single point) Merge the convex hulls Step to merge: -Draw vectors to points on the convex hulls to be merged -Make note of the angle the vectors have to rotate to move from one point on the hull to another. -It should move outwards. If not, the point is removed At the end of the run, the remaining points after elimination constitute the merged convex hull

-- Sep 27 In-Class Exercise
Compute the angle between the line joining the first two points with respect to the origin, say x. Compute the angle between the line joining the next two points with respect to the origin, say y. If the second angle is greater than the first one, ignore the second point. Check the angle between the third and the fourth point, say z. This angle is -ve. So, z is lesser than x. So, go back to the previous position and join that with the first point. Continue iterating.
Compute the angle between the line joining the first two points with respect to the origin, say x. Compute the angle between the line joining the next two points with respect to the origin, say y. If the second angle is greater than the first one, ignore the second point. Check the angle between the third and the fourth point, say z. This angle is -ve. So, z is lesser than x. So, go back to the previous position and join that with the first point. Continue iterating.
2017-09-28

-- Sep 27 In-Class Exercise
  • Sort the points based on x-coordinate's value
  • Keep dividing the points into two sets recursiveliy until there are three points in the set
  • Make convex hull of the three points
  • Merge the convex hull based on below steps
  • We can merge two convex hulls by finding upper and lower common tangents
  • Start with the rightmost point of the left hull and the leftmost point of the right hull
  • The upper common tangent can be found by:
      -scanning the left hull in a anti-clockwise direction untill slope decreases and untill its a tangent to left hull. 
      -scanning the right hull in clockwise direction untill its a tangent to right hull.
    
  • The lower common tangent can be found similarly by moving in opposite direction.
  • Merge the two hulls by removing the internal edges joining the tangent vertices.
(Edited: 2017-09-28)
* Sort the points based on x-coordinate's value * Keep dividing the points into two sets recursiveliy until there are three points in the set * Make convex hull of the three points * Merge the convex hull based on below steps * We can merge two convex hulls by finding upper and lower common tangents * Start with the rightmost point of the left hull and the leftmost point of the right hull * The upper common tangent can be found by: -scanning the left hull in a anti-clockwise direction untill slope decreases and untill its a tangent to left hull. -scanning the right hull in clockwise direction untill its a tangent to right hull. * The lower common tangent can be found similarly by moving in opposite direction. * Merge the two hulls by removing the internal edges joining the tangent vertices.
[ Next ]
X