Question
Can somebody post a solution for this? Preferably in C
http://www.chegg.com/homework-help/Introduction-to-the-Design-and-Analysis-of-Algorithms-3rd-edition-chapter-5.5-problem-10E-solution-9780132316811
Explanation / Answer
#include "QuickHull.h" #include "ExLib_Topology.h" #include "ExLib_FloatDataAccessor.h" #include #include #include #include #include #include #include "OutsideSet.h" void QuickHull::ConvexHull(const FloatDataAccessor & point_set, WingedTriangleMesh & rtn_hull) { /* 3.9.2 - The Quickhill Algorithm Procedure: -> Obtain bounding box to point set as first approximination of convex hull, -> by finding the 4 extreme points in each direction (in 2D). -> These points must lie in convex hull since they are extreme. -> Points lying inside this approximation hull cannot be on convex hull, remove from further consideration. -> Refine approximination with points outside of current hull: -> For each edge: -> Find point farthest away in the direction perpendicular to the edge. Add it to the hull. -> Repeatedly refine until no more points. Robustness Considerations: Problem: -> Initial hull may not always be quad. -> May have triangle if same point is extreme for two directions. -> May have a degenerate hull if two points are the extreme for two directions. -> May need to break ties between vertices for refining hull. -> Select the one projecting farthest along the parallel of the edge. http://algolist.manual.ru/maths/geom/convhull/qhull3d.php Algorithm Implementation Details: -> Maximal Simplex as Starting Point -> Will be a tetrahedron. Otherwise, return as degeneracy. -> For each triangle in convex hull, -> Define "OutsideSet" as the set of points outside of that face. -> Signed distance from the face is greater than 0. -> Divide points into OutsideSets. -> Invariant: -> The ordering of OutsideSets and Triangles in WingedTriangleMesh's storage always match. Preserved by Mimicking WingedTriangleMesh's removal scheme when removing OutsideSets: -> WingedTriangleMesh's fast array element removal: -> If element is not at end of array, -> Move last element into removed element's place. */ //Calculate Maximal Simplex as Starting Point. int simplex_dimension = MaximalSimplex(point_set, rtn_hull); if (simplex_dimension < 4) { //DEGENERATE HULL. return; } //Construct Outside Sets typedef std::vector OUTSIDE_SETS; OUTSIDE_SETS outside_sets; for (unsigned int i = 0; i Place in that face's Outside Set. for (unsigned int i = 0; i GetEdgeSrc(1); unsigned int c_index = rtn_hull[j]->GetEdgeSrc(2); if (i == a_index || i == b_index || i == c_index) continue; //DEGENERATE TRIANGLE Eigen::Vector3f & a = VEC3(point_set[rtn_hull[j]->GetEdgeSrc(0)]); Eigen::Vector3f & b = VEC3(point_set[rtn_hull[j]->GetEdgeSrc(1)]); Eigen::Vector3f & c = VEC3(point_set[rtn_hull[j]->GetEdgeSrc(2)]); float distance = DistanceToTriangle(a, b, c, current_point); if (distance > 1e-10) //Robustness epsilon { outside_sets[j]->Insert(i, distance); break; } } } //Main Loop int pass = 0; for (unsigned int i = 0; i Size() == 0) { ++i; continue; } //Calculate Horizon of Hull from point of view of "farthest point" in this Outside Set. // -> The triangles in "visible_triangles" will be removed and replaced. // -> With a cone from "farthest point" to Hull horizon. // Invariant: // -> Horizon Edges will always form a counter-clockwise loop. unsigned int farthest = outside_sets[i]->GetFarthest(); std::vector horizon_edges; std::set visited_triangles; CalculateHorizon(VEC3(point_set[farthest]), point_set, outside_sets[i]->GetTriangle(), horizon_edges, visited_triangles); //Create new triangles in the form of a cone. // -> Cone Point is Farthest point in this OutsideSet. // -> The circular base is made from the horizon edges. std::vector new_triangles; for (unsigned int j = 0; j 0, "Visited Triangles empty."); unsigned int min_modified_index = INT_MAX; //Removal of Visible Triangles // -> The triangles enclosed by the horizon edge loop are removed. // -> Also remove the triangle's corresponding OutsideSet. // -> Mimick WingedTriangleMesh's removal scheme to preserve order correspondance // -> Between WingedTriangles and OutsideSets. for (std::set::iterator it = visited_triangles.begin(); it != visited_triangles.end(); ++it) { WingedTriangle * to_remove = *it; unsigned int triangle_index = to_remove->GetIndexInMesh(); if (triangle_index GetTriangle() == *it, "Mismatch set and triangle"); //Save the points in each OutsideSet to be deleted. // -> Later redivide them // -> Among new triangles in the Cone. for (unsigned int j = 0; j Size(); ++j) { outside_set_union.push_back((*to_remove_set)[j]); } //Delete OutsideSet if (to_remove->GetIndexInMesh() != outside_sets.size()-1) { delete to_remove_set; outside_sets[to_remove->GetIndexInMesh()] = outside_sets.back(); } else { delete outside_sets[to_remove->GetIndexInMesh()]; } outside_sets.pop_back(); //Delete Triangle rtn_hull.RemoveTriangle(to_remove); } //Add New Triangles and Corresponding OutsideSets. OUTSIDE_SETS new_outside_sets; for (unsigned int j = 0; j GetIndexInMesh(), "Mismatch Occurred"); } for (unsigned int j = 0; j