Виктор Asked:2025-01-15 05:37:49 +0800 CST2025-01-15 05:37:49 +0800 CST 2025-01-15 05:37:49 +0800 CST 使用多个点的程序曲面生成 772 给定：一个三维世界，您需要生成一个任意形状的平面（厚度为一个单位）图形。可以有任意数量的点，但不能少于三个。在这些点之间，填充所有点之间的线段内的所有单元格的空间。 上图中的一个例子。 红细胞是点。橙色 - 点之间需要填充的空间（与红线接触也算）。我用java编程语言编写代码，但可以用伪代码给出示例或提示，或者给出如何实现的想法。提前致谢！ геометрия 1 个回答 Voted Best Answer Stanislav Volodarskiy 2025-01-15T06:18:46+08:002025-01-15T06:18:46+08:00 我们将把所有点投影到 XY 平面上。在其中，我们将构造一组点或多边形的某种三角剖分。有关示例，请参阅Delaunay 三角剖分。从三角测量中，我们选择所有三角形。任务简化为填充一个三角形。 现在，单个平面穿过三维空间中的三个点。对于空间中的任意点，都可以计算出该点是在平面之上、在平面上还是在平面之下。如果单位立方体的一些顶点位于平面之上而一些顶点位于平面之下，则单位立方体与平面相交。从三角形的任意顶点开始，您可以使用广度优先搜索来确定与三角形平面相交的所有立方体。在广度优先搜索中，需要添加立方体在XY上的投影与三角形的投影相交的条件。 该算法的运行时间为 NlogN + K，其中N是点的数量，K是落入结果的立方体的数量。 PS如果您熟悉计算几何和图算法，那么我的解释不会告诉您任何新内容。如果没有，你会很难过。
我们将把所有点投影到 XY 平面上。在其中，我们将构造一组点或多边形的某种三角剖分。有关示例，请参阅Delaunay 三角剖分。从三角测量中，我们选择所有三角形。任务简化为填充一个三角形。
现在，单个平面穿过三维空间中的三个点。对于空间中的任意点，都可以计算出该点是在平面之上、在平面上还是在平面之下。如果单位立方体的一些顶点位于平面之上而一些顶点位于平面之下，则单位立方体与平面相交。从三角形的任意顶点开始，您可以使用广度优先搜索来确定与三角形平面相交的所有立方体。在广度优先搜索中，需要添加立方体在XY上的投影与三角形的投影相交的条件。
该算法的运行时间为 NlogN + K，其中N是点的数量，K是落入结果的立方体的数量。
PS如果您熟悉计算几何和图算法，那么我的解释不会告诉您任何新内容。如果没有，你会很难过。