谁能建议一个快速的三角形检测算法？
Can anyone suggest a quick triangle detection algorithm?
我有一些 Line 对象形式的数据（例如 Line1(start, end)，其中 start 和 end 是点对象形式的坐标）。有没有一种快速的方法可以遍历所有线条以查看它们是否形成三角形？我所说的快速是指比遍历所有 nC3 可能性更好的东西。
编辑：刚刚意识到我可能无法理解所有回复（我不是 Adrian Lamo）。请尝试解释 wrt Python。
Is there a quick way to go through all the lines to see if any of them form a triangle?
是的。假设您的积分是整数（或者可以很容易地转换为整数，因为它们具有固定的有效数字或类似数字）：
在这里为你创意：
- 制作两个可快速搜索的存储结构（例如
std::multimap<int>），一个用于端点的 x 和 y 坐标，将坐标与指向相应行的指针相关联
- 在第一个结构中，搜索具有相同x坐标的元素。这些是唯一的 "candidates" 作为三角形的角。搜索重复条目很快，因为您使用了适当的数据结构。
- 对于其中的每一个，验证它们是否实际上是一条边。如果不是，则丢弃。
- 对于每个剩余的角，验证两个 "opposite" 线端是否属于同一边。丢弃其他的。完成。
1）几何步长：将所有线段输入字典中，第一个端点为键，第二个端点为值。将有重复的键，因此您将保留一个值列表而不是单个值。原则上列表中不会有重复项（除非您两次输入相同的边）。
2) 拓扑步骤：对于字典中的所有条目P，考虑其列表中的所有元素对，设(Q, R)。查找 Q 并检查 R 是否属于 Q 的列表。如果是，则您找到了三角形 (P, Q, R).
根据对称性，将报告每个三角形的所有六个排列。您可以通过在词典意义上强制执行 P<Q<R 来避免这种情况。
我有一些 Line 对象形式的数据（例如 Line1(start, end)，其中 start 和 end 是点对象形式的坐标）。有没有一种快速的方法可以遍历所有线条以查看它们是否形成三角形？我所说的快速是指比遍历所有 nC3 可能性更好的东西。
编辑：刚刚意识到我可能无法理解所有回复（我不是 Adrian Lamo）。请尝试解释 wrt Python。
Is there a quick way to go through all the lines to see if any of them form a triangle?
是的。假设您的积分是整数（或者可以很容易地转换为整数，因为它们具有固定的有效数字或类似数字）：
在这里为你创意：
- 制作两个可快速搜索的存储结构（例如
std::multimap<int>），一个用于端点的 x 和 y 坐标，将坐标与指向相应行的指针相关联 - 在第一个结构中，搜索具有相同x坐标的元素。这些是唯一的 "candidates" 作为三角形的角。搜索重复条目很快，因为您使用了适当的数据结构。
- 对于其中的每一个，验证它们是否实际上是一条边。如果不是，则丢弃。
- 对于每个剩余的角，验证两个 "opposite" 线端是否属于同一边。丢弃其他的。完成。
1）几何步长：将所有线段输入字典中，第一个端点为键，第二个端点为值。将有重复的键，因此您将保留一个值列表而不是单个值。原则上列表中不会有重复项（除非您两次输入相同的边）。
2) 拓扑步骤：对于字典中的所有条目P，考虑其列表中的所有元素对，设(Q, R)。查找 Q 并检查 R 是否属于 Q 的列表。如果是，则您找到了三角形 (P, Q, R).
根据对称性，将报告每个三角形的所有六个排列。您可以通过在词典意义上强制执行 P<Q<R 来避免这种情况。