根据成对点划分矩形

Question

如果您考虑上面的图像,您可以看到它们由一个大的矩形组成,该矩形通过用户定义的坐标对分解成较小的矩形(示例图像中的每一对都用不同的颜色标识).

我想要做的是通过仅定义连接来获得那些矩形的坐标.边缘被视为显式连接.订单无关紧要.

有没有人知道这样做的算法的名称(我确定有一个有花哨的名字!)或者有一些示例C#代码？我一直在努力尝试这样做一段时间,但我没有成功.又一次全数学失败了!

更新:
我想我会根据收到的评论快速更新这个问题.

线必须是直的,因此每对坐标将在一个轴上对齐
坐标必须从边缘或另一对的交叉点开始.第二个坐标必须以类似的方式结束.任何不开始/结束彼此连接的"孤儿"坐标都是非法的,我现在应该忽略它们,一旦我终于开始接触,就应该可以进行抢断.
虽然在这个例子中,所有的对都或多或少地整齐地划分了矩形,但实际情况并非如此,并且可能有许多线条创建许多尺寸的矩形.

第二次更新 - 它的工作原理:)
示例http://xthlegion.co.uk/images/dividerectangle3.png

Answer 1

您要计算的是已知的线段排列.(这不是一个特别好的名字,但它似乎是我们坚持的名字!)计算它:

找到交叉点集(两个线段相交或交叉的所有点).这可以通过Bentley-Ottmann算法计算.如果有n个线段和k个交叉点,则需要O((n + k)log n).(但是如果你只有几个线段,那么使用简单的O(n ²)算法可能会更好.)
通过一些额外的簿记,您可以记录每个交叉点处的入射边缘,从而计算与您的线段对应的平面直线图(PSLG).
将PSLG转换为四边数据结构.这需要两个步骤.首先,通过按角度排序入射到每个顶点的边来在数据结构中找到边缘边连接.
选择尚未连接到两个面的边,在未连接面上创建面,然后绕过该面的边界,依次将其连接到每个边.重复,直到每个边连接到两个面.

通常,这会导致除矩形以外的面(即使所有线段都是轴对齐且所有交叉点都具有整数坐标),但是在您的应用程序中可能不会发生这种情况,或者您可以丢弃非矩形面.