c++ - 套索线选择

Question

我正在使用 Qt 构建一个 2D 图形应用程序。该图具有用户可以创建的节点和边，选择是通过套索选择工具完成的。到目前为止，我已经能够使用简单的 Point in polygon 来实现节点选择。算法。但是，现在我需要实现边缘选择。

目前我用三个类来表示这个图:Node、Edge 和 Graph。 Node 是一个简单的 X、Y 容器。 Edge 有一个指向源节点和目标节点的指针。图形包含节点和边的列表。

我知道当节点是选择的一部分时如何选择边，但是当相应的节点不是选择的一部分时如何实现边选择(即边-多边形相交测试)。我说多边形是因为我的套索工具构建了一个表示 n 边多边形的点列表。

这是我需要的算法示例(红色代表预期结果)。

This is not for school but rather a hobby project I am working on.

Answer 1

$selected = [];

for each $polygon in $scene:
    if $polygon.intersects($selectionPolygon):
        for each $edge in $polygon:
            for each $selectionEdge in $selectionPolygon:
                if $edge.crosses($selectionEdge):
                    $selected.push($edge)
                    break
                endif
            end
        end
    endif
end