BLI_convexhull_2d.hh File Reference

#include "BLI_math_vector_types.hh"
#include "BLI_span.hh"

Go to the source code of this file.

Functions
int	BLI_convexhull_2d (blender::Span< blender::float2 > points, int r_points[])
float	BLI_convexhull_aabb_fit_points_2d (blender::Span< blender::float2 > points)

Function Documentation

BLI_convexhull_2d()

int BLI_convexhull_2d	(	blender::Span< blender::float2 >	points,
		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). Points are ordered counter clockwise. The first point in r_points will be the lowest Y value (lowest (X, Y) when there are multiple Y aligned vertices). The polygons cross product is always positive (or zero).

Returns

The number of indices in r_points.

Note

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

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

BLI_convexhull_aabb_fit_points_2d()

float BLI_convexhull_aabb_fit_points_2d

(

blender::Span< blender::float2 >

points

)

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.

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