Computing the intersections of arbitrary number of planes
$begingroup$
Imagine three sets of planes (A, B, and C). The planes in each set are parallel and evenly spaced and so can be defined by a plane equation and a scalar representing the distance between planes. If all three of these sets were orthogonal (as a contrived example) then by computing the intersections of all the planes somehow, it would generate a lattice consisting of an edge anywhere that any two planes intersect and a vertex at any point where three planes intersect. Assume that I am generating this lattice over a finite bounding volume (let's just make it a cube for simplicity and assume the set of planes exist within said cube). I can easily brute-force solve this by intersecting the sets of planes two sets at a time (i.e. AB, BC, and AC) generating a set of edges and then finding the intersections of each edge with every other edge, but this algorithm would be O(really bad).
I would like to find the lattice generated by an arbitrary number of sets of planes where each set contains parallel planes that are uniformly spaced (although the spacing for each set is arbitrary). I would like to do this in O(decent) if that's possible. I know that I can break this problem down exactly the same way and solve for pairs of planes and then intersect all the edges but this problem gets worse and worse as the number of planes increases. I feel like I can probably solve this more easily by transforming every set of planes into a single plane that intersects the origin, finding the intersecting lines, then intersecting all of those lines and then generating the rest of the lattice since I know the spacing of vertices (if any) on each line will correspond to the distance along that line between the planes for each set (which is again known since the spacing is constant for each set) but this would still be inefficient for an arbitrary number of planes. I'm willing to accept that this is just a hard problem to solve and that brute-forcing it may be my only option but I figured that I'd ask in case anyone has any insight on how I can make this better somehow.
Also, it is safe to ignore the case where the sets of planes never intersect at all or only intersect along an edge. The application of this problem is model synthesis (relevant paper if anyone is interested: http://gamma.cs.unc.edu/synthesis/papers/constraint.pdf)
linear-algebra matrices geometry algebraic-geometry
edited Jan 4 at 13:09
Paul Frost
10.3k3933
asked Mar 28 '14 at 19:30
Jeff TuckerJeff Tucker
1062
$endgroup$
add a comment |
$begingroup$
Imagine three sets of planes (A, B, and C). The planes in each set are parallel and evenly spaced and so can be defined by a plane equation and a scalar representing the distance between planes. If all three of these sets were orthogonal (as a contrived example) then by computing the intersections of all the planes somehow, it would generate a lattice consisting of an edge anywhere that any two planes intersect and a vertex at any point where three planes intersect. Assume that I am generating this lattice over a finite bounding volume (let's just make it a cube for simplicity and assume the set of planes exist within said cube). I can easily brute-force solve this by intersecting the sets of planes two sets at a time (i.e. AB, BC, and AC) generating a set of edges and then finding the intersections of each edge with every other edge, but this algorithm would be O(really bad).
I would like to find the lattice generated by an arbitrary number of sets of planes where each set contains parallel planes that are uniformly spaced (although the spacing for each set is arbitrary). I would like to do this in O(decent) if that's possible. I know that I can break this problem down exactly the same way and solve for pairs of planes and then intersect all the edges but this problem gets worse and worse as the number of planes increases. I feel like I can probably solve this more easily by transforming every set of planes into a single plane that intersects the origin, finding the intersecting lines, then intersecting all of those lines and then generating the rest of the lattice since I know the spacing of vertices (if any) on each line will correspond to the distance along that line between the planes for each set (which is again known since the spacing is constant for each set) but this would still be inefficient for an arbitrary number of planes. I'm willing to accept that this is just a hard problem to solve and that brute-forcing it may be my only option but I figured that I'd ask in case anyone has any insight on how I can make this better somehow.
Also, it is safe to ignore the case where the sets of planes never intersect at all or only intersect along an edge. The application of this problem is model synthesis (relevant paper if anyone is interested: http://gamma.cs.unc.edu/synthesis/papers/constraint.pdf)
linear-algebra matrices geometry algebraic-geometry
edited Jan 4 at 13:09
Paul Frost
10.3k3933
asked Mar 28 '14 at 19:30
Jeff TuckerJeff Tucker
1062
$endgroup$
add a comment |
$begingroup$
Imagine three sets of planes (A, B, and C). The planes in each set are parallel and evenly spaced and so can be defined by a plane equation and a scalar representing the distance between planes. If all three of these sets were orthogonal (as a contrived example) then by computing the intersections of all the planes somehow, it would generate a lattice consisting of an edge anywhere that any two planes intersect and a vertex at any point where three planes intersect. Assume that I am generating this lattice over a finite bounding volume (let's just make it a cube for simplicity and assume the set of planes exist within said cube). I can easily brute-force solve this by intersecting the sets of planes two sets at a time (i.e. AB, BC, and AC) generating a set of edges and then finding the intersections of each edge with every other edge, but this algorithm would be O(really bad).
I would like to find the lattice generated by an arbitrary number of sets of planes where each set contains parallel planes that are uniformly spaced (although the spacing for each set is arbitrary). I would like to do this in O(decent) if that's possible. I know that I can break this problem down exactly the same way and solve for pairs of planes and then intersect all the edges but this problem gets worse and worse as the number of planes increases. I feel like I can probably solve this more easily by transforming every set of planes into a single plane that intersects the origin, finding the intersecting lines, then intersecting all of those lines and then generating the rest of the lattice since I know the spacing of vertices (if any) on each line will correspond to the distance along that line between the planes for each set (which is again known since the spacing is constant for each set) but this would still be inefficient for an arbitrary number of planes. I'm willing to accept that this is just a hard problem to solve and that brute-forcing it may be my only option but I figured that I'd ask in case anyone has any insight on how I can make this better somehow.
Also, it is safe to ignore the case where the sets of planes never intersect at all or only intersect along an edge. The application of this problem is model synthesis (relevant paper if anyone is interested: http://gamma.cs.unc.edu/synthesis/papers/constraint.pdf)
linear-algebra matrices geometry algebraic-geometry
edited Jan 4 at 13:09
Paul Frost
10.3k3933
asked Mar 28 '14 at 19:30
Jeff TuckerJeff Tucker
1062
$endgroup$
Imagine three sets of planes (A, B, and C). The planes in each set are parallel and evenly spaced and so can be defined by a plane equation and a scalar representing the distance between planes. If all three of these sets were orthogonal (as a contrived example) then by computing the intersections of all the planes somehow, it would generate a lattice consisting of an edge anywhere that any two planes intersect and a vertex at any point where three planes intersect. Assume that I am generating this lattice over a finite bounding volume (let's just make it a cube for simplicity and assume the set of planes exist within said cube). I can easily brute-force solve this by intersecting the sets of planes two sets at a time (i.e. AB, BC, and AC) generating a set of edges and then finding the intersections of each edge with every other edge, but this algorithm would be O(really bad).
I would like to find the lattice generated by an arbitrary number of sets of planes where each set contains parallel planes that are uniformly spaced (although the spacing for each set is arbitrary). I would like to do this in O(decent) if that's possible. I know that I can break this problem down exactly the same way and solve for pairs of planes and then intersect all the edges but this problem gets worse and worse as the number of planes increases. I feel like I can probably solve this more easily by transforming every set of planes into a single plane that intersects the origin, finding the intersecting lines, then intersecting all of those lines and then generating the rest of the lattice since I know the spacing of vertices (if any) on each line will correspond to the distance along that line between the planes for each set (which is again known since the spacing is constant for each set) but this would still be inefficient for an arbitrary number of planes. I'm willing to accept that this is just a hard problem to solve and that brute-forcing it may be my only option but I figured that I'd ask in case anyone has any insight on how I can make this better somehow.
Also, it is safe to ignore the case where the sets of planes never intersect at all or only intersect along an edge. The application of this problem is model synthesis (relevant paper if anyone is interested: http://gamma.cs.unc.edu/synthesis/papers/constraint.pdf)
linear-algebra matrices geometry algebraic-geometry
linear-algebra matrices geometry algebraic-geometry
edited Jan 4 at 13:09
Paul Frost
10.3k3933
asked Mar 28 '14 at 19:30
Jeff TuckerJeff Tucker
1062
edited Jan 4 at 13:09
Paul Frost
10.3k3933
asked Mar 28 '14 at 19:30
Jeff TuckerJeff Tucker
1062
edited Jan 4 at 13:09
Paul Frost
10.3k3933
edited Jan 4 at 13:09
Paul Frost
10.3k3933
edited Jan 4 at 13:09
Paul Frost
10.3k3933
10.3k3933
asked Mar 28 '14 at 19:30
Jeff TuckerJeff Tucker
1062
asked Mar 28 '14 at 19:30
Jeff TuckerJeff Tucker
1062
asked Mar 28 '14 at 19:30
Jeff TuckerJeff Tucker
1062
1062
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Something like: $ (x-1)(x-3)(x-5) = 1/100 $ , $ (y-4)(y-7)(y-10) = 1/100 $, $ (z-1)(z-4)(z-7) = 1/100 $ ?
answered Mar 28 '14 at 20:07
AlanAlan
1,924815
$endgroup$
$begingroup$
Oh, you want to compute the intersection to store line segments by pairwise intersection, and points by triple intersection?
$endgroup$
– Alan
Mar 28 '14 at 20:18
$begingroup$
Yes, I need the line segments and points, although the points may be the intersection of more than three planes. Just the edges and vertices from the thing you rendered there. I also need to ensure that I know which line segments and which planes are associated with each vertex
$endgroup$
– Jeff Tucker
Mar 28 '14 at 21:20
$begingroup$
Mathematica statement that brings up 27 points in a list: NSolve[(x - 1) (x - 3) (x - 5) == 1/100 && (y - 4) (y - 7) (y - 10) == 1/100 && (z - 1) (z - 4) (z - 7) == 1/100, {x, y, z}] ---- How big would the table be,? Can it be computed once and stored?
$endgroup$
– Alan
Mar 28 '14 at 21:32
$begingroup$
Yes this is a pre-computation step so I can store it easily. The table could potentially be massive also, and the spacing between the planes is only guaranteed to be the same within a single set; different sets could be spaced completely differently. I'm really not seeing much besides a divide-and-conquer approach that involves computing intersections of small numbers of planes and then merging the results. I could use many systems of linear equations and solve them all too, but it seems like that would be just as inefficient. I'm hoping there's some sort of clever shortcut solution
$endgroup$
– Jeff Tucker
Mar 28 '14 at 22:55
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f730597%2fcomputing-the-intersections-of-arbitrary-number-of-planes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Something like: $ (x-1)(x-3)(x-5) = 1/100 $ , $ (y-4)(y-7)(y-10) = 1/100 $, $ (z-1)(z-4)(z-7) = 1/100 $ ?
answered Mar 28 '14 at 20:07
AlanAlan
1,924815
$endgroup$
$begingroup$
Oh, you want to compute the intersection to store line segments by pairwise intersection, and points by triple intersection?
$endgroup$
– Alan
Mar 28 '14 at 20:18
$begingroup$
Yes, I need the line segments and points, although the points may be the intersection of more than three planes. Just the edges and vertices from the thing you rendered there. I also need to ensure that I know which line segments and which planes are associated with each vertex
$endgroup$
– Jeff Tucker
Mar 28 '14 at 21:20
$begingroup$
Mathematica statement that brings up 27 points in a list: NSolve[(x - 1) (x - 3) (x - 5) == 1/100 && (y - 4) (y - 7) (y - 10) == 1/100 && (z - 1) (z - 4) (z - 7) == 1/100, {x, y, z}] ---- How big would the table be,? Can it be computed once and stored?
$endgroup$
– Alan
Mar 28 '14 at 21:32
$begingroup$
Yes this is a pre-computation step so I can store it easily. The table could potentially be massive also, and the spacing between the planes is only guaranteed to be the same within a single set; different sets could be spaced completely differently. I'm really not seeing much besides a divide-and-conquer approach that involves computing intersections of small numbers of planes and then merging the results. I could use many systems of linear equations and solve them all too, but it seems like that would be just as inefficient. I'm hoping there's some sort of clever shortcut solution
$endgroup$
– Jeff Tucker
Mar 28 '14 at 22:55
add a comment |
$begingroup$
Something like: $ (x-1)(x-3)(x-5) = 1/100 $ , $ (y-4)(y-7)(y-10) = 1/100 $, $ (z-1)(z-4)(z-7) = 1/100 $ ?
answered Mar 28 '14 at 20:07
AlanAlan
1,924815
$endgroup$
$begingroup$
Oh, you want to compute the intersection to store line segments by pairwise intersection, and points by triple intersection?
$endgroup$
– Alan
Mar 28 '14 at 20:18
$begingroup$
Yes, I need the line segments and points, although the points may be the intersection of more than three planes. Just the edges and vertices from the thing you rendered there. I also need to ensure that I know which line segments and which planes are associated with each vertex
$endgroup$
– Jeff Tucker
Mar 28 '14 at 21:20
$begingroup$
Mathematica statement that brings up 27 points in a list: NSolve[(x - 1) (x - 3) (x - 5) == 1/100 && (y - 4) (y - 7) (y - 10) == 1/100 && (z - 1) (z - 4) (z - 7) == 1/100, {x, y, z}] ---- How big would the table be,? Can it be computed once and stored?
$endgroup$
– Alan
Mar 28 '14 at 21:32
$begingroup$
Yes this is a pre-computation step so I can store it easily. The table could potentially be massive also, and the spacing between the planes is only guaranteed to be the same within a single set; different sets could be spaced completely differently. I'm really not seeing much besides a divide-and-conquer approach that involves computing intersections of small numbers of planes and then merging the results. I could use many systems of linear equations and solve them all too, but it seems like that would be just as inefficient. I'm hoping there's some sort of clever shortcut solution
$endgroup$
– Jeff Tucker
Mar 28 '14 at 22:55
add a comment |
$begingroup$
Something like: $ (x-1)(x-3)(x-5) = 1/100 $ , $ (y-4)(y-7)(y-10) = 1/100 $, $ (z-1)(z-4)(z-7) = 1/100 $ ?
answered Mar 28 '14 at 20:07
AlanAlan
1,924815
$endgroup$
Something like: $ (x-1)(x-3)(x-5) = 1/100 $ , $ (y-4)(y-7)(y-10) = 1/100 $, $ (z-1)(z-4)(z-7) = 1/100 $ ?
answered Mar 28 '14 at 20:07
AlanAlan
1,924815
answered Mar 28 '14 at 20:07
AlanAlan
1,924815
answered Mar 28 '14 at 20:07
AlanAlan
1,924815
answered Mar 28 '14 at 20:07
AlanAlan
1,924815
1,924815
$begingroup$
Oh, you want to compute the intersection to store line segments by pairwise intersection, and points by triple intersection?
$endgroup$
– Alan
Mar 28 '14 at 20:18
$begingroup$
Yes, I need the line segments and points, although the points may be the intersection of more than three planes. Just the edges and vertices from the thing you rendered there. I also need to ensure that I know which line segments and which planes are associated with each vertex
$endgroup$
– Jeff Tucker
Mar 28 '14 at 21:20
$begingroup$
Mathematica statement that brings up 27 points in a list: NSolve[(x - 1) (x - 3) (x - 5) == 1/100 && (y - 4) (y - 7) (y - 10) == 1/100 && (z - 1) (z - 4) (z - 7) == 1/100, {x, y, z}] ---- How big would the table be,? Can it be computed once and stored?
$endgroup$
– Alan
Mar 28 '14 at 21:32
$begingroup$
Yes this is a pre-computation step so I can store it easily. The table could potentially be massive also, and the spacing between the planes is only guaranteed to be the same within a single set; different sets could be spaced completely differently. I'm really not seeing much besides a divide-and-conquer approach that involves computing intersections of small numbers of planes and then merging the results. I could use many systems of linear equations and solve them all too, but it seems like that would be just as inefficient. I'm hoping there's some sort of clever shortcut solution
$endgroup$
– Jeff Tucker
Mar 28 '14 at 22:55
add a comment |
$begingroup$
Oh, you want to compute the intersection to store line segments by pairwise intersection, and points by triple intersection?
$endgroup$
– Alan
Mar 28 '14 at 20:18
$begingroup$
Yes, I need the line segments and points, although the points may be the intersection of more than three planes. Just the edges and vertices from the thing you rendered there. I also need to ensure that I know which line segments and which planes are associated with each vertex
$endgroup$
– Jeff Tucker
Mar 28 '14 at 21:20
$begingroup$
Mathematica statement that brings up 27 points in a list: NSolve[(x - 1) (x - 3) (x - 5) == 1/100 && (y - 4) (y - 7) (y - 10) == 1/100 && (z - 1) (z - 4) (z - 7) == 1/100, {x, y, z}] ---- How big would the table be,? Can it be computed once and stored?
$endgroup$
– Alan
Mar 28 '14 at 21:32
$begingroup$
Yes this is a pre-computation step so I can store it easily. The table could potentially be massive also, and the spacing between the planes is only guaranteed to be the same within a single set; different sets could be spaced completely differently. I'm really not seeing much besides a divide-and-conquer approach that involves computing intersections of small numbers of planes and then merging the results. I could use many systems of linear equations and solve them all too, but it seems like that would be just as inefficient. I'm hoping there's some sort of clever shortcut solution
$endgroup$
– Jeff Tucker
Mar 28 '14 at 22:55
$begingroup$
Oh, you want to compute the intersection to store line segments by pairwise intersection, and points by triple intersection?
$endgroup$
– Alan
Mar 28 '14 at 20:18
$begingroup$
Oh, you want to compute the intersection to store line segments by pairwise intersection, and points by triple intersection?
$endgroup$
– Alan
Mar 28 '14 at 20:18
$begingroup$
Yes, I need the line segments and points, although the points may be the intersection of more than three planes. Just the edges and vertices from the thing you rendered there. I also need to ensure that I know which line segments and which planes are associated with each vertex
$endgroup$
– Jeff Tucker
Mar 28 '14 at 21:20
$begingroup$
Yes, I need the line segments and points, although the points may be the intersection of more than three planes. Just the edges and vertices from the thing you rendered there. I also need to ensure that I know which line segments and which planes are associated with each vertex
$endgroup$
– Jeff Tucker
Mar 28 '14 at 21:20
$begingroup$
Mathematica statement that brings up 27 points in a list: NSolve[(x - 1) (x - 3) (x - 5) == 1/100 && (y - 4) (y - 7) (y - 10) == 1/100 && (z - 1) (z - 4) (z - 7) == 1/100, {x, y, z}] ---- How big would the table be,? Can it be computed once and stored?
$endgroup$
– Alan
Mar 28 '14 at 21:32
$begingroup$
Mathematica statement that brings up 27 points in a list: NSolve[(x - 1) (x - 3) (x - 5) == 1/100 && (y - 4) (y - 7) (y - 10) == 1/100 && (z - 1) (z - 4) (z - 7) == 1/100, {x, y, z}] ---- How big would the table be,? Can it be computed once and stored?
$endgroup$
– Alan
Mar 28 '14 at 21:32
$begingroup$
Yes this is a pre-computation step so I can store it easily. The table could potentially be massive also, and the spacing between the planes is only guaranteed to be the same within a single set; different sets could be spaced completely differently. I'm really not seeing much besides a divide-and-conquer approach that involves computing intersections of small numbers of planes and then merging the results. I could use many systems of linear equations and solve them all too, but it seems like that would be just as inefficient. I'm hoping there's some sort of clever shortcut solution
$endgroup$
– Jeff Tucker
Mar 28 '14 at 22:55
$begingroup$
Yes this is a pre-computation step so I can store it easily. The table could potentially be massive also, and the spacing between the planes is only guaranteed to be the same within a single set; different sets could be spaced completely differently. I'm really not seeing much besides a divide-and-conquer approach that involves computing intersections of small numbers of planes and then merging the results. I could use many systems of linear equations and solve them all too, but it seems like that would be just as inefficient. I'm hoping there's some sort of clever shortcut solution
$endgroup$
– Jeff Tucker
Mar 28 '14 at 22:55
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f730597%2fcomputing-the-intersections-of-arbitrary-number-of-planes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
