I have a large static collection of 'walls'. These are held as a two item array of Vector3 points and can be considered a line-segment (it's a 2D problem so we're only interested in X and Z). There are roughly 1000 of these.

There is a large list of points - (in the millions) held in a list called pointCollection and a much smaller (in the hundreds) of Vector3 points held in a second list called testCollection.

Combining each item of pointCollection and testCollection and testing each of these segments against the wall collection allows for some work to be done if there are no intersections.

My current approach works well but is too slow and as such cannot be used without some improvement.

My working (but slow) code below shows my initial approach both in the test and intersection function.

//iterate over the point collection
foreach (Vector3 myPoint in pointCollection){

    //iterate over the test collection
    foreach (Vector3 myTest in testCollection){

        //assume no intersection until proven wrong
        bool pointClean = true;
        
        //test against all walls
        foreach (Vector3[] myWall in myWalls){
        if (intersects(myPoint.x, myPoint.z, myTest.x, myTest.z, myWall[0].x, myWall[0].z, myWall[1].x, myWall[1].z) == true){
            //Break to avoid unneeded tests - this point has already intersected
            pointClean = false;
            break;
        }
    }
    
    if (pointClean == true){
        //do some work if the point is clean
    }               
}

//tests the intersection of line segment (ab -> cd) vs (pq -> rs)
public bool intersects(float a, float b, float c, float d, float p, float q, float r, float s) {
    float det = (c - a) * (s - q) - (r - p) * (d - b);
    float gamma;
    float lambda;
        
    if (det == 0) {
        return false;
    } else {
        lambda = ((s - q) * (r - a)   (p - r) * (s - b)) / det;
        gamma = ((b - d) * (r - a)   (c - a) * (s - b)) / det;
        return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
    }
}

I feel there maybe some shortcuts available 'quickly' exclude some possible overlaps by using rectangles or sorted lists but I'm drawing blanks.

CodePudding user response：

If two walls can be intersecting, then first make them non-intersecting by splitting walls at such intersection points.

Given the numbers, I would reverse the loops, and have the iteration over the smaller (testCollection) collection first.

For each myTest of those, transpose the walls to polar coordinates with myTest as the origin, and sort those polar points by their angle (i.e. their angular coordinate). Iterate these angles (and associated edges) always retaining the wall that is closest to the origin (or none, when there is an angle segment without any wall), so creating a sorted list of wall segments that -- from the viewpoint of myTest -- are non-overlapping. Pay attention to also deal with the segment between the largest and least angle (wrapping around).

Then iterate the larger pointCollection, converting each myPoint point to the same polar coordinate system. With a binary search on angle, you find zero or one wall to check for an intersection.

Make sure to have quick exits in the intersection-check: if the distance (i.e. the radial polar coordinate) of myPoint is greater than that of both end points of the found segment, then there is an intersection. If it is less than both, then there is no intersection. For the remaining case, determine the distance at which the line through myPoint would intersect and compare it with the actual distance of myPoint.

It may be possible to gain some efficiency by using an alternative to polar coordinates, using the slope instead of the angle, and the square of the distance to avoid the square root operation.

CodePudding user response：

I tried and found the answer from Trincot was good and did yield some gains however they were not game-changing. I was able to solve the problem however by focusing on 'fail fast' part of the problem (i.e. gain positive intersections early so as to avoid additional work).

Basically the principle required was that if a wall was 'hit' then it was quite likely to be hit again by points nearby (it either being closer to the test point or possibly just bigger).

When an intersection with a wall occurred that wall could 'rank up' in priority for future tests. This creates a positive feedback loop with the most likely intersections being tested first and therefore increasing their rankings - therefore reducing the need for additional tests.

This achieved roughly a 10-fold increase in overall speed with my dataset - some care was required to maintain the rank ordered list of walls and reset/shuffle it at appropriate points so the sort algorithm itself didn't become weighty.