在Javascript中检测墙壁（线条）列表的独特房间（多边形）

Question

我用 JavaScript 编写了一个脚本来创建点（顶点）和墙（连接这些顶点的线）。

我的下一个实现现在要求我访问该墙阵列并找到唯一的多边形来检测它们是否创建房间。

数据已经以将顶点添加到顶点数组中的方式进行组织，并且墙具有“v1”和“v2”属性，指示它们所属的顶点。 “v1”和“v2”可以被认为是开始和结束，但是墙是在混乱中创建的，这意味着它们可以按任何顺序完成，并且很多墙可以具有相同的 v2 顶点。

我制作了一个示例数据以及该数据如何在屏幕上“绘制”。我还手动对图像进行了着色，以演示什么是房间，但我正在努力寻找一种将其纳入算法的方法。找到了一些数学例子，但无法复制正确的结果。

示例（具有 2 个数组的对象 - 1 个用于顶点，1 个用于墙壁）。顶点获得一个 id，该 id 被墙用来引用。如果以任何方式（v1 或 v2，v1 到 v1，v1 到 v2，v2 到 v1 或 v2 到 v2）共享相同 id 的顶点，我认为 2 堵墙是相连的。

{
    "vertices":
    [
        {"id":1,"x":401.9999999999999,"y":250.99999999999994},
        {"id":2,"x":531.9999999999999,"y":371.99999999999994},
        {"id":3,"x":595.9999999999999,"y":555.9999999999999},
        {"id":4,"x":781.9999999999998,"y":713.9999999999999},
        {"id":5,"x":1036.9999999999998,"y":713.9999999999999},
        {"id":6,"x":781.9999999999998,"y":828.9999999999998},
        {"id":7,"x":908.9999999999998,"y":885.9999999999998},
        {"id":8,"x":974.9999999999998,"y":830.9999999999998},
        {"id":9,"x":1146.9999999999998,"y":583.9999999999999},
        {"id":10,"x":1144.9999999999998,"y":808.9999999999998},
        {"id":11,"x":169.92891649440006,"y":347.2844582472},
        {"id":12,"x":636.5982877164412,"y":153.66702470084715},
        {"id":13,"x":720.9289164943999,"y":266.2844582472},
        {"id":14,"x":362.9289164944,"y":352.2844582472},
        {"id":15,"x":478.9289164944,"y":434.28445824719995},
        {"id":16,"x":478.9289164944,"y":581.2844582472},
        {"id":17,"x":245.92891649440006,"y":615.2844582472},
        {"id":18,"x":223.36547524631717,"y":460.65852263533225},
        {"id":19,"x":100.92891649440011,"y":553.2844582472},
        {"id":20,"x":185.92891649440006,"y":742.2844582472},
        {"id":21,"x":8.928916494400113,"y":742.2844582472},
        {"id":22,"x":-75.07108350559986,"y":657.2844582472},
        {"id":23,"x":-75.07108350559986,"y":484.28445824719995},
        {"id":24,"x":1.928916494400113,"y":365.2844582472},
        {"id":25,"x":726.5565877032943,"y":510.58901297277316},
        {"id":26,"x":837.9289164943999,"y":370.2844582472},
        {"id":27,"x":837.9289164943999,"y":192.2844582472},
        {"id":28,"x":742.9289164943999,"y":126.2844582472},
        {"id":29,"x":747.9289164943999,"y":202.2844582472},
        {"id":30,"x":747.9289164943999,"y":293.2844582472},
        {"id":31,"x":344.5320692909314,"y":670.9549979947822},
        {"id":32,"x":531.9289164943999,"y":631.2844582472},
        {"id":33,"x":691.6286174279545,"y":637.2329115785851},
        {"id":34,"x":550.8501387912459,"y":802.9594750369934},
        {"id":35,"x":287.9289164944,"y":802.9594750369934},
        {"id":36,"x":76.92891649440011,"y":861.2844582471998},
        {"id":37,"x":875.9289164943999,"y":560.2844582472},
        {"id":38,"x":680.9807883325162,"y":379.5585897817683}
    ],
    "walls":
    [
        {"id":1,"v1":1,"v2":2},
        {"id":2,"v1":3,"v2":2},
        {"id":4,"v1":4,"v2":5},
        {"id":5,"v1":4,"v2":6},
        {"id":6,"v1":6,"v2":7},
        {"id":7,"v1":8,"v2":5},
        {"id":8,"v1":9,"v2":5},
        {"id":9,"v1":10,"v2":5},
        {"id":10,"v1":1,"v2":11},
        {"id":11,"v1":1,"v2":12},
        {"id":12,"v1":2,"v2":13},
        {"id":13,"v1":12,"v2":13},
        {"id":14,"v1":14,"v2":15},
        {"id":15,"v1":15,"v2":16},
        {"id":16,"v1":16,"v2":17},
        {"id":17,"v1":17,"v2":18},
        {"id":18,"v1":18,"v2":14},
        {"id":19,"v1":11,"v2":19},
        {"id":20,"v1":19,"v2":20},
        {"id":21,"v1":20,"v2":21},
        {"id":22,"v1":21,"v2":22},
        {"id":23,"v1":22,"v2":23},
        {"id":24,"v1":23,"v2":24},
        {"id":25,"v1":24,"v2":11},
        {"id":26,"v1":3,"v2":25},
        {"id":27,"v1":25,"v2":26},
        {"id":28,"v1":26,"v2":27},
        {"id":29,"v1":27,"v2":28},
        {"id":30,"v1":29,"v2":30},
        {"id":31,"v1":30,"v2":13},
        {"id":32,"v1":29,"v2":12},
        {"id":33,"v1":12,"v2":28},
        {"id":34,"v1":20,"v2":31},
        {"id":35,"v1":31,"v2":32},
        {"id":36,"v1":32,"v2":3},
        {"id":37,"v1":3,"v2":33},
        {"id":38,"v1":4,"v2":33},
        {"id":39,"v1":33,"v2":34},
        {"id":40,"v1":34,"v2":35},
        {"id":41,"v1":35,"v2":31},
        {"id":42,"v1":35,"v2":36},
        {"id":43,"v1":36,"v2":21},
        {"id":44,"v1":33,"v2":37},
        {"id":45,"v1":37,"v2":26},
        {"id":46,"v1":25,"v2":38}
    ]
}

理想情况下，它会生成这些房间（对涉及的墙进行分组）：

在这种情况下，将有 9 个房间，忽略没有尽头或分支的墙。任何内墙都会形成自己的多边形，它本身就是一个房间，因此深灰色多边形表示的区域将是一个房间，而浅灰色多边形表示的区域将是另一个房间。深灰色多边形的面积不应属于浅灰色多边形。

Answer 1

想象你站在墙边。你伸出右手去碰墙壁。然后你开始走路，始终将手放在墙上。当你到达一个非常点时，你会选择离开该顶点的最左边的墙，从你来的方向看。因为这是唯一一堵你可以在手不离开墙上的情况下走到的墙；任何其他墙都位于您到达的墙和相对于该墙的最左边的出墙形成的角度后面。继续这样做，直到到达起始点，即手从同一侧触摸同一面墙。

然后分析你观察到的情况。您可能遇到过两次墙壁，每一面各一次。在这种情况下，该墙不包含任何区域。您可以移除这些墙壁，这可能会导致您的墙壁环路分裂成多个环路。之后，您可能会发现您多次访问过的顶点，每次遇到时都有一对不同的墙。这将是循环中的一个关键点，多个房间在一个点相遇。同样，您可以在这个顶点分割循环，始终谈论一个传出边缘和之后的下一个传入边缘，并将它们连接起来形成一个更小的循环。

完成所有这些之后，您将获得一组循环，每个循环都包含一些非空区域。移走您穿过的所有墙壁，然后如果还有剩余的墙壁，请选择其中任何一堵墙壁，然后再次开始用手靠近墙壁行走。重复此操作，直到所有墙都被丢弃或组装成没有重复顶点的循环。

最后你可能需要研究嵌套。将内部房间从周围的房间中移除。或者，如果您想要的只是给东西上色，您可以按封闭区域的降序对循环进行排序（例如使用鞋带公式），以便较小的房间绘制在较大房间的顶部，确保单独的颜色。