如何判断四条直线是否构成一个四边形，是凸四边形还是凹四边形？

Question

在 C++ 中，如何检测任意给定的四条线是否构成四边形（凸或凹），以及它们是否构成多个四边形？

例如，这样：

有这样一个：

还有这个：

我已经阅读了this和this，但我的主要问题是检测凹四边形，特别是如果我不知道这些线是否形成闭合形状。

我也尝试这样做（我自己的代码，以及一些同学）这个，但它检测到几乎总是有一个四边形，即使没有任何

Answer 1

首先，凹四边形的存在意味着其内接凸四边形的存在。您的示例演示了这一点，并且它通常适用于 4 行的情况。

要测试是否存在凸四边形，请检查两个条件：

您可以通过计算所有 6 对两条线的交点来检查三条线是否相交于一个点，然后将该交点的 x/y 值插入到其他两条线中以查看该点是否也在同一点上那些行。如果这个条件不成立，那么就不存在四边形、凸面或凹面。

如果该条件成立，您可以检查是否没有两条线平行。如果这个条件成立，那么在你的平面上的某个地方就存在一个凹四边形。如果不成立，仍然可能存在四边形，您只需要再做一些检查即可。

首先，如果两条平行线实际上是同一条线，那么实际上只有 3 条不同的线，因此不存在四边形。其次，另外两条不平行的线在两条平行线之间相交，也没有四边形。否则，存在一个凸四边形。要测试这一点，只需再次计算交点，然后检查该点是否位于两条线的同一“侧”。

现在，凹四边形怎么样？在平行线的情况下，不会有凹四边形。否则，我相信如果有一个凸四边形，那么也会有一个凹四边形伴随它，它将与凸四边形共享一个角。也不可能同时有两个凹四边形。

总而言之，这可以让您计算平面中四边形的总数。