Blender  V3.3
Functions
BLI_convexhull_2d.h File Reference

Go to the source code of this file.

Functions

int BLI_convexhull_2d_sorted (const float(*points)[2], int n, int r_points[])
 
int BLI_convexhull_2d (const float(*points)[2], int n, int r_points[])
 
float BLI_convexhull_aabb_fit_hull_2d (const float(*points_hull)[2], unsigned int n)
 
float BLI_convexhull_aabb_fit_points_2d (const float(*points)[2], unsigned int n)
 

Function Documentation

◆ BLI_convexhull_2d()

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

A.M. Andrew's monotone chain 2D convex hull algorithm.

Parameters
pointsAn array of 2D points.
nThe number of points in points.
r_pointsAn array of the convex hull vertex indices (max is n). must be allocated as n * 2 because of how its used internally, even though the final result will be no more than n in size.
Returns
the number of points in r_points.

Definition at line 162 of file convexhull_2d.c.

References BLI_convexhull_2d_sorted(), float(), MEM_freeN, MEM_mallocN, pointref_cmp_yx(), and PointRef::pt.

Referenced by BLI_convexhull_aabb_fit_points_2d().

◆ BLI_convexhull_2d_sorted()

int BLI_convexhull_2d_sorted ( const float(*)  points[2],
int  n,
int  r_points[] 
)

A.M. Andrew's monotone chain 2D convex hull algorithm.

Parameters
pointsAn array of 2D points presorted by increasing x and y-coords.
nThe number of points in points.
r_pointsAn array of the convex hull vertex indices (max is n).
Returns
the number of points in r_points.

Definition at line 42 of file convexhull_2d.c.

References is_left(), and top.

Referenced by BLI_convexhull_2d().

◆ BLI_convexhull_aabb_fit_hull_2d()

float BLI_convexhull_aabb_fit_hull_2d ( const float(*)  points_hull[2],
unsigned int  n 
)
Returns
The best angle for fitting the convex hull to an axis aligned bounding box.

Intended to be used with BLI_convexhull_2d

Parameters
points_hullOrdered hull points (result of BLI_convexhull_2d mapped to a contiguous array).
Note
we could return the index of the best edge too if its needed.

Definition at line 204 of file convexhull_2d.c.

References blender::compositor::area(), atan2f, copy_v2_v2(), max, max_ff(), min, min_ff(), mul_v2_v2_cw(), normalize_v2(), and sub_v2_v2v2().

Referenced by BLI_convexhull_aabb_fit_points_2d().

◆ BLI_convexhull_aabb_fit_points_2d()

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

Wrap BLI_convexhull_aabb_fit_hull_2d and do the convex hull calculation.

Parameters
pointsarbitrary 2d points.

Definition at line 251 of file convexhull_2d.c.

References angle(), BLI_convexhull_2d(), BLI_convexhull_aabb_fit_hull_2d(), copy_v2_v2(), float(), MEM_freeN, and MEM_mallocN.

Referenced by bm_face_array_uv_rotate_fit_aabb(), and p_chart_rotate_fit_aabb().