The heuristic for fast division of space?

Question

The heuristic for fast division of space?

I have a (sub) space filled with segments N

. These line segments are always part of a convex polygon. It might look like this:

I want to do a heuristic to select a line segment to divide space. The selected segment support line will then divide the space. There are two heuristic factors that work against each other:

The line segment should distribute space evenly; subspace A must have as many line segments as subspace B ( balance )
The support line of the line segment should intersect (split) as few other line segments as possible ( freedom )

Example:

Blue line: perfect freedom, very bad balance.

Red line: very poor freedom, mediocre balance.

Green line: bad freedom, great balance.

Purple line: good freedom, decent balance.

In the example above, the combined heuristic might select the purple line.

Now I could just loop through each line segment and compare it to every other line segment (seeing which ones it crosses over and how balanced they are on each side). But this requires surgery O(N^2)

. I would prefer something that works in O(N log N)

.

Any ideas on an algorithm O(N log N)

that goes through the line segments and gives them a score? One of my ideas was to sort the segments three times and form multiple quadrants:

The quadrant center gives an idea of where most of the line segments are. So maybe use them to find a line segment near that center and check if its orientation is correct relative to the quadrants. Somehow. This will give a good balance.

For the intersection, I thought about creating bounding rectangles for the segments and sorting them into a tree, which would possibly speed up the intersection evaluation?

Some additional hints (that my input looks like a lot of time)

Most segments are axial (pure X or Y orientation)
Most of the segments are small compared to their distribution.

Thanks for any new ideas or ideas - the smallest hint of data structure or strategy will help a lot!

+3

algorithm time-complexity computational-geometry heuristics

bombax 03 Aug 15 at 18:37

source to share

1 answer

bombax · Accepted Answer · 2015-08-16T17:33:52+0000

Decision

I found a heuristic that works great for my BSP tree purposes and which is also very interesting to analyze. In the code below, I first tried to use the AABB tree to ask "which segments intersect this line". But even that was too slow, so I ended up just going with an expensive initial comparison algorithm O(N^2)

that sped up quickly as the BSP tree was built using somewhat clever observation!

Let each BSP node keep track of which line segments it has still left inside its subspace (and from which it should choose the next separator).
Let each segment has four values associated with it: posCount

, negCount

, introduced

and saved

. Let it also have a link partner

to another segment if it was split (otherwise it is null

).
Initialize splitters in the root node (i.e. ALL of them) with the following O(N^2)

algo:

Algorithm calcRelationCounts(splitters S)

:O(N^2)

for all splitters s in S
    s.posCount = s.negCount = s.introduced = s.saved = 0
    for all splitters vs in S
        if (s == vs) continue
        if vs is fully on the positive side of the plane of s
            s.posCount++
        else if vs is fully on the negative side of the plane of s
            s.negCount++
        else if vs intersects the plane of s
            s.negCount++, s.posCount++, s.introduced++
        else if vs is coplanar with s
            s.saved++

For each node with the remaining splitters, choose the one that maximizes the following:

Algorithm evaluate(...)

where treeDepth = floor(log2(splitterCountAtThisNode))

:O(1)

evaluate(posCount, negCount, saved, introduced, treeDepth) {
    float f;
    if (treeDepth >= EVALUATE_X2) {
        f = EVALUATE_V2;
    } else if (treeDepth >= EVALUATE_X1) {
        float r = treeDepth - EVALUATE_X1;
        float w = EVALUATE_X2 - EVALUATE_X1;
        f = ((w-r) * EVALUATE_V1 + r * EVALUATE_V2) / w;
    } else {
        f = EVALUATE_V1;
    }

    float balanceScore = -f * BALANCE_WEIGHT * abs(posCount - negCount);
    float freedomScore = (1.0f-f) * (SAVED_WEIGHT * saved - INTRO_WEIGHT * introduced);
    return freedomScore + balanceScore;
}

With the following magic numbers that my optimization algorithm used:

#define BALANCE_WEIGHT 437
#define INTRO_WEIGHT 750
#define SAVED_WEIGHT 562
#define EVALUATE_X1 3
#define EVALUATE_X2 31
#define EVALUATE_V1 0.0351639f
#define EVALUATE_V2 0.187508f

Use this separator as separator for this node, call it SEL. Then split all the splitters on that node into three groups positives

, negatives

and remnants

:

Algorithm distributeSplitters()

:

for all splitters s at this node
    s.partner = null
    if s == SEL then add s to "remnants"
    else
        if s is fully on the positive side of SEL
            add s to "positives"
        else if s is fully on the negative side of SEL
            add s to "negatives
        else if s intersects SEL
            split s into two appropriate segments sp and sn
            sp.partner = sn, sn.partner = sp
            add sn to "negatives", sp to "positives" and s to "remnants"
        else if s coplanar with SEL
            add s to "remnants"

// the clever bit
if (positives.size() > negatives.size())
    calcRelationCounts(negatives)
    updateRelationCounts(positives, negatives, remnants)
else
    calcRelationCounts(positives)
    updateRelationCounts(negatives, positives, remnants)

add positives and negatives to appropriate child nodes for further processing

The smart thing I figured out here is that often, especially the first couple of heuristic sections above, will create very unbalanced splits (but very free). The problem is that you get " O(N^2) + O((N-n)^2)" + ...

which is terrible when n

small! Instead, I figured out that instead we can hard-code the smallest split that takes O(N^2)

, which is not bad, and then just iterate over each bit of the splitter, subtracting the counts from the smaller split part that only accepts O(Nn)

which is much better than O(N^2)

.Here is the code for updateRelationCounts()

:

Algorithm updateRelationCounts()

:

updateRelationCounts(toUpdate, removed, remnants) {
    for all splitters s in toUpdate
            for all splitters vs in removed, then remnants
                if vs has a partner
                    if the partner intersects s
                        s.posCount++, s.negCount++, s.introduced++
                    else if the partner is fully on the positive side of s
                        s.posCount++
                    else if the partner is fully on the negative side of s
                        s.negCount++
                    else if the partner is coplanar with s
                        s.saved++
                else
                    if vs intersects s
                        s.posCount--, s.negCount--, s.introduced--
                    else if vs is fully on the positive side of s
                        s.posCount--
                    else if vs is fully on the negative side of s
                        s.negCount--
                    else if vs is coplanar with s
                        s.saved--

I've checked this carefully now and it seems like the logic is correct in that the update changes correctly, posCount

etc., so that they are the same as they would be if they were programmed again!

The heuristic for fast division of space?

Decision

More articles: