回 帖 发 新 帖 刷新版面

主题:这个问题太复杂,你有办法吗?

你有办法吗?

平面上有若干条线段,这些线段可能构成n个封闭的区域,现在需要获得所有封闭区域. 已知这些线段的坐标值。

非常感谢

回复列表 (共2个回复)

沙发

You can use graph theory to solve your problem.

板凳

感谢你的回答,我自己也想了许多办法,有一个想法是这样的,但不知道可不可行,各位可以帮我分析分析:

                     .a1-------.a4
                    / \       /
                   /   \     /
                  /     \   /
                 /       \ /
                .a2-------.a3

如上图,图中有四个点和五条线构成3个封闭区域,分别是(a1->a2->a3), (a1->a3->a4), (a1->a2-a3-a4)。我使用如下算法来遍历并获得这些区域,当然在这个过程中可能会出现无数次的重复:

a1->a2->a3->a1
a1->a2->a3
a1->a2->a3->a4->a1
a1->a2->a3->a4
a1->a2->a3
a1->a2
a1

同理再从a2出发, a3出发 ...

...当判别到a3时,发现两个通路,分别可以到达a1和a4,先到达a1时发现一个封闭区域(a1->a2->a3); 然后返回到a3,到达a4,再到达a1,发现另一个封闭区域(a1->a2->a3->a4)...

我来回复

您尚未登录,请登录后再回复。点此登录或注册