一种k-支配轮廓点获取方法及装置.pdf

(19)中华人民共和国国家知识产权局*CN102521399A*(12)发明专利申请(10)申请公布号CN102521399A(43)申请公布日2012.06.27(21)申请号201110439255.4(22)申请日2011.12.23(71)申请人苏州大学地址215123江苏省苏州市工业园区仁爱路199号(72)发明人赵雷吴娴黄荣跃(74)专利代理机构北京集佳知识产权代理有限公司11227代理人常亮李辰(51)Int.Cl.G06F17/30(2006.01)权利要求书权利要求书2页2页说明书说明书77页页附图附图33页(54)发明名称一种k-支配轮廓点获取方法及装置(57)摘要本发明实施例公开了一种k-支配轮廓点获取方法及装置，在所述方法中，在每次数据集更新的时候，不再将待处理点与传统轮廓点进行比较，而是与数量少于传统轮廓点的k-支配轮廓点进行比较，并且，引入了准轮廓点的概念，使部分待处理点与准轮廓点进行比较，而准轮廓点比传统轮廓点更易于维护，因此减少了计算量。同时，本发明公开的获取方法引用了支配关系链表，保留了数据点间的k-支配关系，使之在数据集更新后使用，从而避免了数据点间k-支配关系的反复计算，因而减少了计算量。CN102539ACN102521399A权利要求书1/2页1.一种k-支配轮廓点获取方法，其特征在于，包括以下步骤：1)计算得到数据集中的k-支配轮廓点，并将在计算所述k-支配轮廓点的过程中不被其他数据点所d-支配的数据点作为准轮廓点，并保存数据点间的支配关系；2)确定当前的待更新数据点的更新类型，所述更新类型包括：插入或删除，当所述待更新数据点的更新类型为插入时，确定所述待更新数据点为待处理点，当所述待更新数据点的更新类型为删除时，删除所述待更新数据点，并确定与所述待更新数据点存在支配关系的数据点为待处理点；3)判断所述待处理点是否被k-支配轮廓点集中的数据点所k-支配，若否，则执行步骤5)，若是，则执行步骤4)；4)判断k-支配所述待处理点的所述k-支配轮廓点是否d-支配所述待处理点，若是，则将待处理点直接插入数据集中，若否，则执行步骤5)；5)判断所述k-支配轮廓点集中是否存在被待处理点所k-支配的轮廓点，若否，则执行步骤7)，若是，则从所述k-支配轮廓点集中移除所述被支配的数据点，并执行步骤6)；6)判断所述移除点是否被待处理点所d-支配，如果否，则将所述移除点放入准轮廓点集中；7)判断所述准轮廓点集中是否存在k-支配所述待处理点的准轮廓点，如果否，将所述待处理点插入k-支配轮廓点集中，如果是，进入步骤8)；8)判断所述准轮廓点集中是否存在被所述待处理点所d-支配的准轮廓点，如果否，将所述待处理点插入准轮廓点集中，如果是，保存待处理点和准轮廓点的d-支配关系，并将待处理点插入数据集中。2.根据权利要求1所述的方法，其特征在于，步骤1)中保存数据间的支配关系的具体步骤为：计算得到数据间的支配关系后，为每个数据点建立支配关系链表，并将所述数据点与其他数据点之间的支配关系保存在支配关系链表中。3.根据权利要求1所述的方法，其特征在于，步骤3)、步骤4)、步骤5)、步骤6)、步骤7)及步骤8)中还包括：计算获取数据间的k-支配关系后，将所述k-支配关系保存在产生k-支配关系的数据点的支配关系链表中，并设置被支配点的front指针指向所在支配点的关系链表中的位置；计算获取数据间的d-支配关系后，将被支配点的DDP属性设置为支配点。4.根据权利要求1所述的方法，其特征在于，步骤2)中当更新类型为删除时，确定待处理点的具体步骤为：在删除所述待删除数据点前，判断所述待删除数据点所对应的关系链表中是否有数据点，如果没有，直接将所述待删除数据点及其所对应的支配关系链表删除；如果有，即确定该待删除数据点的支配关系链表中的数据点为待处理点。5.根据权利要求1中所述的方法，其特征在于，判断待处理点是否被k-支配轮廓点集中的数据点所k-支配的具体步骤为：11)选取所述k-支配轮廓点集中的一个k-支配轮廓点；12)判断选取的所述k-支配轮廓点是否k-支配所述待处理点，如果是，则保存所述待2CN102521399A权利要求书2/2页处理点与选取的所述k-支配轮廓点的k-支配关系，如果否，则进入步骤13)；13)判断所述k-支配轮廓点集中是否还有其他k-支配轮廓点未被选取和所述待处理点进行比较，如果是，则选取其他的数据点执行步骤12)，直到所述k-支配轮廓点集中的所有点都和所述待处理点完成了比较。6.根据权利要求1所述的方法，其特征在于，所述步骤6)中还包括：如果所述移除点被所述待处理点所d-支配，则将所述d-支配关系保存在所述移除点与所述待处理点的支配关系链表中，并设置所述移除点的DDP属性为所述待处理点。7.根据权利要求1所