主题:这个问题太复杂,你有办法吗?
adjust585888
[专家分:0] 发布于 2006-04-29 22:36:00
你有办法吗?
平面上有若干条线段,这些线段可能构成n个封闭的区域,现在需要获得所有封闭区域. 已知这些线段的坐标值。
非常感谢
回复列表 (共2个回复)
沙发
justforfun626 [专家分:18460] 发布于 2006-04-30 04:03:00
You can use graph theory to solve your problem.
板凳
adjust585888 [专家分:0] 发布于 2006-04-30 10:48:00
感谢你的回答,我自己也想了许多办法,有一个想法是这样的,但不知道可不可行,各位可以帮我分析分析:
.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)...
我来回复