topic Re: Space line, how to find the red boundary? in ObjectARX Forum

Space line, how to find the red boundary?

1127204185 — Sun, 29 May 2022 10:23:32 GMT

Space line, how to find the red boundary?

Re: Space line, how to find the red boundary?

tbrammer — Mon, 30 May 2022 08:48:30 GMT

ObjectARX has classes like AcDbSubDMesh that can represent meshes. But I don't think that there

is an API that can find the border lines.

Basically the algorithm would be like this:

1.) Build an index of all start- and endpoints of the lines.

2.) Now you can represent lines by index pairs. I.e. the four lines around face A are (0,1), (1,4), (0,3) and (3,4).

3.) Create a "connection map". I.e.:

std::map<unsigned, std::vector<unsigned> > connections; connections[0].push_back(1); connections[1].push_back(0); connections[0].push_back(3); connections[3].push_back(0); connections[3].push_back(4); connections[4].push_back(3); connections[3].push_back(6); connections[6].push_back(3); ...

4.) For every connection look for closed triangle- or quad-loops. I.e. (3,4) has two loops: face A and C. If a connection is within two loops, it is an inner connection. If it has only one loop, like (6,7) and (7,8) it is an outer boundary.

Re: Space line, how to find the red boundary?

tbrammer — Mon, 30 May 2022 14:21:56 GMT

You might find my code sample here useful.

But note that it works for triangles only. You must enhance the code so that it also works with quads.

Re: Space line, how to find the red boundary?

1127204185 — Mon, 30 May 2022 14:51:56 GMT

The difficulty is how to find these closed areas？

A:0-1-4-3

B:1-2-5-4

D:3-4-7-6

C:4-5-8-7

Re: Space line, how to find the red boundary?

tbrammer — Mon, 30 May 2022 15:26:02 GMT

It's not too difficult.

Let's say you start at (3,4)
In the connections map you find the points connected to 3 and 4.

Set3: 0,6,9 (point 9 is left of point 3. It isn't drawn in my picture)
Set4: 1,5,7

We first check, whether there is a triangle: Does one or two of the points in Set3 connect to 4?

If there are less than two triangle connections then we search for quad connections between Set3 and Set4.

In this case there is no triangle connection. But we easily find the two quad connections (0,1) and (6,7).
And now, because we found two connections, you can tell that (3,4) is an inner connection.

Re: Space line, how to find the red boundary?

1127204185 — Mon, 30 May 2022 15:50:41 GMT

My algorithm，3-4 there are two results, proving that it is not a boundary

No. 1 3-4 No. 2 3-4-1 3-4-5 3-4-7 No. 3 3-4-1-0 3-4-1-14 3-4-1-2 3-4-5-2 3-4-5-10 3-4-5-8 3-4-7-6 3-4-7-8 No. 4 3-4-1-0-15 3-4-1-0-17 3-4-1-0-3 Found a closed body A 3-4-1-14-15 3-4-1-14-? 3-4-1-14-13 3-4-1-2-13 3-4-1-2-11 3-4-1-2-5 3-4-5-2-1 3-4-5-2-13 3-4-5-2-11 3-4-5-2-5 3-4-5-10-11 3-4-5-10-? 3-4-5-10-9 3-4-5-8-9 3-4-5-8-7 3-4-7-6-3 Found a closed body C 3-4-7-6-19 3-4-7-8-5 3-4-7-8-9

Re: Space line, how to find the red boundary?

1127204185 — Mon, 30 May 2022 15:58:50 GMT

No. 1 6-7 No. 2 6-7-4 6-7-8 No. 3 6-7-4-3 6-7-4-1 6-7-4-5 6-7-8-5 6-7-8-9 No. 4 6-7-4-3-6 Found a closed body C 6-7-4-3-0 6-7-4-3-18 6-7-4-1-0 6-7-4-1-14 6-7-4-1-2 6-7-4-5-2 6-7-4-5-10 6-7-4-5-8 6-7-8-5-2 6-7-8-5-10 6-7-8-5-4 6-7-8-5-9 6-7-8-9-10 6-7-8-9-?

Re: Space line, how to find the red boundary?

tbrammer — Tue, 31 May 2022 06:53:38 GMT

Yep, you got the algorithm. Now you just need to code it 😁.

Re: Space line, how to find the red boundary?

1127204185 — Tue, 31 May 2022 10:19:53 GMT

Still don't understand

no.5 3-4-5-2-1-0 no.6 3-4-5-2-1-0-3

Re: Space line, how to find the red boundary?

tbrammer — Tue, 31 May 2022 13:04:37 GMT

My idea was to search for triangles and quads only because your drawing only contains triangles and quads and because it is common to form shells from triangles an quads.

I would not search for loops that contain more than four points!

So neither 3-4-5-2-1-0 nor 3-4-5-2-1-0-3 is a "valid" loop. I would check 3-4-5-2 and discard it, because 2 isn't connected to 3.

If you expect faces with more than 4 edges the algorithm becomes much more complex. In this case you have to "walk along" all possible paths and remember which points you have already visited. You will find a bunch of long loops that can be split into shorter loops like (3,4,5,2,1,0) => (3,4,1,0)+(4,5,2,1). These long loops must be sorted out.

Re: Space line, how to find the red boundary?

1127204185 — Tue, 31 May 2022 14:18:03 GMT

I would search for loops that contain more than four points!

Re: Space line, how to find the red boundary?

tbrammer — Tue, 31 May 2022 15:10:55 GMT

Hm. Really? It's quite challenging to find an effective algorithm for this.

I already wrote one basic idea above: Walk along all possible paths and remember which points you have already visited. If you come to a point that you visited before you found a loop. Store all loops. You will find a bunch of long loops that can be split into shorter loops like (3,4,5,2,1,0) => (3,4,1,0)+(4,5,2,1). These long loops must be sorted out. Analyse the remaining short loops and look for single connections. These are the border lines.

If you find loops with 4 and more points the points may not be in the same plane and/or the face might be concave.

What is this?

If all four points 0,1,2 and 3 are within the same plane you have a triangle (0,1,2) and a concave quad (0,1,3,2).
In this case (1,2,3) is the outer border.
Otherwise you have two triangles (0,1,2) and (1,2,3).
In this case (1,3,2,0) is the outer border.

Now imagine loops with 5, 6, ... points.

Maybe it makes sense to look for points within (nearly?) the same plane while searching for loops.

Re: Space line, how to find the red boundary?

1127204185 — Thu, 02 Jun 2022 05:20:51 GMT

Each edge can get 2 closed

6-7 -4-3-6

6-7-8-9-?-?...-?-19-6

Re: Space line, how to find the red boundary?

tbrammer — Thu, 02 Jun 2022 07:49:01 GMT

(6-7-8-9-?-?...-?-19) can be split into smaller loops. (6,7,4,3) can't. You must sort out all loops that can be split! I.e. consider (6,7,8,9,10,5,4,3,18,19). It includes the connected points (6,3), (7,4) and (5,8). So it can be split at these three connections in three steps:

split at (6,3): (6,7,8,9,10,5,4,3,18,19) => (6,3,18,19) + (6,7,8,9,10,5,4,3)
split at (7,4): (6,7,8,9,10,5,4,3) => (6,7,4,3) + (7,8,9,10,5,4)
split at (5,8): (7,8,9,10,5,4)=(5,4,7,8,9,10) => (5,8,9,10) + (5,4,7,8)

Result: (6,3,18,19) + (6,7,4,3) + (5,8,9,10).

This includes (6,7) only once.

Re: Space line, how to find the red boundary?

1127204185 — Thu, 02 Jun 2022 10:27:33 GMT

Problem code

static void MyGroupMyCommand1 () { ads_name sset; resbuf *rbList = acutBuildList(RTDXF0, _T("LINE"), RTNONE); int result = acedSSGet(NULL, NULL, NULL, rbList, sset); if (result != RTNORM) { return; } Adesk::Int32 length = 0; acedSSLength(sset, &length); Acad::ErrorStatus es = Acad::eOk; resbuf StartTime; acedGetVar(_RXST("TDUSRTIMER"), &StartTime); vector<AcGePoint3dArray> dat,dat2; vector<AcGePoint3dArray> dattemp1; AcGePoint3dArray dattemp,dat3; for (int i = 0; i < length; i++) { ads_name ename; acedSSName(sset, i, ename); dattemp.removeAll(); AcDbObjectId objId = AcDbObjectId::kNull; es = acdbGetObjectId(objId, ename); if (es != Acad::eOk) { continue; } AcDbEntity* pEnt = NULL; es = acdbOpenObject(pEnt, objId, AcDb::kForRead); if (es != Acad::eOk) { continue; } if (pEnt->isKindOf(AcDbCurve::desc())) { AcDbCurve* pCurve = AcDbCurve::cast(pEnt); AcGePoint3d staPt,entPt; pCurve->getStartPoint(staPt); pCurve->getEndPoint(entPt); AcGePoint3dArray pa1; pa1.append(staPt); pa1.append(entPt); dat2.push_back(pa1); dat3.append(staPt); dat3.append(entPt); pa1.removeAll(); pCurve->close(); } pEnt->close(); } acedSSFree(sset); AcGePoint3dArray dat4 =deletePoint(dat3,1e-7); acutPrintf(_RXST("\ndat3: %d \n"), dat3.length()); acutPrintf(_RXST("\ndat4: %d \n"), dat4.length()); acutPrintf(_RXST("\ndat2: %d \n"), dat2.size()); map<int, AcGePoint3d> dats; dats.clear(); for (int i = 1; i < dat4.length()+1; i++) { dats.insert(pair<int, AcGePoint3d>(i, dat4.at(i - 1))); } vector<vector<int>> dat5; AcGePoint3d pp0,pp1; for (int i = 0; i < dat2.size(); i++) { pp0=dat2.at(i).at(0); pp1=dat2.at(i).at(1); int k1,k2; for(map<int, AcGePoint3d>::const_iterator it = dats.begin(); it != dats.end(); ++it) { if (pp0.distanceTo(it->second) < 1e-7) { k1=it->first; } if (pp1.distanceTo(it->second) < 1e-7) { k2=it->first; } } vector<int> temp; temp.push_back(k1); temp.push_back(k2); dat5.push_back(temp); acutPrintf(_RXST("\n %d = %d _ %d"), i,k1,k2); } map<int, vector<int>> dat6; for (int i = 1; i < dats.size(); i++) { vector<int> temp; temp.clear(); for (int ii = 0; ii < dat5.size(); ii++) { if (dat5.at(ii).at(0) == i) { temp.push_back(dat5.at(ii).at(1)); } if (dat5.at(ii).at(1) == i) { temp.push_back(dat5.at(ii).at(0)); } } dat6.insert(pair<int, vector<int>>(i, temp)); } vector<int> temp,temp1,temp2,temp3; vector<vector<int>> temps,temps1,temps2,temps3; for (int i = 0; i < dat5.size(); i++) { int a1=dat5.at(i).at(0); int a2=dat5.at(i).at(1); temp.push_back(a1); temp.push_back(a2); temps.push_back(temp); while (temps1.size() != 2) { temp3.clear(); for (int ii = 0; ii < temps.size(); ii++) { temp1=temps.at(ii); int a3=temp1.back(); int a4=temp1.at(temp1.size() - 2); auto it1 =dat6.find(a3); vector<int> kk=it1->second; for (int iii = 0; iii < kk.size(); iii++) { temp3=temp1; int a5 = kk.at(iii); if ( a5 != a4 ) { temp3.push_back(kk.at(iii)); temps2.push_back(temp3); } if ( a5 = a1 || temp1.size() > 2) { temp3.push_back(a5); temps1.push_back(temp3); } } } temps=temps2; } } resbuf EndTime; acedGetVar(_RXST("TDUSRTIMER"), &EndTime); ads_real UserTime; UserTime = 86400.0 * (EndTime.resval.rreal - StartTime.resval.rreal); TCHAR ChTime[50]; acdbRToS(UserTime, 2, 8, ChTime); acutPrintf(_RXST("\nTime: %s \n"), ChTime); }

Re: Space line, how to find the red boundary?

tbrammer — Tue, 07 Jun 2022 07:43:01 GMT

I haven't checked your code yet. What do you mean by "problem code"?

Does it solve the problem for you or does it not work as expected? Please specify.

Re: Space line, how to find the red boundary?

1127204185 — Tue, 07 Jun 2022 09:06:45 GMT

it not work as expected vector<int> temp,temp1,temp2,temp3; vector<vector<int>> temps,temps1,temps2,temps3; for (int i = 0; i < dat5.size(); i++) { int a1=dat5.at(i).at(0); int a2=dat5.at(i).at(1); temp.push_back(a1); temp.push_back(a2); temps.push_back(temp); while (temps1.size() != 2) { temp3.clear(); for (int ii = 0; ii < temps.size(); ii++) { temp1=temps.at(ii); int a3=temp1.back(); int a4=temp1.at(temp1.size() - 2); auto it1 =dat6.find(a3); vector<int> kk=it1->second; for (int iii = 0; iii < kk.size(); iii++) { temp3=temp1; int a5 = kk.at(iii); if ( a5 != a4 ) { temp3.push_back(kk.at(iii)); temps2.push_back(temp3); } if ( a5 = a1 || temp1.size() > 2) { temp3.push_back(a5); temps1.push_back(temp3); } } } temps=temps2; } }

Re: Space line, how to find the red boundary?

tbrammer — Wed, 08 Jun 2022 15:45:11 GMT

In MyGroupMyCommand1 () you use a function deletePoint(dat3, 1e-7). Can you post the code?

Comments in the code would be extremely helpful to show which results you expect and where things don't work as expected.

Re: Space line, how to find the red boundary?

1127204185 — Wed, 08 Jun 2022 16:08:32 GMT

//Remove duplicates AcGePoint3d

static AcGePoint3dArray deletePoint(AcGePoint3dArray ptA,double minl) { //AcGeTol pan; //pan.setEqualPoint(minl); if(ptA.length()>0) { for(int i=0;i<ptA.length()-1;i++) { for(int j=ptA.length()-1;j>i;j--) { //if((ptA.at(i)).isEqualTo(ptA.at(j))) if((ptA.at(i)).distanceTo(ptA.at(j))<=minl) { ptA.removeAt(j); } } } } return ptA; }

Re: Space line, how to find the red boundary?

tbrammer — Thu, 09 Jun 2022 13:56:22 GMT

At first glance I only see that some for loops use wrong ranges. i.e.:

map<int, AcGePoint3d> dats; for (int i = 1; i < dat4.length()+1; i++) dats.insert(pair<int, AcGePoint3d>(i, dat4.at(i - 1))); for (int i = 1; i < dats.size(); i++) // will only iterate over dats.size()-1 entries

It makes more sense to use the AcGePoint3dArray dat4 directly instead of a map. Simply use the array-index as point index! Note: Usually a map is filled like this:

dats[i] = dat4[i-1]; // will create an entry at key i

To understand the code better I have renamed some variables and made some changes. You find my code in the attached zip. Basically you have to code an algorithm that "walks along" all possible paths using connectedPointsIndices and finds all the shortest possible closed loops. This isn't trivial - and it's your job. Good luck!