算法高手请进

Question

我在程序中定义了一组线段，每条线段包含两个属性即point1,point2两个点坐标，这些线相互连接构成了一个网，现在我想在这个网里搜索出最小多边形的个数，并得到每一个多边形的顶点坐标，大家看有什么好的算法吗？想了两天了，还是没什么思路。一些简单的线段是这样定义的：
line1 两个点： point(0,0),point(0,5),
line2 两个点： point(0,0),point(5,0)
line3 两个点： point(0,5),point(5,5)
line4 两个点： point(5,0),point(5,5)
line5 两个点： point(5,0),point(10,0)
line6 两个点： point(5,5),point(10,5)
line7 两个点： point(10,0),point(10,5)
上面这7条线组成的应该是两个矩形，怎么得到这两个矩形中每一个矩形的顶点坐标呢？？
同时不能把两个矩形合并为一个矩形，是要搜索各个点组成的最小矩形，且矩形之间不能相互包含。

Answer 1

大家也可以参考这个XML文件，来构成线段，<FCCH_Line>构成一条线段
<?xml version="1.0"?>
<FCCH_MulitLineString xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <MulitLineString>
    <FCCH_Line>
      <Line_Length>119</Line_Length>
      <Start_Point>
        <X>144</X>
        <Y>76</Y>
      </Start_Point>
      <End_Point>
        <X>263</X>
        <Y>76</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>153</Line_Length>
      <Start_Point>
        <X>263</X>
        <Y>76</Y>
      </Start_Point>
      <End_Point>
        <X>416</X>
        <Y>76</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>119</Line_Length>
      <Start_Point>
        <X>144</X>
        <Y>144</Y>
      </Start_Point>
      <End_Point>
        <X>263</X>
        <Y>144</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>153</Line_Length>
      <Start_Point>
        <X>263</X>
        <Y>144</Y>
      </Start_Point>
      <End_Point>
        <X>416</X>
        <Y>144</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>119</Line_Length>
      <Start_Point>
        <X>144</X>
        <Y>199</Y>
      </Start_Point>
      <End_Point>
        <X>263</X>
        <Y>199</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>153</Line_Length>
      <Start_Point>
        <X>263</X>
        <Y>199</Y>
      </Start_Point>
      <End_Point>
        <X>416</X>
        <Y>199</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>68</Line_Length>
      <Start_Point>
        <X>144</X>
        <Y>76</Y>
      </Start_Point>
      <End_Point>
        <X>144</X>
        <Y>144</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>55</Line_Length>
      <Start_Point>
        <X>144</X>
        <Y>144</Y>
      </Start_Point>
      <End_Point>
        <X>144</X>
        <Y>199</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>68</Line_Length>
      <Start_Point>
        <X>263</X>
        <Y>76</Y>
      </Start_Point>
      <End_Point>
        <X>263</X>
        <Y>144</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>55</Line_Length>
      <Start_Point>
        <X>263</X>
        <Y>144</Y>
      </Start_Point>
      <End_Point>
        <X>263</X>
        <Y>199</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>68</Line_Length>
      <Start_Point>
        <X>416</X>
        <Y>76</Y>
      </Start_Point>
      <End_Point>
        <X>416</X>
        <Y>144</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
    <FCCH_Line>
      <Line_Length>55</Line_Length>
      <Start_Point>
        <X>416</X>
        <Y>144</Y>
      </Start_Point>
      <End_Point>
        <X>416</X>
        <Y>199</Y>
      </End_Point>
      <Line_Type>户室线</Line_Type>
      <Line_Color />
      <Line_Size>3</Line_Size>
    </FCCH_Line>
  </MulitLineString>
</FCCH_MulitLineString>   

Answer 2

图方面的算法可能可以算出来吧讲下我的一个比较简单的思路，不考虑性能，
先能正确建立数组,存的是点？是线？
然后根据数组生成一正确的路径graphicpath
然后使用bitmap的drawpath(red,points[])，路径用红色勾线，画在一bitmap上
然后遍历每一个像素，每一个像素朝四周蔓延，如果碰到红色就是碰到边了，而且红色的这点在数组里存在，说明是顶点，就加入，如果这个像素再也蔓延不了了，之前碰到的顶点就是所在多边形的所有顶点，这个像素蔓延完毕，然后这个像素蔓延过的点其他像素已经不用再考虑了