Blender  V3.3
Classes
convexhull_2d.c File Reference
#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_convexhull_2d.h"
#include "BLI_math.h"
#include "BLI_strict_flags.h"
#include "BLI_utildefines.h"

Go to the source code of this file.

Classes

struct  PointRef
 

Functions

Main Convex-Hull Calculation
static float is_left (const float p0[2], const float p1[2], const float p2[2])
 
int BLI_convexhull_2d_sorted (const float(*points)[2], const int n, int r_points[])
 
static int pointref_cmp_yx (const void *a_, const void *b_)
 
int BLI_convexhull_2d (const float(*points)[2], const int n, int r_points[])
 
Utility Convex-Hull Functions
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().

◆ 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 37 of file convexhull_2d.c.

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

◆ pointref_cmp_yx()

static int pointref_cmp_yx ( const void a_,
const void b_ 
)
static

Definition at line 141 of file convexhull_2d.c.

References Freestyle::a, and usdtokens::b().

Referenced by BLI_convexhull_2d().