Mixing
How to effectively check whether a path is inside a series of bounding boxes?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Given a series of interconnected rectangular bounding boxes,
and a path that is a described by a polynomial (or a polynomial spline),
how can I check whether the path is entirely inside the bounding boxes, precisely?
(as shown in the below figure)
geometry computer-science bezier-curve
edited Jul 21 at 5:02
Parcly Taxel
33.6k136588
asked Jul 17 at 2:50
Nyaruko
1185
add a comment |Â
up vote
2
down vote
favorite
Given a series of interconnected rectangular bounding boxes,
and a path that is a described by a polynomial (or a polynomial spline),
how can I check whether the path is entirely inside the bounding boxes, precisely?
(as shown in the below figure)
geometry computer-science bezier-curve
edited Jul 21 at 5:02
Parcly Taxel
33.6k136588
asked Jul 17 at 2:50
Nyaruko
1185
The curve only satisfies inequalities by function of box (line).
– Takahiro Waki
Jul 17 at 3:33
@TakahiroWaki, yes correct, and I am actually looking for a method that could effectively split the trajectory into multiple parts and perform the check on each individual of them. Currently, I perform a binary search, but I wonder is there any better method.
– Nyaruko
Jul 17 at 4:14
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Given a series of interconnected rectangular bounding boxes,
and a path that is a described by a polynomial (or a polynomial spline),
how can I check whether the path is entirely inside the bounding boxes, precisely?
(as shown in the below figure)
geometry computer-science bezier-curve
edited Jul 21 at 5:02
Parcly Taxel
33.6k136588
asked Jul 17 at 2:50
Nyaruko
1185
Given a series of interconnected rectangular bounding boxes,
and a path that is a described by a polynomial (or a polynomial spline),
how can I check whether the path is entirely inside the bounding boxes, precisely?
(as shown in the below figure)
geometry computer-science bezier-curve
edited Jul 21 at 5:02
Parcly Taxel
33.6k136588
asked Jul 17 at 2:50
Nyaruko
1185
edited Jul 21 at 5:02
Parcly Taxel
33.6k136588
edited Jul 21 at 5:02
Parcly Taxel
33.6k136588
edited Jul 21 at 5:02
Parcly Taxel
33.6k136588
33.6k136588
asked Jul 17 at 2:50
Nyaruko
1185
asked Jul 17 at 2:50
Nyaruko
1185
asked Jul 17 at 2:50
Nyaruko
1185
1185
The curve only satisfies inequalities by function of box (line).
– Takahiro Waki
Jul 17 at 3:33
@TakahiroWaki, yes correct, and I am actually looking for a method that could effectively split the trajectory into multiple parts and perform the check on each individual of them. Currently, I perform a binary search, but I wonder is there any better method.
– Nyaruko
Jul 17 at 4:14
add a comment |Â
The curve only satisfies inequalities by function of box (line).
– Takahiro Waki
Jul 17 at 3:33
@TakahiroWaki, yes correct, and I am actually looking for a method that could effectively split the trajectory into multiple parts and perform the check on each individual of them. Currently, I perform a binary search, but I wonder is there any better method.
– Nyaruko
Jul 17 at 4:14
The curve only satisfies inequalities by function of box (line).
– Takahiro Waki
Jul 17 at 3:33
The curve only satisfies inequalities by function of box (line).
– Takahiro Waki
Jul 17 at 3:33
@TakahiroWaki, yes correct, and I am actually looking for a method that could effectively split the trajectory into multiple parts and perform the check on each individual of them. Currently, I perform a binary search, but I wonder is there any better method.
– Nyaruko
Jul 17 at 4:14
@TakahiroWaki, yes correct, and I am actually looking for a method that could effectively split the trajectory into multiple parts and perform the check on each individual of them. Currently, I perform a binary search, but I wonder is there any better method.
– Nyaruko
Jul 17 at 4:14
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Let the curves in the spline be given by parametric expressions $(x(t),y(t))$ with $0le tle1$ as is common in computer graphics.
Consider each pair of curve and rectangle in turn. For the four edges of that rectangle, determine all $t$-values on the curve that correspond to intersections, of which there may be none. This is relatively simple to accomplish by rotating the edge onto an axis and finding roots of the component polynomials of the resulting curve, as detailed for example here.
Then determine if $t=0$ on the curve is in the rectangle; from there mark the found intersection $t$-parameters as entering or exiting the rectangle alternately. This gives a subset of $[0,1]$ corresponding to that part of the curve within the rectangle. For a given curve, take the union of said subsets arising from its pairings with all rectangles; it lies entirely within the bounding boxes if the union is the whole interval $[0,1]$.
The entire spline is then inside the bounding boxes if each of its component curves is.
answered Jul 17 at 5:18
Parcly Taxel
33.6k136588
add a comment |Â
up vote
3
down vote
Another answer has already suggested a specific algorithm, so I won't go into too many details on that. I think it's worth mentioning, though, that there are two properties of splines that you can put to use for this:
- A spline is a parametrized convex combination of its control points, and is thus contained in their convex hull.
- A spline can be efficiently subdivided into shorter splines of the same type.
Together, these allow for a recursive algorithm to check whether a spline is contained in a convex area (e.g. a rectangle): If an endpoint is outside the area, it isn't. If all control points are inside the area, it is. If neither is the case, subdivide and recursively apply the algorithm to the components.
You can find more on these properties at this SO question and the links provided there.
answered Jul 17 at 5:36
joriki
164k10180328
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Let the curves in the spline be given by parametric expressions $(x(t),y(t))$ with $0le tle1$ as is common in computer graphics.
Consider each pair of curve and rectangle in turn. For the four edges of that rectangle, determine all $t$-values on the curve that correspond to intersections, of which there may be none. This is relatively simple to accomplish by rotating the edge onto an axis and finding roots of the component polynomials of the resulting curve, as detailed for example here.
Then determine if $t=0$ on the curve is in the rectangle; from there mark the found intersection $t$-parameters as entering or exiting the rectangle alternately. This gives a subset of $[0,1]$ corresponding to that part of the curve within the rectangle. For a given curve, take the union of said subsets arising from its pairings with all rectangles; it lies entirely within the bounding boxes if the union is the whole interval $[0,1]$.
The entire spline is then inside the bounding boxes if each of its component curves is.
answered Jul 17 at 5:18
Parcly Taxel
33.6k136588
add a comment |Â
up vote
3
down vote
accepted
Let the curves in the spline be given by parametric expressions $(x(t),y(t))$ with $0le tle1$ as is common in computer graphics.
Consider each pair of curve and rectangle in turn. For the four edges of that rectangle, determine all $t$-values on the curve that correspond to intersections, of which there may be none. This is relatively simple to accomplish by rotating the edge onto an axis and finding roots of the component polynomials of the resulting curve, as detailed for example here.
Then determine if $t=0$ on the curve is in the rectangle; from there mark the found intersection $t$-parameters as entering or exiting the rectangle alternately. This gives a subset of $[0,1]$ corresponding to that part of the curve within the rectangle. For a given curve, take the union of said subsets arising from its pairings with all rectangles; it lies entirely within the bounding boxes if the union is the whole interval $[0,1]$.
The entire spline is then inside the bounding boxes if each of its component curves is.
answered Jul 17 at 5:18
Parcly Taxel
33.6k136588
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Let the curves in the spline be given by parametric expressions $(x(t),y(t))$ with $0le tle1$ as is common in computer graphics.
Consider each pair of curve and rectangle in turn. For the four edges of that rectangle, determine all $t$-values on the curve that correspond to intersections, of which there may be none. This is relatively simple to accomplish by rotating the edge onto an axis and finding roots of the component polynomials of the resulting curve, as detailed for example here.
Then determine if $t=0$ on the curve is in the rectangle; from there mark the found intersection $t$-parameters as entering or exiting the rectangle alternately. This gives a subset of $[0,1]$ corresponding to that part of the curve within the rectangle. For a given curve, take the union of said subsets arising from its pairings with all rectangles; it lies entirely within the bounding boxes if the union is the whole interval $[0,1]$.
The entire spline is then inside the bounding boxes if each of its component curves is.
answered Jul 17 at 5:18
Parcly Taxel
33.6k136588
Let the curves in the spline be given by parametric expressions $(x(t),y(t))$ with $0le tle1$ as is common in computer graphics.
Consider each pair of curve and rectangle in turn. For the four edges of that rectangle, determine all $t$-values on the curve that correspond to intersections, of which there may be none. This is relatively simple to accomplish by rotating the edge onto an axis and finding roots of the component polynomials of the resulting curve, as detailed for example here.
Then determine if $t=0$ on the curve is in the rectangle; from there mark the found intersection $t$-parameters as entering or exiting the rectangle alternately. This gives a subset of $[0,1]$ corresponding to that part of the curve within the rectangle. For a given curve, take the union of said subsets arising from its pairings with all rectangles; it lies entirely within the bounding boxes if the union is the whole interval $[0,1]$.
The entire spline is then inside the bounding boxes if each of its component curves is.
answered Jul 17 at 5:18
Parcly Taxel
33.6k136588
edited Jul 17 at 6:28
answered Jul 17 at 5:18
Parcly Taxel
33.6k136588
answered Jul 17 at 5:18
Parcly Taxel
33.6k136588
answered Jul 17 at 5:18
Parcly Taxel
33.6k136588
33.6k136588
add a comment |Â
add a comment |Â
up vote
3
down vote
Another answer has already suggested a specific algorithm, so I won't go into too many details on that. I think it's worth mentioning, though, that there are two properties of splines that you can put to use for this:
- A spline is a parametrized convex combination of its control points, and is thus contained in their convex hull.
- A spline can be efficiently subdivided into shorter splines of the same type.
Together, these allow for a recursive algorithm to check whether a spline is contained in a convex area (e.g. a rectangle): If an endpoint is outside the area, it isn't. If all control points are inside the area, it is. If neither is the case, subdivide and recursively apply the algorithm to the components.
You can find more on these properties at this SO question and the links provided there.
answered Jul 17 at 5:36
joriki
164k10180328
add a comment |Â
up vote
3
down vote
Another answer has already suggested a specific algorithm, so I won't go into too many details on that. I think it's worth mentioning, though, that there are two properties of splines that you can put to use for this:
- A spline is a parametrized convex combination of its control points, and is thus contained in their convex hull.
- A spline can be efficiently subdivided into shorter splines of the same type.
Together, these allow for a recursive algorithm to check whether a spline is contained in a convex area (e.g. a rectangle): If an endpoint is outside the area, it isn't. If all control points are inside the area, it is. If neither is the case, subdivide and recursively apply the algorithm to the components.
You can find more on these properties at this SO question and the links provided there.
answered Jul 17 at 5:36
joriki
164k10180328
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Another answer has already suggested a specific algorithm, so I won't go into too many details on that. I think it's worth mentioning, though, that there are two properties of splines that you can put to use for this:
- A spline is a parametrized convex combination of its control points, and is thus contained in their convex hull.
- A spline can be efficiently subdivided into shorter splines of the same type.
Together, these allow for a recursive algorithm to check whether a spline is contained in a convex area (e.g. a rectangle): If an endpoint is outside the area, it isn't. If all control points are inside the area, it is. If neither is the case, subdivide and recursively apply the algorithm to the components.
You can find more on these properties at this SO question and the links provided there.
answered Jul 17 at 5:36
joriki
164k10180328
Another answer has already suggested a specific algorithm, so I won't go into too many details on that. I think it's worth mentioning, though, that there are two properties of splines that you can put to use for this:
- A spline is a parametrized convex combination of its control points, and is thus contained in their convex hull.
- A spline can be efficiently subdivided into shorter splines of the same type.
Together, these allow for a recursive algorithm to check whether a spline is contained in a convex area (e.g. a rectangle): If an endpoint is outside the area, it isn't. If all control points are inside the area, it is. If neither is the case, subdivide and recursively apply the algorithm to the components.
You can find more on these properties at this SO question and the links provided there.
answered Jul 17 at 5:36
joriki
164k10180328
answered Jul 17 at 5:36
joriki
164k10180328
answered Jul 17 at 5:36
joriki
164k10180328
answered Jul 17 at 5:36
joriki
164k10180328
164k10180328
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854090%2fhow-to-effectively-check-whether-a-path-is-inside-a-series-of-bounding-boxes%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
The curve only satisfies inequalities by function of box (line).
– Takahiro Waki
Jul 17 at 3:33
@TakahiroWaki, yes correct, and I am actually looking for a method that could effectively split the trajectory into multiple parts and perform the check on each individual of them. Currently, I perform a binary search, but I wonder is there any better method.
– Nyaruko
Jul 17 at 4:14