公开(公告)号：CN101593195A

公开(公告)日：2009-12-02

申请号：CN200810113969.4

申请日：2008-05-30

Applicant: 中国科学院计算技术研究所

Inventor： 郎兵 ,  朱效民 ,  刘炎 ,  方金云

IPC: G06F17/30

Abstract: 本发明提供一种面面叠加处理中的内环外环匹配方法，包括如下步骤：1)在面面叠加处理前，输入或读取参与叠加的每个初始多边形的ID，属于同一个多边形的内环和外环具有同一个ID；2)在面面叠加的过程中，新生成的内环和外环继承叠加运算的初始多边形的ID；3)根据内环和外环的ID，将ID相同的内环和外环进行匹配，形成完整的结果多边形。本发明大大地减少了内外环匹配的计算量。尤其是对于生成结果有大量多边形时，本发明能够明显地提升计算效率。本发明能够解决某些复杂的内外环匹配，而现有的point－in－polygon－test无法做到这一点。

公开(公告)号：CN101499055A

公开(公告)日：2009-08-05

申请号：CN200810057419.5

申请日：2008-02-01

Applicant: 中国科学院计算技术研究所

Inventor： 刘炎 ,  朱效民 ,  郎兵 ,  方金云

IPC: G06F17/00

Abstract: 本发明提供一种面面叠加中的线段处理方法，包括：输入多边形，所述多边形来源于两个多边形组；拆分所述的多边形，得到多边形上的各条线段；对所得到的各条线段采用扫描线算法处理，得到所有相交的线段；将所得到的所有相交的线段按照相交情况以及线段所属的多边形组进行分类，得到四种类别：red1_blue1、red2_blue1、red1_blue2以及red2_blue2；对所有相交的线段按照所划分的类别分别进行处理，得到属于交点的点的坐标、交点所在的线段、交点是出点还是入点的信息、记录交点排序大小的标志信息。本发明在线段处理过程中得到了多种属性，有利于面面叠加中的后续操作；本发明可以对特殊类型的交点进行处理。

公开(公告)号：CN101499082A

公开(公告)日：2009-08-05

申请号：CN200810057537.6

申请日：2008-02-02

Applicant: 中国科学院计算技术研究所

Inventor： 闫杰 ,  朱效民 ,  郎兵 ,  方金云

IPC: G06F17/30

Abstract: 本发明提供一种面面叠加环构造方法，包括对两个多边形组中的多边形进行交操作，以及对两个多边形组中的多边形进行差操作；其中，交操作包括：对产生交点的多边形环通过交点的出入属性查找多边形环；对没有产生交点的多边形环，根据代表点与另一组多边形间的关系，决定是否将该环插入到结果的环的集合中去；差操作包括：对多边形进行分类；对只存在同色交点以及不存在任何交点的多边形进行插入操作，得到差结果的内环集合、差结果的外环集合以及一个待拆分的内环集合；根据交点以及待拆分的内环集合求差操作，将所得到的结果插入差结果的外环集合中。本发明具有效率高、构造过程完整的优点。