-- Sep 22 In-Class Exercise
We can find convex hull of data points using divide and conquer approach.
We sort the points according to their x-coordinate, find convex hulls of each set of points and merge the results to get the convex hull of all points.
Given: Points (0,0), (1,0.5), (1/-0.5), (3,5), (3,-5) and (4,0)
Splitting them based on x-coordinates, we get 4 sets: {0,0}, {(1,0.5),(1,-0.5)}, {(3,5), (3,-5)} and {4,0}
Now, to merge them back together, we look through the set of points to find minimal and maximal y-values
From sets {(1,0.5),(1,-0.5)} and {(3,5), (3,-5)}, we connect the maximal y-values from points (1,0.5) and (3,5). Then we connect to point (0,0) and see find cross-product of the edges to check the direction of movement to find the next point.
We have to move clockwise and so we disregard the edge from (3,5) to(1,0.5) and instead use the line from (3,5) to (0,0) as an edge of the convex hull.
Similarly, for minimal y-value case, we connect points (3,-5) to (1,-0.5) and (0,0) and realize we need to move anti-clockwise and so we eliminate the edge involving the former point.
In the same way, we connect (4,0) to the set {(3,5), (3,-5)}
This gives us the convex hull with points (0,0), (3,5), (4,0) and (3,-5)
We can find convex hull of data points using '''divide and conquer''' approach.
We sort the points according to their x-coordinate, find convex hulls of each set of points and merge the results to get the convex hull of all points.
Given: Points (0,0), (1,0.5), (1/-0.5), (3,5), (3,-5) and (4,0)
Splitting them based on x-coordinates, we get 4 sets: {0,0}, {(1,0.5),(1,-0.5)}, {(3,5), (3,-5)} and {4,0}
Now, to merge them back together, we look through the set of points to find minimal and maximal y-values
From sets {(1,0.5),(1,-0.5)} and {(3,5), (3,-5)}, we connect the maximal y-values from points (1,0.5) and (3,5). Then we connect to point (0,0) and see find cross-product of the edges to check the direction of movement to find the next point.
We have to move clockwise and so we disregard the edge from (3,5) to(1,0.5) and instead use the line from (3,5) to (0,0) as an edge of the convex hull.
Similarly, for minimal y-value case, we connect points (3,-5) to (1,-0.5) and (0,0) and realize we need to move anti-clockwise and so we eliminate the edge involving the former point.
In the same way, we connect (4,0) to the set {(3,5), (3,-5)}
This gives us the convex hull with points (0,0), (3,5), (4,0) and (3,-5)
((resource:AI.jpeg|Resource Description for AI.jpeg))