VLA-IntersectWith is slow

[office]

Hi there.

I have in my drawing 50 pipes(polylines) and when i search them for instersections it is slow and it is because i have 3-4 pipes with more than 300 vertices. There is any alternative faster solution?

Here is my code for intersection check:

 

(if (/= pipesHandleList nil)
(progn
(setq i 0)
(repeat (length pipesHandleList)
(setq pipeIntersection nil)
(if (/= (handent (nth i pipesHandleList)) nil)
(if (/= (vlax-ename->vla-object (handent (nth i pipesHandleList))) nil)
(if (/= (nth i pipesHandleList) mainPipeHandle)
(progn
(setq otherPipe (vlax-ename->vla-object (handent (nth i pipesHandleList))))
(setq pipeIntersection (vla-IntersectWith mainPipe otherPipe acextendnone)) ;This slows down if there is poylines with more than 200/300 vertices
))
)
)
(setq i (+ 1 i))
)
))

[martti.halminen]

I don't have time to look at this at detail level, but some ideas:

- do all the type conversions  before the checking, and use the converted data, not the original, so that you won't (re)do those inside the loop.

- as you are going through the whole list, FOREACH or MAPCAR would be better than a counted loop using NTH for access.

- don't do redundant work: if A intersects B, you don't need to check for B intersecting A

- If the real culprit is the vla-intersectwith, you could try pre-filtering before calling that: first check whether the bounding boxes of the pipes intersect: no need for an exact  check if the bboxes don't intersect. (also pre-calculate those in the conversion step to avoid re-work.)

-- 

[office]

- The real culprit is the vla-intersectwith, this is slowing down very. The others not at all. I attached a screenshot. If you mean this about the bounding boxes I think I still have the problem, because the pipes does not intersect only the bboxes.

[office]

Here I attached a DWG(2010 format) with the 46 pipes and a test.lsp. If you want to make a check, download both of the files, appload the test lisp and with the command "TEST" you can check my problem which is that is slow.

[martti.halminen]

That is the general idea. Its usability depends on how scattered your pipes are: if they are all in a heap, all the bounding boxes may intersect.

Generally, you have three kinds of pipe-pipe pairs:

A) the bounding boxes don't intersect

B) the boxes intersect, but the pipes don't. Your picture is one of these.

C) the pipes intersect, so of course also the bounding boxes intersect.

As you only need to run vla-intersectwith for the non-A cases, the potential for speed improvements depends on how large part of your stuff is case A. If close to none, this may actually make the program slower.

-- 

[martti.halminen · Accepted solution]

I tried a little non-scientific testing (just counting seconds, didn't bother with a stopwatch or instrumenting).

Using the bounding box filtering, I get about 10 % speedup for the worst cases, about 50% for the smaller pipes.

- The worst single case was when the identity check failed and the large pipe ran vla-intersectwith against itself...

If you need a faster system, you could replace vla-intersectwith by some function that would utilize the characteristics in your network. In particular, seems every intersection in your pipework is at the endpoint of one of the pipes, so instead of polyline-vs-polyline intersections you could run point-on-polyline checks.

-- 

[hmsilva]

---

@Anonymous wrote:

... 

If you need a faster system, you could replace vla-intersectwith by some function that would utilize the characteristics in your network. In particular, seems every intersection in your pipework is at the endpoint of one of the pipes, so instead of polyline-vs-polyline intersections you could run point-on-polyline checks.

...

---

Nicely thinking!

Henrique

[office]

I already use point-on-polyline check, I knew this trick, that is faster and I use it when I check for connections. Basicly I check the 0.0 and (vla-get-length pipe) positions if the result is nil I come with the vla-intersectwith to check if the pipes are intersecting/crossing each other or not.

But there is cases when other pipes do not connect with each other, they only intersecting/crossing with each other and I have to use the vla-intersectwith to find the right position between the 0.0 and (vla-get-length pipe).

I will use the bounding boxes to speed up with a few procent.

Thank you for the support 🙂

[martti.halminen]

I'm not quite clear are we talking about the same thing. Seems to me we could categorise the intersections to three kinds:

L - pipe endpoints connected

T - endpoint of one pipe connected somewhere along the length of other, not at its endpoint

X - pipes intersect at a point which is not the endpoint of either one.

So L would need an endpoints-equal check, T would be point-on-polyline and only X would need polyline-polyline intersection.

Depending on the logic of the pipework this gives one additional chance of filtering: are multiple connections between the same two pipes possible?

If not, you would only need to check for an X connection if there isn't an L or T already found for that pair of pipes (and the bounding boxes intersect).

-- 

[office]

Here is a screenshot with the connection cases.

[martti.halminen]

Well, that ring system and waste pipe kill most of the non-intersecting ideas, so we are left with reducing the calls to vla-intersectwith by better filtering so that not every pipe needs to be checked.

One way would be partitioning: divide the area into some kind of grid, and handle each box separately, then combine the results.

Another would be replacing the bounding boxes with better-fitting lightweight constructs, convex hull is one way, another would be covering the pipe by several smaller boxes instead of one large one.

And for heavyweight stuff it could be useful to see what the spatial database people have invented, see for example http://www.comp.nus.edu.sg/~ooibc/spatialsurvey.pdf

-- 

[office]

There is still a problem especialy with the convex hull, if there is a little convex hull in a big one, there is no intersection. If I use bounding box i can check for the 4 points if it is inside of a big bounding box or the 2 bounding box intersect with each other. Here is a screenshot.

I think I will remain for the momment with the point check on polyline and if the result is nil I wil run the bounding box check to find out if I need to use the vla-intersectwith.

[martti.halminen]

One way to recognize the polygon fully inside another -situation is to run a point-inside-polygon check on one point of the smaller polygon.

(Given that we have already established that the polygon edges don't intersect)

One algorithm for this is to draw a line from the point to infinity and count the intersections with the other polygon: if odd, you are inside, even (or zero), you are outside.

[Or run the check both ways if it is unclear which polygon would be the smaller one]

--