0

您会在平原上获得 4 个点的坐标。您需要用一条线将它们全部连接起来。线不得自行交叉。

你的策略是什么？

看图片例子

我的第一个直觉是将点组织为“左上”、“右上”、“左下”和“右下”并继续连接它们，使左上到左下，左下到下右，右下到右上，右上连接回左上。

这在大多数情况下都有效，但并非全部。有更好的策略吗？

谢谢你们。

4

2 回答 2

2

取三个点并形成一个顺时针三角形（将面积计算为两侧的叉积 - 如果为负，则交换两个顶点）。

取第四点并计算它与前者的每个（定向）边形成的三角形的面积。当你找到一个负区域时，在这一侧插入新的顶点，你就完成了。

可以证明你没有找到负区域，这意味着第四个点在三角形内部。您可以将其插入任何一侧。

在此处输入图像描述

if Area(P0, P1, P2) < 0
  Swap(P0, P1)

if Area(P0, P1, P3) < 0
  Solution: P0-P3-P1-P2
else if Area(P1, P2, P3) < 0
  Solution: P1-P3-P2-P0
else if Area(P2, P0, P3) < 0
  Solution: P2-P3-P0-P1
else
  Solution: P0-P1-P2-P3

更新

您可以使用所谓的轨迹方法来考虑它。假设您已经形成并定向了一个三角形，并希望插入第四个点。选择要插入的边，您可以在插入不会导致边交叉的所有位置绘制草图。

在此处输入图像描述

查看允许区域的形状，您观察到它是半平面与插入侧的并集，以及原始三角形。

三角形的三条支撑线将平面划分为 7 个区域。在任何区域内，您可以选择 1、2 或 3 种插入一侧的可能性（在图​​中，我们处于类型 1 的区域）。

这种明显做作的方法向您表明，您必须将第四点与三角形边进行比较（面积测试），并且在最坏的情况下，您无法避免与它们中的三个进行比较。

边界的形状告诉你需要使用什么样的方程，区域的数量暗示你必须执行多少次测试。

于 2015-02-01T15:46:22.097 回答
0

好吧，我还没有玩到足以 100% 确定的程度，但我认为以下方法会起作用：

  • 选择一个点。
  • 将其从其他点中减去以获得 3 个向量到其他 3 个点。
  • 使用点积和大小来确定每对向量之间的角度（3 对用于 3 个点）。
  • 将该点连接到其他两个向量之间夹角最大的点。
  • 将剩余的点也连接到这 2 个点。

到目前为止，我还没有想出一个失败的例子，但也许这只是因为它对我来说太晚了。:)

快速说明：

A点B = ax*bx + ay*by [ + az*bz ... ] = | 一个|| B |cos(angle_between_A_and_B)


为了使计算更有效：

首先，由于点积只给你从 0 到 180 度的角度，你可以通过检查哪个余弦更小或更负来检查哪个角度更大。这避免了需要执行反余弦。

这仍然需要您对每个幅度执行 sqrt 函数，因为点积给您 |A||B|cos(angle)，并且您必须除以 |A||B| 得到余弦。但是，通过一些启发式方法，我们也可以避免 sqrt。|一个| 和 |B| 必须始终是积极的。所以：

  • 如果一个点积是负的，另一个是正的，那么负的点积肯定有负余弦，另一个有正余弦，所以负的就是一个更大的角度。

  • 如果它们都是正数，那么您可以对点积进行平方，然后除以平方的幅度（x^2 + y^2 [+ z^2...] 没有 sqrt）。较小的结果将是较小的余弦，因此角度较大。

  • 如果点积都是负数，则执行相同的操作，但结果越大，余弦越小，因此角度越大。

于 2015-02-01T05:11:41.290 回答