基于邻接表分解自相交折线的算法设计

Algorithm of decompose self-intersection broken line with adjacency list

寻求能快速、高效分解自相交折线的算法是计算机做二维图形所必须面对的问题。虽然邻接表和单链表的指针部分耗用了一定量的内存,但在删除、插入等操作上实现了快速、高效,因此非常适合解决这个问题。文中算法的时间复杂度和空间复杂度均达到预期目标,并在实际的应用中确实满足了快速、高效等性能要求。

Algorithm of decomposing self-intersection broken lines, which is clipping and efficient, is inevitablely met in using computer to draw planar graphics. The pointer of adjacency list and single list consumes some memories, however, the delete operation and insert operation are clipping and efficient, so it is very necessary to solve the problem. Time complexity and space complexity of the algorithm are reasonable, and the algorithm can satisfy people＇s demand in the realistic world.