用哈希表数据结构快速删除重叠的实体

newer · 发表于 2025-1-9 19:29:12

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

使用哈希表快速删除完全重叠的实体

==============

什么是哈希表？

哈希表（或哈希映射）是一种数据结构，它提供了一种存储键值对的机制，允许快速检索数据。每个键都通过哈希函数进行处理，该函数将索引（或哈希码）计算到存储桶或插槽数组中。然后将键值对存储在相应的存储桶中。哈希表的基本操作（例如插入、删除和搜索）通常具有 O(1) 的平均时间复杂度，因此非常高效。

为什么使用哈希表在 ARX 中删除相同实体非常高效？

1. 快速查找：

哈希表的主要优势在于它能够执行快速查找。删除重复实体时，您可以为每个实体计算哈希值，并检查该哈希值是否已存在于表中。
如果哈希值已存在，则表示该实体是重复的，可以标记为删除。
如果哈希值不存在，则将实体添加到表中。

2. 有效处理冲突：

在哈希表中，当两个不同的实体产生相同的哈希码时，就会发生冲突。高级哈希表实现使用诸如链接（其中每个存储桶都是条目的链接列表）或开放寻址（其中冲突触发对下一个可用插槽的搜索）等技术有效地处理冲突。
正确处理冲突可确保即使存在重复实体，整体性能仍保持最佳状态。

3. 可扩展性：

哈希表可以随着实体数量的增加而很好地扩展。随着更多实体的添加，实施良好的哈希表可以调整自身大小以保持性能，从而确保操作平均保持 O(1)。
在 ARX 中处理大型数据集或复杂图纸时，这种可扩展性至关重要。

ARX 和哈希表

在 ARX（AutoCAD 运行时扩展）上下文中，使用哈希表管理和删除重复实体是有益的，原因如下：

1.唯一标识：

每个实体都可以使用结合各种属性（例如几何图形、图层、颜色等）的哈希值进行唯一标识。
此唯一标识可确保只有真正相同的实体才被视为重复项。

2.性能：

AutoCAD 图纸可以包含数千甚至数百万个实体。使用哈希表管理重复项可确保流程保持高效并且不会降低性能。
这种效率在复杂的 CAD 环境中尤其重要，因为用户需要快速且响应迅速的操作。

使用哈希表删除重复实体的示例代码
以下是 ARX 中一个更正的完整代码示例，用于使用哈希表删除重复实体：

[C++] 纯文本查看 复制代码

/**
 * @brief Removes duplicate entities, keeping only unique ones.
 * 
 * @param objectIdArray Array of entity object IDs
 * @param param Bitmask parameter used for selectively calculating the hash value:
 *  - 1: Use the entity's dxfName
 *  - 2: Use the entity's layerName
 *  - 4: Use the entity's colorIndex
 *  - 8: Use the entity's linetypeName
 *  - 16: Use the entity's linetypeScale
 *  - 32: Use the entity's lineWidth
 *  - 64: Use the entity's GRIP Point array (nStretchPts)
 *  - 128: Use the entity's bounding box (box)
 *  - 256: Use the entity's centroid
 *  - 512: Use the entity's description (entity->desc())
 */
void XdDbUtils::RemoveDuplicateEntities(AcDbObjectIdArray& objectIdArray, int param)
{
    std::unordered_map<size_t, AcDbObjectId> entityHashmap;
    AcDbObjectIdArray remainingObjects;
 
    // Iterate through the entity object array
    for (int i = 0; i < objectIdArray.length(); ++i) {
        AcDbObjectId objectId = objectIdArray[ i];
        AcDbEntity* pEntity = nullptr;
        if (acdbOpenAcDbEntity(pEntity, objectId, AcDb::kForRead) == Acad::eOk && pEntity) {
            // Calculate the hash value of the entity
            size_t hash = XdDbUtils::CalculateHash(pEntity, param);
 
            // Check if the hash value already exists in the hash table
            if (entityHashmap.find(hash) == entityHashmap.end()) {
                // The hash value does not exist, add to the hash table and remainingObjects array
                entityHashmap[hash] = objectId;
                remainingObjects.append(objectId);
            }
            // Close the entity
            pEntity->close();
        }
    }
 
    // Replace the original objectIdArray with the remainingObjects array
    objectIdArray = remainingObjects;
}

结论

使用哈希表删除 ARX 中的重复实体非常高效，因为哈希表的查找、插入和删除操作速度很快。这种效率对于在复杂的 AutoCAD 环境中保持性能至关重要，可确保快速准确地处理大型数据集。

==================

(defun c:xdtb_removeovents (/ ss len ret)
(xdrx-begin)
(if (setq ss (xdrx-ssget
(xdrx-string-multilanguage
"\n选择要处理的对象<退出>:"
"\nSelect objects to process <Exit>:"
)
)
)
(progn
(setq len (sslength ss))
(setq ret (xdrx-entity-removeduplicates ss 129))
(xdrx-prompt
(xdrx-string-formatex
(xdrx-string-multilanguage
"\n共删除了 %d 个重复的实体."
"\nA total of %d duplicate entities have been removed."
)
(- len ret)
)
)
)
)
(xdrx-end)
(princ)
)

60ck · 发表于 2025-1-10 09:26:15

执行后出现错误的讯息
错误: no function definition: XDRX-ENTITY-REMOVEDUPLICATES

newer · 发表于 2025-1-10 11:09:45

60ck 发表于 2025-1-10 09:26
执行后出现错误的讯息
错误: no function definition: XDRX-ENTITY-REMOVEDUPLICATES

请用最新的2025.0108以后版本的API

60ck · 发表于 2025-1-12 01:51:52

newer 发表于 2025-1-10 11:09
请用最新的2025.0108以后版本的API

好的，谢谢你
我再来试试看

账号		自动登录	找回密码
密码			立即注册

[每日一码] 用哈希表数据结构快速删除重叠的实体

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评

点评