Function VHConvexHull

src/openboardview/vectorhulls.cpp:150–194

}

std::vector<ImVec2> VHConvexHull(const std::vector<ImVec2> &points) {
	std::vector<ImVec2> hull;

	// There must be at least 3 points
	if (points.size() < 3) return hull;

	// Find the leftmost point
	int l = 0;
	for (size_t i = 1; i < points.size(); i++) {
		if (points[i].x < points[l].x) {
			l = i;
		}
	}

	// Start from leftmost point, keep moving counterclockwise
	// until reach the start point again.  This loop runs O(h)
	// times where h is number of points in result or output.
	int p = l, q;
	do {
		// Add current point to result
		//		hull[hpc] = CoordToScreen(points[p].x, points[p].y);
		hull.push_back({points[p].x, points[p].y});

		// Search for a point 'q' such that orientation(p, x,
		// q) is counterclockwise for all points 'x'. The idea
		// is to keep track of last visited most counterclock-
		// wise point in q. If any point 'i' is more counterclock-
		// wise than q, then update q.
		q = (p + 1) % points.size();
		for (size_t i = 0; i < points.size(); i++) {
			// If i is more counterclockwise than current q, then update q
			if (VHConvexHullOrientation(points[p], points[i], points[q]) == 2) {
				q = i;
			}
		}

		// Now q is the most counterclockwise with respect to p
		// Set p as q for next iteration, so that q is added to
		// result 'hull'
		p = q;

	} while ((p != l) && (hull.size() < points.size())); // While we don't come to first point

	return hull;
}

int VHTightenHull(ImVec2 hull[], int n, double threshold) {
	// theory: circle the hull, compare 3 points at a time, if the mid point is