Math Question - Best way to Determine Line Segments and Dynamic Range Splits

Questions
1

So lets say I have a line ‘s’ from value ‘s0’ to value ‘s1’

s0|--------------------------------------------------------------------|s1

Now I have a range on that line we will call it ‘a’ which also has a start and end a0-a1. The values for a0 and a1 where calculated from a center point of the range and a width.

Which lets say is placed here:

s0|------------------a0|--------------------------------|a1------------|s1

Now let’s say I have a second range ‘b’ which all we are givin is the centerpoint we will call ‘bC’ and the width of the range we will call ‘bW’.

What would be the fastest way to determine if this range ‘b’ can be placed on line ‘s’ with no ranges overlapping, with this process being repeated to additional range ‘c’, ‘d’, ‘e’ etc…

I was thinking have an array

s = [0,100]

and then if I add a range it would be

rC = 50
rW = 50
for(let p=0; p<s.length; p+=2){
   let a = [p]
   let b = [p+1]
   let c = rC-(rW*0.5)
   let d = rC+(rW*0.5)
   if(a<c && b>d){
     s.splice(p,0, c, d)
   }
}

but then how do I know an area is a range and not an opening…
anyone else have any ideas?

then if they do overlap, how would I test if I can offset them by the overlap and then see if they are a valid placement.

2

You can try:

function addInterval(itrv) {
    let [a, b] = itrv;
    for (let i = 0; i < safeRanges.length; ++i) {
        let [r0, r1] = safeRanges[i];
        if (a >= r0 && b <= r1) {
            safeRanges.splice(i, 1, [r0, a], [b, r1]);
            return true;
        }
    }

    return false;
}

function showRanges() {
    return safeRanges.map((e) => `[${e[0]},${e[1]}]`).toString();
}

let safeRanges = [[0, 100]];

console.log(showRanges());

addInterval([10, 30]);
console.log(showRanges());

addInterval([4, 8]);
console.log(showRanges());

addInterval([25, 35]);
console.log(showRanges());

produces:
image

I called the array safeRanges to be clear it will contain only safe ranges (intervals), meaning intervals that can be subdivided further. In your example, [s0, a0] and [a1, s1] are safe intervals and [a0, a1] is not.

You must call addInterval with an interval [a, b] and not a center/width, but it is easy enough to convert one from the other: [a,b] == [center-width, center+width].

You can have 0-length interval, for eg:

let safeRanges = [[0, 100]];
addInterval([0,100]);
showRanges();

will produce: "[0,0],[100,100]"

You can easily get rid of them by modifying the code around safeRanges.splice(i, 1, [r0, a], [b, r1]); by testing r0 == a and b == r1 before adding the intervals into the array.

Note that it is not especially fast, the algorithm / implementation can certainly be improved (the splice is probably a bad idea for performance sake).

1 Like
3

It seems this new request shifts the problem a bit, as if I understand correctly the centerpoint is now of no use, only the width matters and you want to know if an interval of width*2 can be inserted into the game?

4

Yeah, and if it can’t find any valid ranges on the segment continue to the next segment. (there are multiple segments)

:slight_smile: its a fun question

I was thinking doing like
[{start:0, end:100, open:true}]
and then if it falls in that ‘slot’ replace the slot with the appropriate new info.
[{start:0, end :10, open:true}, {start:10, end: 80, open:false}, {start:80, end :100, open:true}]

5

If it’s only a matter of finding if a given length (width*2) fits inside an interval, then you have a problem: where to cut the interval that fits?

For eg, if you start with [0, 100] and you want to insert the [20, 30] = 10 length interval: where to cut the [0, 100] interval? You have an infinite number of solutions.

6

That’s what my code above is doing but with a simpler structure (array of 2-array instead of array of object) and without keeping the “closed” intervals: why do you want to keep the closed intervals?

7

I’m confused by what you mean now?

If I get some time I’ll make a pg to demonstrate what I am trying to do.

8

When you said:

then if they do overlap, how would I test if I can offset them by the overlap and then see if they are a valid placement.

I understood that if an interval does not fit you would like to try to move it (so change centerpoint) and see if a fit can be found.

For eg, given a segment [10, 30] and rC=15 and rW=8 => no fit (rC-rW=7 < 10), but if you move rC to 20 (for eg), then it fits because rC-rW = 12 > 10 and rC+rW = 28 < 30

If that’s not what you meant, then just forget what I said.

1 Like
9

Nope you are spot on.

Ill make a demo here today for sure where we can mess with this.

Its kinda like a “box packing” question but in 1D

10

YEEHAW
https://playground.babylonjs.com/#GMYHAD#7

Subsegmentation was the awnser!

1 Like