给定一个凸四边形的 4 线方程，我怎样才能找到 4 个角的坐标？

Question

我有四个直线方程y=mx+b，有6个交点

已知这些线构成了一个凸四边形。

如何找出四边形的哪四个交点（最好按顺序）？

Answer 1

求解每个线对的线性方程组

  y = m[i] * x + b[i]
  y = m[j] * x + b[j]

其中m[i], b[i]是第i行的系数，求交点(x,y)。

如果恰好有6条交点（无平行线，无退化），则每条线有3个交点排成一行。两个交点是"outer"，一个（中间）是"inner"，所以有三个内点和三个外点。

似乎凸四边形总是包含所有三个内点，所以我们可以分离内点，得到对应的第四个点。

例如指定线为A,B,C,D，交点AB,AC,CD在内侧，则第四点为交点BD（B和D在交点列表中是唯一的）

P.S。请注意，线方程形式 y=mx+b 并不适用于所有可能的线（不适用于垂直线），因此最好使用 more general form，如 A*x + B*y + C = 0 或其他。

Answer 2

第一个凹四边形：

第6个交点应该也在1)我只是忘记画在那里了。

计算所有交点并将它们配对成直线
```
l1: p2,p5,p6
l2: p1,p4,p6
l3: p1,p2,p3
l4: p3,p4,p5
```
l表示直线，p表示交点
判断点是边还是中间

所以中间点是如果你从它所属的线的每一侧得到另一个点。换句话说，如果您将点转换为其参数位置（或距某个起点的距离），则中点位于其他两点距离之间。 parameter/distance 你在交集计算时直接获得，但如果你不这样做，你可以使用这个：
```
t(p) = dot(p-A,B-A)
```
其中 A,B 是直线端点，p 是查询的交点，t(p) 是它的标量 "distance" 来自 A.

所以找出哪些点只是边缘e，哪些是中间m:
```
l1: e2,e5,m6
l2: e1,e4,m6
l3: e1,m2,e3
l4: e3,m4,e5
```
现在如果任何点至少有一次是中间那么它是部分中间的，如果它只是边缘那么它是边缘如果它只是中间那么它是中间的：
```
edge:    p1,p3,p5
partial: p2,p4
middle:  p6
```
构造多边形

所以我们必须使用边缘点。我们跳过部分点（因为它们位于已使用的线上），最后我们还使用中间点。我们知道我们的多边形将是：
```
(p1,p3,p5) + (p6)
```
现在我们需要找到凹的中点p6会去哪里。共有 3 种组合：
```
e1,m6,e3,e5
e1,e3,m6,e5
e1,e3,e5,m6
```
我们知道 m6 属于 l1,l2 并且 l1,l2 也有 p2,p5,p1,p4 其中只有边缘点：e1,e5 所以 m6 将放在它们之间，因此正确的解决方案是：
```
e1,e3,e5,m6
```

现在凸四边形：

如果我们利用 #1,#2 那么为了形成凸四边形我们必须使用中间点和部分中间点并选择一个纯边缘点。 Select 不属于纯中点线的。所以我们必须使用：

    (p2,p4) + (m6) + one_from(e1,e3,e5)

m6 不属于 l3,l4 所以我们需要找到属于两者的边 e3 所以

    (p2,p4) + (m6) + (e3)

现在我们只需要找出顺序即可。中间点和边缘点不会靠近它们，所以你有 2 个解决方案：

    p2,m6,p4,e3
    p2,e3,p4,m6

两者都是正确的它们只是自身的反转（不同的多边形缠绕规则）所以你可以根据z任意两个相邻顶点的叉积坐标选择你需要的那个。

Given 4 line equation of a convex quadrilateral, how can I find coordinate of 4 corner?