37 static float is_left(
const float p0[2],
const float p1[2],
const float p2[2])
39 return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1]);
53 float xmin = points[0][0];
54 for (i = 1; i < n; i++) {
55 if (points[i][0] != xmin) {
62 if (minmax == n - 1) {
63 r_points[++
top] = minmin;
64 if (points[minmax][1] != points[minmin][1]) {
66 r_points[++
top] = minmax;
74 xmax = points[n - 1][0];
75 for (i = n - 2; i >= 0; i--) {
76 if (points[i][0] != xmax) {
83 r_points[++
top] = minmin;
85 while (++i <= maxmin) {
87 if (
is_left(points[minmin], points[maxmin], points[i]) >= 0 && i < maxmin) {
93 if (
is_left(points[r_points[
top - 1]], points[r_points[
top]], points[i]) > 0.0f) {
103 if (maxmax != maxmin) {
104 r_points[++
top] = maxmax;
109 while (--i >= minmax) {
111 if (
is_left(points[maxmax], points[minmax], points[i]) >= 0 && i > minmax) {
117 if (
is_left(points[r_points[
top - 1]], points[r_points[
top]], points[i]) > 0.0f) {
123 if (points[i][0] == points[r_points[0]][0] && points[i][1] == points[r_points[0]][1]) {
130 if (minmax != minmin) {
131 r_points[++
top] = minmin;
146 if (
a->pt[1] >
b->pt[1]) {
149 if (
a->pt[1] <
b->pt[1]) {
153 if (
a->pt[0] >
b->pt[0]) {
156 if (
a->pt[0] <
b->pt[0]) {
165 float(*points_sort)[2] =
MEM_mallocN(
sizeof(*points_sort) * (
size_t)n, __func__);
167 int points_hull_num, i;
169 for (i = 0; i < n; i++) {
170 points_ref[i].
pt = points[i];
176 for (i = 0; i < n; i++) {
177 memcpy(points_sort[i], points_ref[i].
pt,
sizeof(
float[2]));
183 points_map = (
int *)points_sort;
184 for (i = 0; i < points_hull_num; i++) {
185 points_map[i] = (int)((
const float(*)[2])points_ref[r_points[i]].
pt - points);
188 memcpy(r_points, points_map, (
size_t)points_hull_num *
sizeof(*points_map));
193 return points_hull_num;
206 unsigned int i, i_prev;
207 float area_best = FLT_MAX;
211 for (i = 0; i < n; i++) {
212 const float *ev_a = points_hull[i];
213 const float *ev_b = points_hull[i_prev];
219 float min[2] = {FLT_MAX, FLT_MAX},
max[2] = {-FLT_MAX, -FLT_MAX};
223 for (j = 0; j < n; j++) {
234 if (
area > area_best) {
239 if (
area < area_best) {
248 return (area_best != FLT_MAX) ?
atan2f(dvec_best[0], dvec_best[1]) : 0.0f;
258 index_map =
MEM_mallocN(
sizeof(*index_map) * n * 2, __func__);
262 if (points_hull_num) {
263 float(*points_hull)[2];
266 points_hull =
MEM_mallocN(
sizeof(*points_hull) * (
size_t)points_hull_num, __func__);
267 for (j = 0; j < points_hull_num; j++) {
268 copy_v2_v2(points_hull[j], points[index_map[j]]);
typedef float(TangentPoint)[2]
MINLINE float max_ff(float a, float b)
MINLINE float min_ff(float a, float b)
MINLINE void mul_v2_v2_cw(float r[2], const float mat[2], const float vec[2])
MINLINE void copy_v2_v2(float r[2], const float a[2])
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
MINLINE float normalize_v2(float r[2])
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble top
Read Guarded memory(de)allocation.
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
static int pointref_cmp_yx(const void *a_, const void *b_)
float BLI_convexhull_aabb_fit_points_2d(const float(*points)[2], unsigned int n)
int BLI_convexhull_2d_sorted(const float(*points)[2], const int n, int r_points[])
float BLI_convexhull_aabb_fit_hull_2d(const float(*points_hull)[2], unsigned int n)
int BLI_convexhull_2d(const float(*points)[2], const int n, int r_points[])
static float is_left(const float p0[2], const float p1[2], const float p2[2])
void(* MEM_freeN)(void *vmemh)
void *(* MEM_mallocN)(size_t len, const char *str)
static void area(int d1, int d2, int e1, int e2, float weights[2])
static const pxr::TfToken b("b", pxr::TfToken::Immortal)