#include <algorithm>
#include <cstdlib>
#include <cstring>
#include "MEM_guardedalloc.h"
#include "BLI_bounds.hh"
#include "BLI_convexhull_2d.h"
#include "BLI_math_vector.h"
#include "BLI_utildefines.h"
#include "BLI_strict_flags.h"

Classes
struct	AngleCanonical

struct	HullAngleStep

struct	HullAngleIter

Functions
Internal Math Functions
static float	sincos_rotate_cw_x (const float2 &sincos, const float2 &p)

static float	sincos_rotate_cw_y (const float2 &sincos, const float2 &p)

Main Convex-Hull Calculation
static float	is_left (const float p0[2], const float p1[2], const float p2[2])

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

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

Hull Angle Iteration
Step over all angles defined by a convex hull in order from 0-90 degrees, when angles are converted into their canonical form (see sincos_canonical).
static float2	sincos_canonical (const float2 &sincos)

static int	hull_angle_canonical_cmp (const AngleCanonical &a, const AngleCanonical &b)

static void	hull_angle_insert_ordered (HullAngleIter &hiter, HullAngleStep *insert)

static bool	convexhull_2d_angle_iter_step_on_axis (const HullAngleIter &hiter, HullAngleStep &hstep)

static HullAngleIter	convexhull_2d_angle_iter_init (const float(*points_hull)[2], const int points_hull_num)

static void	convexhull_2d_angle_iter_step (HullAngleIter &hiter)

Comupte AABB Fitting Angle (Optimized)
template<int Axis, int AxisSign>
static float	convexhull_2d_compute_extent_on_axis (const float(points_hull)[2], const int points_hull_num, const float2 &sincos, int index_p)

static float	convexhull_aabb_fit_hull_2d (const float(*points_hull)[2], int points_hull_num)

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 183 of file convexhull_2d.cc.

References b, BLI_assert, convexhull_2d_sorted(), copy_v2_v2(), float, MEM_freeN(), and MEM_mallocN.

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 655 of file convexhull_2d.cc.

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

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

◆ convexhull_2d_angle_iter_init()

static HullAngleIter convexhull_2d_angle_iter_init	(	const float(*)	points_hull[2],
		const int	points_hull_num )

static

Definition at line 447 of file convexhull_2d.cc.

References blender::math::abs(), HullAngleStep::angle, HullAngleIter::axis, convexhull_2d_angle_iter_step_on_axis(), hull_angle_insert_ordered(), AngleCanonical::index, HullAngleStep::index, HullAngleStep::index_max, LIKELY, blender::math::normalize_and_get_length(), HullAngleIter::points_hull, HullAngleIter::points_hull_num, and sincos_canonical().

Referenced by convexhull_aabb_fit_hull_2d().

◆ convexhull_2d_angle_iter_step()

static void convexhull_2d_angle_iter_step ( HullAngleIter & hiter )

static

Definition at line 530 of file convexhull_2d.cc.

References HullAngleStep::angle, HullAngleIter::axis_ordered, BLI_assert, convexhull_2d_angle_iter_step_on_axis(), hull_angle_canonical_cmp(), hull_angle_insert_ordered(), and HullAngleStep::next.

Referenced by convexhull_aabb_fit_hull_2d().

◆ convexhull_2d_angle_iter_step_on_axis()

static bool convexhull_2d_angle_iter_step_on_axis	(	const HullAngleIter &	hiter,
		HullAngleStep &	hstep )

static

Definition at line 424 of file convexhull_2d.cc.

References HullAngleStep::angle, BLI_assert, AngleCanonical::index, HullAngleStep::index, HullAngleStep::index_max, LIKELY, blender::math::normalize_and_get_length(), HullAngleIter::points_hull, HullAngleIter::points_hull_num, AngleCanonical::sincos, AngleCanonical::sincos_canonical, and sincos_canonical().

Referenced by convexhull_2d_angle_iter_init(), and convexhull_2d_angle_iter_step().

◆ convexhull_2d_compute_extent_on_axis()

template<int Axis, int AxisSign>

static float convexhull_2d_compute_extent_on_axis	(	const float(*)	points_hull[2],
		const int	points_hull_num,
		const float2 &	sincos,
		int *	index_p )

static

When using the rotating calipers, step one half of the caliper to a new index.

Note that this relies on points_hull being ordered CCW which BLI_convexhull_2d ensures.

Definition at line 562 of file convexhull_2d.cc.

References BLI_assert, count, sincos_rotate_cw_x(), and sincos_rotate_cw_y().

Referenced by convexhull_aabb_fit_hull_2d().

◆ convexhull_2d_sorted()

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

static

Definition at line 80 of file convexhull_2d.cc.

References BLI_assert, is_left(), and top.

Referenced by BLI_convexhull_2d().

◆ convexhull_aabb_fit_hull_2d()

static float convexhull_aabb_fit_hull_2d	(	const float(*)	points_hull[2],
		int	points_hull_num )

static

Definition at line 594 of file convexhull_2d.cc.

References angle(), HullAngleStep::angle, HullAngleIter::axis, HullAngleIter::axis_ordered, BLI_assert, convexhull_2d_angle_iter_init(), convexhull_2d_angle_iter_step(), convexhull_2d_compute_extent_on_axis(), FLT_MAX, AngleCanonical::index, blender::Bounds< T >::max, blender::Bounds< T >::min, and min.

Referenced by BLI_convexhull_aabb_fit_points_2d().

◆ hull_angle_canonical_cmp()

static int hull_angle_canonical_cmp	(	const AngleCanonical &	a,
		const AngleCanonical &	b )

static

Definition at line 357 of file convexhull_2d.cc.

References b.

Referenced by convexhull_2d_angle_iter_step(), and hull_angle_insert_ordered().

◆ hull_angle_insert_ordered()

static void hull_angle_insert_ordered	(	HullAngleIter &	hiter,
		HullAngleStep *	insert )

static

Definition at line 412 of file convexhull_2d.cc.

References HullAngleStep::angle, HullAngleIter::axis_ordered, hull_angle_canonical_cmp(), insert(), and HullAngleStep::next.

Referenced by convexhull_2d_angle_iter_init(), and convexhull_2d_angle_iter_step().

◆ is_left()

static float is_left	(	const float	p0[2],
		const float	p1[2],
		const float	p2[2] )

static

tests if a point is Left|On|Right of an infinite line. Input: three points P0, P1, and P2

Returns: > 0.0 for P2 left of the line through P0 and P1. = 0.0 for P2 on the line. < 0.0 for P2 right of the line.

Definition at line 75 of file convexhull_2d.cc.

Referenced by area_actionzone_get_rect(), area_split_invoke(), BKE_camera_multiview_model_matrix_scaled(), BKE_camera_multiview_view_matrix(), camera_stereo3d_model_matrix(), camera_stereo3d_shift_x(), convexhull_2d_sorted(), UI_panel_category_draw_all(), view3d_stereo3d_setup(), and view3d_stereo3d_setup_offscreen().

◆ sincos_canonical()

static float2 sincos_canonical ( const float2 & sincos )

static

Return a canonical version of sincos for the purpose of bounding box fitting, this maps any sincos to 0-1 range for both sin & cos.

Definition at line 304 of file convexhull_2d.cc.

References BLI_assert, and result.

Referenced by convexhull_2d_angle_iter_init(), and convexhull_2d_angle_iter_step_on_axis().

◆ sincos_rotate_cw_x()

static float sincos_rotate_cw_x	(	const float2 &	sincos,
		const float2 &	p )

static

Definition at line 44 of file convexhull_2d.cc.

Referenced by convexhull_2d_compute_extent_on_axis().

◆ sincos_rotate_cw_y()

static float sincos_rotate_cw_y	(	const float2 &	sincos,
		const float2 &	p )

static

Definition at line 49 of file convexhull_2d.cc.

Referenced by convexhull_2d_compute_extent_on_axis().

Classes

Functions

Function Documentation

◆ BLI_convexhull_2d()

◆ BLI_convexhull_aabb_fit_points_2d()

◆ convexhull_2d_angle_iter_init()

◆ convexhull_2d_angle_iter_step()

◆ convexhull_2d_angle_iter_step_on_axis()

◆ convexhull_2d_compute_extent_on_axis()

◆ convexhull_2d_sorted()

◆ convexhull_aabb_fit_hull_2d()

◆ hull_angle_canonical_cmp()

◆ hull_angle_insert_ordered()

◆ is_left()

◆ sincos_canonical()

◆ sincos_rotate_cw_x()

◆ sincos_rotate_cw_y()