如何订购从架子上获得的图表

问题描述 投票：0回答：1

让我描述一下图片，然后提出问题。下面是三排的架子。每个数字代表一个盒子。黑点代表盒子的质心，可以用 $(x,y)$ 坐标表示。这可以看作是输入。所以输入是 $(x,y)$ 元组的列表。在本例中，有 29 个元组的列表。我想要一个程序按照以下顺序输出元组

1<< 2 << 3 <<4 ......

我最初的想法是使用字典顺序，其定义如下

（a，b）<< (c,d) if and only if a< c or (a= c, b < d)

它的总排序是给定任意两点，我们可以判断其中一个是否小于另一个。 现在问题就出现了，所以按照字典序排序我可以它可以识别

1<< 2 but then as box 3 have a coordinate y less than 2 the order becomes 1<< 3 <<2 and so on. I put a short code for lexicographic ordering

Data = [(1,1) , (2,1) ,( 1,3), (2,) ]

for i in range(len(data)):
        for j in range(i, len(data) - 1):
            if data[i][0] > data[j][0]:
                temp = data[j]
                data[j] = data[i]
                data[i] = temp
            else:
                if data[i][1] > data[j][1]:
                    temp = data[j]
                    data[j] = data[i]
                    data[i] = temp

现在解决这个问题的一种可能的方法是让盒子水平对齐地堆放在架子上，然后使用字典顺序。但是该点以元组坐标列表的形式给出输入，它不理解与其相邻的内容。所以我认为应该用图表进行一些解释。因此，让我们制作一个图，其中每个节点都是一个盒子，如果盒子位于同一架子上并且彼此相邻，我们将连接两个节点。现在，如果节点的度数严格大于 2，则可以识别出旁边有一个垂直堆叠。因此现在必须仅针对 $y$ 进行排序？

请让我知道如何编写这个想法或任何其他包等处理类似的想法或参考。

enter image description here

algorithm math computer-vision graph-theory
1个回答
0
投票

我可能误解了一些东西，但如果没有的话，以下是单个架子的可行解决方案。

一个盒子架子是一组三元组，(x, y, n)。

顺序关系，<<, on the set is then defined as:

a << b <=> a.x < b.x or a.x = b.x and a.y > b.y

假设：

  • 两个盒子不能处于同一位置，即 a.x = b.x -> 不是 a.y = b.y

这可以用许多编程语言轻松实现。 例如（使用伪通用语法）：

boxes = [ ..., (x, y, n), ... ]
boxes.sort((a,b) => 
    if a.x < b.x return a_is_before_b
    if a.x = b.x and a.y > b.y return a_is_before_b
    return a_is_after_b
)

上面的代码在下面用 javascript 编码。

function print(lob) {
    text = "";
    for ( i = 0; i < lob.length; i++ ) {
        text += '<br>' + 'Box ' + lob[i][2] + ' at (' + lob[i][0] + ', ' + lob[i][1] + ')'
    }
    return text;
}

boxes = [ [ 11.5, 3.5, 9 ], [ 9.5, 3.5, 8 ], [ 8.5, 3.5, 7 ], [ 4.5, 1.5, 4 ], [ 7.5, 2.5, 6 ], [ 4.5, 5.5, 2 ], [ 4.5, 3.5, 3 ], [ 7.5, 4.5, 5 ], [ 2.5, 3.5, 1 ] ];

function onload() {
    document.getElementById("print1").innerHTML = print(boxes);
    boxes.sort( (a, b) => { if ( a[0] < b[0] ) return -1; if ( a[0] == b[0] && a[1] > b[1] ) return -1; return 1 } );
    document.getElementById("print2").innerHTML = print(boxes);
}
<body onload="onload()">
List of boxes before sort:
<div id="print1"></div>
<br>
List of boxes after sort:
<div id="print2"></div>
</body>

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.