BLI_convexhull_2d.h File Reference

Go to the source code of this file.

Functions
int	BLI_convexhull_2d (const float(*points)[2], int points_num, int r_points[])
float	BLI_convexhull_aabb_fit_points_2d (const float(*points)[2], int points_num)

Function Documentation

BLI_convexhull_2d()

int BLI_convexhull_2d	(	const float(*)	points[2],
		int	points_num,
		int	r_points[] )

Extract 2D convex hull.

Parameters

points	An array of 2D points.
points_num	The number of points in points.
r_points	An array of the convex hull vertex indices (max is points_num). Vertices are ordered counter clockwise, the polygons cross product is always negative (or zero).

Returns

The number of indices in r_points.

Note

Performance is O(points_num.log(points_num)), same as qsort.

Definition at line 185 of file convexhull_2d.cc.

References b, BLI_assert, convexhull_2d_sorted(), copy_v2_v2(), i, MEM_freeN(), and MEM_malloc_arrayN().

Referenced by BLI_convexhull_aabb_fit_points_2d(), convexhull_2d_as_array(), blender::geometry::PackIsland::finalize_geometry_(), blender::ed::space_node::find_bounds_by_zone_recursive(), M_Geometry_convex_hull_2d(), and blender::geometry::rotate_inside_square().

BLI_convexhull_aabb_fit_points_2d()

float BLI_convexhull_aabb_fit_points_2d	(	const float(*)	points[2],
		int	points_num )

Returns

The best angle for fitting the points to an axis aligned bounding box.

Note

We could return the index of the best edge too if its needed.

Parameters

points

Arbitrary 2D points.

Definition at line 656 of file convexhull_2d.cc.

References angle(), BLI_assert, BLI_convexhull_2d(), convexhull_aabb_fit_hull_2d(), copy_v2_v2(), MEM_freeN(), and MEM_malloc_arrayN().

Referenced by convexhull_2d_aabb_fit_points_2d(), M_Geometry_box_fit_2d(), and blender::geometry::p_chart_rotate_fit_aabb().