uikit - 如何平均细分封闭的CGPath？

Question

我有不确定数量的CGPath各种形状和大小的封闭元素，它们都包含一条凹贝塞尔曲线，如下图中的红色和蓝色形状。

将这些形状划分n为（大致）相等大小的区域的最简单和最有效的方法是什么？

Answer 1

你想要的是Delaunay triangulation。这是一个类似于您想要做的示例。它使用as3 库。这是一个 iOS 端口，应该可以帮助您：

https://github.com/czgarrett/delaunay-ios

Answer 2

我不太了解您想要实现的目标的背景以及限制是什么。例如，是否存在细分区域大小相等的硬性要求？

通常，性能问题的解决方案不是更快的算法，而是不同的方法，通常是以下一种或多种：

1. 预先计算值，或尽可能离线计算。比如说使用另一个服务器 API，它能够离线进行细分并为多个客户端缓存结果。您可以将计算后的结果作为位图提供，其中每种颜色都索引到您要显示的值表中。查找该值将是在触摸位置索引像素的简单问题。

2. 简化或近似解决方案。网格细分是否足够准确？在 500 x 6 = 3000 个细分中，每个区域只有大约 51 个正方形点，即大约 7x7 个点的区域。在那个尺寸下，用户不会注意到该区域是否完全准确。由于触摸分辨率，您可能最终需要聚合相邻区域。

3. 逐步细化。您通常不需要预先计算整个算法。算法通常以离散（通常是对称的）单元运行，这意味着您经常重复使用先前步骤中的信息。您可以预先计算第一步，然后使用后台线程逐步填充其余细节。您也可以推迟最终计算，直到触摸发生。在这一点上，最多一秒的延迟仍然是可以容忍的，或者在最坏的情况下，您可以在计算过程中显示动画。

您可以使用一些混合方法，并可能使用 Delaunay 三角剖分计算一个或两个级别，然后使用简单、快速的三角形细分来再计算两个级别。

根据所需的精度，如果不需要离散样本，则可以使用三角形各点之间的加权平均值来近似最终级别，即，如果触摸位于两点之间的中间，则选择它们之间的平均值。