How to clip line collection

[gchling]

I have a line collection(contains many line) and a PathsD(with some polylines),
I need to pick out the the lines that intersects the PathD:
int nLen = m_pPts->size();
double dPtX, dPtY;
for (int i = 0; i < nLen; i++)
{
dPtX = m_pPts->at(i).x;
dPtY = m_pPts->at(i).y;
PathD lineClip;
lineClip.push_back(PointD(centerX, centerY));
lineClip.push_back(PointD(dPtX, dPtY));

			PathsD clip, solutionClosed, solutionOpen;
			clip.push_back(lineClip);

			ClipperD clipperD;
			clipperD.AddOpenSubject(clip);
			clipperD.AddClip(*m_pFaultages);
			clipperD.Execute(ClipType::Intersection, FillRule::NonZero, solutionClosed, solutionOpen);
			// 
			if (solutionOpen.size() > 0) {
				continue;
			}			
		ptsInrange.push_back(m_pPts->at(i));
}

It runs very inefficiently, What is the right way?

[gchling]

The Clip is not changed in each loop,only the subject is changed, if there is function to remove subject, maybe can increase efficiency.

[sergey-239]

AddOpenSubject, AddSubject, AddClip, are all just wrappers of the AddPaths. AddPaths in turn does quite a lot of work by building internal structures used by clipping operation. Some internal lists get new elements from all added paths, so removal of a path is not simple (nearly the same amount of work has to be done).
What you could do is to switch from ClipperD to Clipper64 by scaling the clip and subjects yourself from PathD to Path64 moving scaling of clip out of the loop: this would eliminate the double-to-integer conversion of the clip on each iteration and the double memory allocations for every path you add to ClipperD.
Also, you could parallelize your loop using all available CPU cores. See the comment #289 (reply in thread) for the example of such parallelization.

[gchling]

I only need to judge if a line intersects the Paths，Is there high efficiency function to instead of using solutionOpen.size()?

[sergey-239]

I doubt. First you have to define a sort criteria that is not trivial for an entity that is defined with four coordinates that have different semantics: the x and y coordinates are not comparable.
The function to find an intersection of two segments shown here #317 (comment) performs quite well. On my Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz notebook it does find 10,000,000 intersections in 75ms in a single thread provided all coordinates are read from the unique memory locations. Read that referenced thread: it is all about GetIntersectPoint of the library.
So, I believe that simple search the unsorted array of your points for intersections is not worse than search some sorted as you have to account the time for sorting that would not be better than O(n Log n).

[gchling]

According to my case ,the clip segments has no change in each calculation,only the subject segment is change.
So the sort of clip segments only excute one time.
I'll compare the performance.

[gchling]

Sorting criteria is difficute to define, the desirable sort is that can quickly find all segments that intersects rectangular the subject in.
I have not got how to sort.

[sergey-239]

The only solution I can think of is a sorting the list of your clip segments along one axis, say, x and then use this solution to find out if a 2D segment potentially intersects with a segment of the clip path as if segments intersects then their projections to the axises also intersects (more precisely projections have common subsegment):
https://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/

[gchling]

Thank you. That's just what I need.