社区 › ObjectARX/VC++ 编程技术 › 多边形叠加分析(交并差)

gzxl 发表于 2021-12-13 09:23:02

多边形叠加分析(交并差)

本帖最后由 gzxl 于 2021-12-13 09:32 编辑

MFC 的多边形叠加分析(交并差)见原帖网址：
https://github.com/team79/Polygo ... ter/MFCApplication3

arx的多边形叠加分析(交并差)效果图：
attach://117161.gif
arx 的不支持有弧段的多边形。

数学法计算交集与面域法计算交集的时间比较：
数学法用时: 0 毫秒

面域法用时: 2937毫秒

获取多段线顶点坐标,并加入点集合中
    /// @brief 获取多段线顶点坐标,并加入点集合中
    /// @param polylineId : 多段线实体 ID
    /// @param pointArray : 返回的顶点集合
    /// @return : 成功返回 Acad::eOk，失败返回 Acad::eInvalidInput
    static Acad::ErrorStatus GetPolylineVertPts(AcDbObjectId polylineId, AcGePoint3dArray& pointArray)
    {
      Acad::ErrorStatus es = Acad::eOk;
      AcDbObject* pObject = NULL;
      AcDbPolyline* pline = NULL;
      if ((es = acdbOpenObject(pObject, polylineId, AcDb::kForRead)) != Acad::eOk)
            return es;
      if (!pObject->isKindOf(AcDbPolyline::desc()))
      {
            pObject->close();
            return Acad::eInvalidInput;
      }
      pline = AcDbPolyline::cast(pObject);
      int num = pline->numVerts();
      for (int i = 0; i < num; i++)
      {
            AcGePoint3d temPt;
            if ((es = pline->getPointAt(i, temPt)) == Acad::eOk)
            {
                pointArray.append(temPt);
            }
      }

      AcGePoint3d startPt;
      es = pline->getPointAt(0, startPt);
      pointArray.append(startPt);

      pObject->close();
      return es;
    }多边形叠加分析(交集) 测试
// 创建多段线过滤条件
struct resbuf* filter = acutBuildList(RTDXF0, _T("LWPOLYLINE"), RTNONE);
ads_name ss;
// 提示用户选择二个多边形
acutPrintf(_T("\n请选择二个多边形(闭合多段线):\n"));
int res = acedSSGet(NULL, NULL, NULL, filter, ss);
// 释放缓冲区链表
acutRelRb(filter);

// 计时开始
DWORD start, end;
start = GetTickCount();

// 如果取消了选择或者选择条件不符合
if (res != RTNORM)
{
    acutPrintf(_T("\n没有选择二个多边形(闭合多段线)!"));
    return;
}
// 选择集个数
Adesk::Int32 length;
acedSSLength(ss, &length);
if (length != 2)
{
    acutPrintf(_T("\n必须选择二个多边形(闭合多段线)!"));
    // 释放选择集
    acedSSFree(ss);
    return;
}
// 第一、二个多边形顶点集合，交集顶点集合
AcGePoint3dArray poly1Pts, poly2Pts, interPolyPts;
// 错误状态码
Acad::ErrorStatus es;
// 图元名
ads_name eame1, eame2;
acedSSName(ss, 0, eame1);
acedSSName(ss, 1, eame2);
// 释放选择集
acedSSFree(ss);
// 图元名转换为实体ID
AcDbObjectId obj1Id, obj2Id;
es = acdbGetObjectId(obj1Id, eame1);
es = acdbGetObjectId(obj2Id, eame2);
// 获取多边形顶点，并加入集合
es = GetPolylineVertPts(obj1Id, poly1Pts);
es = GetPolylineVertPts(obj2Id, poly2Pts);

MPolygon p1, p2;
Edge temp;
// 第一个多边形
for (int i = 0; i < poly1Pts.length() - 1; i++)
{
    temp.LPoint.x = poly1Pts.x;
    temp.LPoint.y = poly1Pts.y;
    temp.RPoint.x = poly1Pts.x;
    temp.RPoint.y = poly1Pts.y;
    p1.external_circle.circle_edge.push_back(temp);
}
temp.LPoint.x = poly1Pts.x;
temp.LPoint.y = poly1Pts.y;
temp.RPoint.x = poly1Pts.x;
temp.RPoint.y = poly1Pts.y;
p1.external_circle.circle_edge.push_back(temp);
p1.internal_circle.clear();

// 第二个多边形
for (int i = 0; i < poly2Pts.length() - 1; i++)
{
    temp.LPoint.x = poly2Pts.x;
    temp.LPoint.y = poly2Pts.y;
    temp.RPoint.x = poly2Pts.x;
    temp.RPoint.y = poly2Pts.y;
    p2.external_circle.circle_edge.push_back(temp);
}
temp.LPoint.x = poly2Pts.x;
temp.LPoint.y = poly2Pts.y;
temp.RPoint.x = poly2Pts.x;
temp.RPoint.y = poly2Pts.y;
p2.external_circle.circle_edge.push_back(temp);
p2.internal_circle.clear();

vector<AcGePoint2dArray> interPts;
MPolygon::SolveAnd(p1, p2, interPts); // 交集
if (interPts.size() > 0)
{
    for (int i = 0; i < (int)interPts.size(); i++)
    {
      AcGePoint2dArray pts = interPts;
      if (pts.length() > 0)
      {
            int numVertices = pts.length();
            AcDbPolyline* pPoly = new AcDbPolyline(numVertices);
            for (int j = 0; j < numVertices; j++)
            {
                AcGePoint2d pt2d = pts;
                pPoly->addVertexAt(j, pt2d, 0, 0, 0);
            }
            pPoly->setColorIndex(1);
            pPoly->setClosed(TRUE);
            pPoly->setConstantWidth(10);
            AcDbBlockTable* pBlkTbl = NULL;
            acdbHostApplicationServices()->workingDatabase()->getBlockTable(pBlkTbl, AcDb::kForRead);
            AcDbBlockTableRecord* pBlkTblRcd = NULL;
            pBlkTbl->getAt(ACDB_MODEL_SPACE, pBlkTblRcd, AcDb::kForWrite);
            pBlkTbl->close();
            pBlkTblRcd->appendAcDbEntity(pPoly);
            pBlkTblRcd->close();
            pPoly->close();
      }
    }
}
// 结束计时
end = GetTickCount() - start;
acutPrintf(_T("\n数学法用时: %d 毫秒"), end);多边形叠加分析(并集) 测试
// 创建多段线过滤条件
struct resbuf* filter = acutBuildList(RTDXF0, _T("LWPOLYLINE"), RTNONE);
ads_name ss;
// 提示用户选择二个多边形
acutPrintf(_T("\n请选择二个多边形(闭合多段线):\n"));
int res = acedSSGet(NULL, NULL, NULL, filter, ss);
// 释放缓冲区链表
acutRelRb(filter);

// 计时开始
DWORD start, end;
start = GetTickCount();

// 如果取消了选择或者选择条件不符合
if (res != RTNORM)
{
    acutPrintf(_T("\n没有选择二个多边形(闭合多段线)!"));
    return;
}
// 选择集个数
Adesk::Int32 length;
acedSSLength(ss, &length);
if (length != 2)
{
    acutPrintf(_T("\n必须选择二个多边形(闭合多段线)!"));
    // 释放选择集
    acedSSFree(ss);
    return;
}
// 第一、二个多边形顶点集合，交集顶点集合
AcGePoint3dArray poly1Pts, poly2Pts, interPolyPts;
// 错误状态码
Acad::ErrorStatus es;
// 图元名
ads_name eame1, eame2;
acedSSName(ss, 0, eame1);
acedSSName(ss, 1, eame2);
// 释放选择集
acedSSFree(ss);
// 图元名转换为实体ID
AcDbObjectId obj1Id, obj2Id;
es = acdbGetObjectId(obj1Id, eame1);
es = acdbGetObjectId(obj2Id, eame2);
// 获取多边形顶点，并加入集合
es = GetPolylineVertPts(obj1Id, poly1Pts);
es = GetPolylineVertPts(obj2Id, poly2Pts);

MPolygon p1, p2;
Edge temp;
// 第一个多边形
for (int i = 0; i < poly1Pts.length() - 1; i++)
{
    temp.LPoint.x = poly1Pts.x;
    temp.LPoint.y = poly1Pts.y;
    temp.RPoint.x = poly1Pts.x;
    temp.RPoint.y = poly1Pts.y;
    p1.external_circle.circle_edge.push_back(temp);
}
temp.LPoint.x = poly1Pts.x;
temp.LPoint.y = poly1Pts.y;
temp.RPoint.x = poly1Pts.x;
temp.RPoint.y = poly1Pts.y;
p1.external_circle.circle_edge.push_back(temp);
p1.internal_circle.clear();

// 第二个多边形
for (int i = 0; i < poly2Pts.length() - 1; i++)
{
    temp.LPoint.x = poly2Pts.x;
    temp.LPoint.y = poly2Pts.y;
    temp.RPoint.x = poly2Pts.x;
    temp.RPoint.y = poly2Pts.y;
    p2.external_circle.circle_edge.push_back(temp);
}
temp.LPoint.x = poly2Pts.x;
temp.LPoint.y = poly2Pts.y;
temp.RPoint.x = poly2Pts.x;
temp.RPoint.y = poly2Pts.y;
p2.external_circle.circle_edge.push_back(temp);
p2.internal_circle.clear();

vector<AcGePoint2dArray> interPts;
MPolygon::SolveOr(p1, p2, interPts);// 并集
if (interPts.size() > 0)
{
    for (int i = 0; i < (int)interPts.size(); i++)
    {
      AcGePoint2dArray pts = interPts;
      if (pts.length() > 0)
      {
            int numVertices = pts.length();
            AcDbPolyline* pPoly = new AcDbPolyline(numVertices);
            for (int j = 0; j < numVertices; j++)
            {
                AcGePoint2d pt2d = pts;
                pPoly->addVertexAt(j, pt2d, 0, 0, 0);
            }
            pPoly->setColorIndex(1);
            pPoly->setClosed(TRUE);
            pPoly->setConstantWidth(10);
            AcDbBlockTable* pBlkTbl = NULL;
            acdbHostApplicationServices()->workingDatabase()->getBlockTable(pBlkTbl, AcDb::kForRead);
            AcDbBlockTableRecord* pBlkTblRcd = NULL;
            pBlkTbl->getAt(ACDB_MODEL_SPACE, pBlkTblRcd, AcDb::kForWrite);
            pBlkTbl->close();
            pBlkTblRcd->appendAcDbEntity(pPoly);
            pBlkTblRcd->close();
            pPoly->close();
      }
    }
}

// 结束计时
end = GetTickCount() - start;
acutPrintf(_T("\n数学法用时: %d 毫秒"), end);多边形叠加分析(差集) 测试
// 创建多段线过滤条件
struct resbuf* filter = acutBuildList(RTDXF0, _T("LWPOLYLINE"), RTNONE);
ads_name ss;
// 提示用户选择二个多边形
acutPrintf(_T("\n请选择二个多边形(闭合多段线):\n"));
int res = acedSSGet(NULL, NULL, NULL, filter, ss);
// 释放缓冲区链表
acutRelRb(filter);

// 计时开始
DWORD start, end;
start = GetTickCount();

// 如果取消了选择或者选择条件不符合
if (res != RTNORM)
{
    acutPrintf(_T("\n没有选择二个多边形(闭合多段线)!"));
    return;
}
// 选择集个数
Adesk::Int32 length;
acedSSLength(ss, &length);
if (length != 2)
{
    acutPrintf(_T("\n必须选择二个多边形(闭合多段线)!"));
    // 释放选择集
    acedSSFree(ss);
    return;
}
// 第一、二个多边形顶点集合，交集顶点集合
AcGePoint3dArray poly1Pts, poly2Pts, interPolyPts;
// 错误状态码
Acad::ErrorStatus es;
// 图元名
ads_name eame1, eame2;
acedSSName(ss, 0, eame1);
acedSSName(ss, 1, eame2);
// 释放选择集
acedSSFree(ss);
// 图元名转换为实体ID
AcDbObjectId obj1Id, obj2Id;
es = acdbGetObjectId(obj1Id, eame1);
es = acdbGetObjectId(obj2Id, eame2);
// 获取多边形顶点，并加入集合
es = GetPolylineVertPts(obj1Id, poly1Pts);
es = GetPolylineVertPts(obj2Id, poly2Pts);

MPolygon p1, p2;
Edge temp;
// 第一个多边形
for (int i = 0; i < poly1Pts.length() - 1; i++)
{
    temp.LPoint.x = poly1Pts.x;
    temp.LPoint.y = poly1Pts.y;
    temp.RPoint.x = poly1Pts.x;
    temp.RPoint.y = poly1Pts.y;
    p1.external_circle.circle_edge.push_back(temp);
}
temp.LPoint.x = poly1Pts.x;
temp.LPoint.y = poly1Pts.y;
temp.RPoint.x = poly1Pts.x;
temp.RPoint.y = poly1Pts.y;
p1.external_circle.circle_edge.push_back(temp);
p1.internal_circle.clear();

// 第二个多边形
for (int i = 0; i < poly2Pts.length() - 1; i++)
{
    temp.LPoint.x = poly2Pts.x;
    temp.LPoint.y = poly2Pts.y;
    temp.RPoint.x = poly2Pts.x;
    temp.RPoint.y = poly2Pts.y;
    p2.external_circle.circle_edge.push_back(temp);
}
temp.LPoint.x = poly2Pts.x;
temp.LPoint.y = poly2Pts.y;
temp.RPoint.x = poly2Pts.x;
temp.RPoint.y = poly2Pts.y;
p2.external_circle.circle_edge.push_back(temp);
p2.internal_circle.clear();

vector<AcGePoint2dArray> interPts;
MPolygon::SolveSub(p1, p2, interPts);// 差集
if (interPts.size() > 0)
{
    for (int i = 0; i < (int)interPts.size(); i++)
    {
      AcGePoint2dArray pts = interPts;
      if (pts.length() > 0)
      {
            int numVertices = pts.length();
            AcDbPolyline* pPoly = new AcDbPolyline(numVertices);
            for (int j = 0; j < numVertices; j++)
            {
                AcGePoint2d pt2d = pts;
                pPoly->addVertexAt(j, pt2d, 0, 0, 0);
            }
            pPoly->setColorIndex(1);
            pPoly->setClosed(TRUE);
            pPoly->setConstantWidth(10);
            AcDbBlockTable* pBlkTbl = NULL;
            acdbHostApplicationServices()->workingDatabase()->getBlockTable(pBlkTbl, AcDb::kForRead);
            AcDbBlockTableRecord* pBlkTblRcd = NULL;
            pBlkTbl->getAt(ACDB_MODEL_SPACE, pBlkTblRcd, AcDb::kForWrite);
            pBlkTbl->close();
            pBlkTblRcd->appendAcDbEntity(pPoly);
            pBlkTblRcd->close();
            pPoly->close();
      }
    }
}

// 结束计时
end = GetTickCount() - start;
acutPrintf(_T("\n数学法用时: %d 毫秒"), end);交并差所需的类见以下附件PolygonOAUtil.h、PolygonOAUtil.cpp
PolygonOAUtil.h头文件

/// @file 多边形叠加分析(交并差)
/// @date 2021-12-08
/// @version v1.0

#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/////////////////////////////////////////////////////////////////
// Point 类 : 实现多边形点的存储，并记录点的性质。
class Point
{
public:
    // 存储多边形顶点的横坐标, 纵坐标
    double x, y;

    // 重构 Point 类的构造函数
    Point(double x = 0, double y = 0) : x(x), y(y) {}

    // 重构类的=运算
    Point& operator=(const Point& b);

    // 重构类的<运算
    bool operator<(const Point& b);

    // 重构类的!=运算
    bool operator!=(const Point b);

    // 重构类的==运算
    bool operator==(const Point b);
};

/////////////////////////////////////////////////////////////////
// Edge 类 : 实现多边形边的存储，并记录边的性质；
class Edge
{
public:
    // 存储简单多边形边的左顶点, 右顶点
    Point LPoint, RPoint;

    // 存储边的奇偶性   奇边 ： 1 偶边 ： 0
    int odd;

    // 存储变的内外性，即该边是在另一多边形的内部还是外部    内边 ： 1 外边： 0 重边 ：2
    int inout;

    // 初始化 Edge 类对象的各个成员变量，避免因未初始化而引起的不知名错误
    void init();

    // 重构 Edge 类的构造函数
    Edge() {}

    // 重构 Edge 类的构造函数
    Edge(Point l, Point r) :LPoint(l), RPoint(r) {}

    // 重构类的==运算
    bool operator==(const Edge B);

    // 重构类的!=运算
    bool operator!=(const Edge B);

    // 计算两线段交点
    static double tCross(const Point& p1, const Point& p2);
    static double Cross(const Point& p1, const Point& p2, const Point& p3, const Point& p4);
    static double Area(const Point& p1, const Point& p2, const Point& p3);
    static double fArea(const Point& p1, const Point& p2, const Point& p3);
    static bool Meet(const Point& p1, const Point& p2, const Point& p3, const Point& p4);
    static Point Inter(const Point& p1, const Point& p2, const Point& p3, const Point& p4);
    static double Dot(Point A, Point B);

    // 判断点是否在线段之上
    static bool OnSegment(Point p, Point a1, Point a2);

    // 求两线段交点
    static Point GetCrossPoint(Edge a, Edge b);

    // 实现边的控制台输出，该函数主要用与在最初开发系统时对程序的调试
    void output();
};

/////////////////////////////////////////////////////////////////
// TEdge 类 : 在进行多边形的交并差计算时实现多边形边的存储，起到过度的作用，同时记录边的性质；
class TEdge : public Edge
{
public:
    // 标记边是属于多边形 A、还是多边形 B
    int pgn;

    // 标记边是否已访问过, 初始值为false
    bool visited;

    // 记录边是否为重边
    int repet;

    // 指向连接左、右端点的本输入多边形的邻边的指针
    int lpAdjEg, rpAdjEg;

    // 指向连接左、右端点的另一输入多边形的两邻边的指针
    int lpotherPgnAdjEg, rpotherPgnAdjEg;

    // 重构TEdge类的构造函数
    TEdge();

    // 重构类的=运算
    TEdge& operator=(const Edge& e);

    // 重构类的==运算
    bool operator==(const TEdge B);

    // 重构类的!=运算
    bool operator!=(const TEdge B);

    // 重构类的==运算
    bool operator==(const Edge B);

    // 重构类的!=运算
    bool operator!=(const Edge B);
};

/////////////////////////////////////////////////////////////////
// Circle 类 : 实现多边形内环与外环的存储，并记录环的性质
class Circle
{
public:
    // 存储环的多条边
    vector<Edge> circle_edge;

    // 用来表示该环是内环还是外环
    int type;// 好像 type 无作用

    // 重构 Circle 类的构造函数
    Circle();

    // 初始化 Circle 类对象的各个成员变量，避免因未初始化而引起的不知名错误
    void init();

    // 判断点是否在线段之上
    static bool PointAboveSegment(Point p, Edge e);
};

/////////////////////////////////////////////////////////////////
// MPolygon类：实现多边形的存储，并记录多边形的性质。
class MPolygon
{
public:
    // 存储多边形的外环
    Circle external_circle;

    // 存储多边形的内环
    vector<Circle> internal_circle;

    // 重构 MPolygon 类的构造函数
    MPolygon();

    // 初始化 MPolygon 类对象的各个成员变量，避免因未初始化而引起的不知名错误
    void init();

    // 计算位于点p下方的另一多边形边的条数
    int calc(Point p, const MPolygon B);

    // 判断另一多边形中是否有边e
    bool finde(Edge e, const MPolygon B);

    // 判断内边还是外边
    void getinout(const MPolygon B);

    // 判断奇边还是偶边
    void getodd();

    // 得到简单边，作用是当前多边形的边与第二个多边形的边存在的交点插入当前多边形中
    // 并重构当前多边形的边
    void getSimpleEdge(const MPolygon B);

    // 计算两个多边形交集
    static int SolveAnd(MPolygon p1, MPolygon p2, vector<AcGePoint2dArray>& interPts);

    // 计算两个多边形并集
    static int SolveOr(MPolygon p1, MPolygon p2, vector<AcGePoint2dArray>& interPts);

    // 计算两个多边形差集
    static int SolveSub(MPolygon p1, MPolygon p2, vector<AcGePoint2dArray>& interPts);
};attach://117164.rar

asen 发表于 2021-12-13 15:53:49

把每个多边形转为面域, 然后用面域的ARX的布尔函数求得也是可以的

Wanda 发表于 2021-12-14 08:24:57

大佬和顾老师的ID很像啊

tigcat 发表于 2021-12-14 10:12:52

来支持楼主一下，感谢分享c+源码

czb203 发表于 2022-2-12 22:58:10

来支持楼主一下，感谢分享c+源码

yonjay 发表于 2022-12-2 11:44:07

g大，CAD用面域求差集好像有bug

yonjay 发表于 2022-12-3 08:38:31

g大，测试了循环卡，CAD就崩了

查看完整版本: 多边形叠加分析(交并差)