32f9b65cc5
Since [0], removing degenerate points at the beginning of the hull
would re-order points so the last were moved to the beginning.
While this isn't an error, having the resulting hull *sometimes*
re-ordering it's result based on internal error correction isn't ideal.
Document that the first point in the hull has the lowest Y value and
update tests to ensure this.
Also correct the doc-string regarding the hulls cross-product
and tests this is working as documented.
[0]: 87f9fd8fb3
39 lines
1.1 KiB
C++
39 lines
1.1 KiB
C++
/* SPDX-FileCopyrightText: 2023 Blender Authors
|
|
*
|
|
* SPDX-License-Identifier: GPL-2.0-or-later */
|
|
|
|
#pragma once
|
|
|
|
#include "BLI_math_vector_types.hh"
|
|
#include "BLI_span.hh"
|
|
|
|
/** \file
|
|
* \ingroup bli
|
|
*/
|
|
|
|
/**
|
|
* Extract 2D convex hull.
|
|
*
|
|
* \param points: An array of 2D points.
|
|
* \param points_num: The number of points in points.
|
|
* \param 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).
|
|
*
|
|
* \return The number of indices in `r_points`.
|
|
*
|
|
* \note Performance is `O(points_num.log(points_num))`, same as `qsort`.
|
|
*/
|
|
int BLI_convexhull_2d(blender::Span<blender::float2> points, int r_points[/*points_num*/]);
|
|
|
|
/**
|
|
* \return 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.
|
|
*
|
|
* \param points: Arbitrary 2D points.
|
|
*/
|
|
float BLI_convexhull_aabb_fit_points_2d(blender::Span<blender::float2> points);
|