Mapping line segments to $2$-dimensional area
2
$begingroup$
Given a $2$-dimensional space subdivided into $Ntimes N$ tiles, drawing a line from the edge's midpoint to the opposite field how can the $N$ tiles be found covering the majority of the line's path?
A visual aid:
Is there a better way to this than computing the linear equation and iteratively advancing in tiny steps to check which bucket we fall on? If not what is the lower limit step size to choose?
geometry algorithms
edited Jan 16 at 10:01
idriskameni
585318
asked Jan 16 at 9:39
KilianKilian
1134
$endgroup$
add a comment |
2
$begingroup$
Given a $2$-dimensional space subdivided into $Ntimes N$ tiles, drawing a line from the edge's midpoint to the opposite field how can the $N$ tiles be found covering the majority of the line's path?
A visual aid:
Is there a better way to this than computing the linear equation and iteratively advancing in tiny steps to check which bucket we fall on? If not what is the lower limit step size to choose?
geometry algorithms
edited Jan 16 at 10:01
idriskameni
585318
asked Jan 16 at 9:39
KilianKilian
1134
$endgroup$
$begingroup$
Define “majority of the line’s path,” (or in the image, “spends the most area on”).
$endgroup$
– amd
Jan 17 at 0:30
add a comment |
2
2
2
1
$begingroup$
Given a $2$-dimensional space subdivided into $Ntimes N$ tiles, drawing a line from the edge's midpoint to the opposite field how can the $N$ tiles be found covering the majority of the line's path?
A visual aid:
Is there a better way to this than computing the linear equation and iteratively advancing in tiny steps to check which bucket we fall on? If not what is the lower limit step size to choose?
geometry algorithms
edited Jan 16 at 10:01
idriskameni
585318
asked Jan 16 at 9:39
KilianKilian
1134
$endgroup$
Given a $2$-dimensional space subdivided into $Ntimes N$ tiles, drawing a line from the edge's midpoint to the opposite field how can the $N$ tiles be found covering the majority of the line's path?
A visual aid:
Is there a better way to this than computing the linear equation and iteratively advancing in tiny steps to check which bucket we fall on? If not what is the lower limit step size to choose?
geometry algorithms
geometry algorithms
edited Jan 16 at 10:01
idriskameni
585318
asked Jan 16 at 9:39
KilianKilian
1134
edited Jan 16 at 10:01
idriskameni
585318
asked Jan 16 at 9:39
KilianKilian
1134
edited Jan 16 at 10:01
idriskameni
585318
edited Jan 16 at 10:01
idriskameni
585318
edited Jan 16 at 10:01
idriskameni
585318
585318
asked Jan 16 at 9:39
KilianKilian
1134
asked Jan 16 at 9:39
KilianKilian
1134
asked Jan 16 at 9:39
KilianKilian
1134
1134
$begingroup$
Define “majority of the line’s path,” (or in the image, “spends the most area on”).
$endgroup$
– amd
Jan 17 at 0:30
add a comment |
$begingroup$
Define “majority of the line’s path,” (or in the image, “spends the most area on”).
$endgroup$
– amd
Jan 17 at 0:30
$begingroup$
Define “majority of the line’s path,” (or in the image, “spends the most area on”).
$endgroup$
– amd
Jan 17 at 0:30
$begingroup$
Define “majority of the line’s path,” (or in the image, “spends the most area on”).
$endgroup$
– amd
Jan 17 at 0:30
add a comment |
1 Answer
1
active
oldest
votes
1
$begingroup$
You are lucky. I've spent weeks coming out with an algorithm for solving this type of problem. Here is how you should approach it:
- Notice that you have a regular grid in both $x$ and $y$ directions. In your particular drawings you have vertical planes at $x_j=2j+1$, with $jinmathbb Z$, or more exactly in a subset of that, from $j_{min}$ to $j_{max}$. Similarly, your horizontal planes have $y_k=2k+1$.
- Calculate the intersections of the lines with your horizontal and vertical planes. Use $$tan theta=frac yx$$ That means that the intersections with vertical planes occur at $(x_j,x_jtantheta)$, and the intersections with vertical planes are at $(y_kcot theta,y_k)$. Choose only the ones that occur inside (or on the border) of your tiles.
- If $|tantheta|<1$, then your line is mostly horizontal. Then sort your intersections by the $x$ coordinate, and calculate the length along $x$ between your intersections. Choose the largest $N$ of those, and these are where your length is longest. If $|tantheta|>1$, just use the $y$ lengths instead.
- Once you have the $x$ boundaries of any interval, choose the midpoint, calculate the $y$ position (from the tangent formula), then figure out in which $y$ interval it lands. Similarly, just switch $y$ and $x$ if you calculated the $y$ intervals.
answered Feb 4 at 4:51
AndreiAndrei
12k21126
$endgroup$
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
});
}
});
draft saved
draft discarded
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%2f3075528%2fmapping-line-segments-to-2-dimensional-area%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
1
$begingroup$
You are lucky. I've spent weeks coming out with an algorithm for solving this type of problem. Here is how you should approach it:
- Notice that you have a regular grid in both $x$ and $y$ directions. In your particular drawings you have vertical planes at $x_j=2j+1$, with $jinmathbb Z$, or more exactly in a subset of that, from $j_{min}$ to $j_{max}$. Similarly, your horizontal planes have $y_k=2k+1$.
- Calculate the intersections of the lines with your horizontal and vertical planes. Use $$tan theta=frac yx$$ That means that the intersections with vertical planes occur at $(x_j,x_jtantheta)$, and the intersections with vertical planes are at $(y_kcot theta,y_k)$. Choose only the ones that occur inside (or on the border) of your tiles.
- If $|tantheta|<1$, then your line is mostly horizontal. Then sort your intersections by the $x$ coordinate, and calculate the length along $x$ between your intersections. Choose the largest $N$ of those, and these are where your length is longest. If $|tantheta|>1$, just use the $y$ lengths instead.
- Once you have the $x$ boundaries of any interval, choose the midpoint, calculate the $y$ position (from the tangent formula), then figure out in which $y$ interval it lands. Similarly, just switch $y$ and $x$ if you calculated the $y$ intervals.
answered Feb 4 at 4:51
AndreiAndrei
12k21126
$endgroup$
add a comment |
1
$begingroup$
You are lucky. I've spent weeks coming out with an algorithm for solving this type of problem. Here is how you should approach it:
- Notice that you have a regular grid in both $x$ and $y$ directions. In your particular drawings you have vertical planes at $x_j=2j+1$, with $jinmathbb Z$, or more exactly in a subset of that, from $j_{min}$ to $j_{max}$. Similarly, your horizontal planes have $y_k=2k+1$.
- Calculate the intersections of the lines with your horizontal and vertical planes. Use $$tan theta=frac yx$$ That means that the intersections with vertical planes occur at $(x_j,x_jtantheta)$, and the intersections with vertical planes are at $(y_kcot theta,y_k)$. Choose only the ones that occur inside (or on the border) of your tiles.
- If $|tantheta|<1$, then your line is mostly horizontal. Then sort your intersections by the $x$ coordinate, and calculate the length along $x$ between your intersections. Choose the largest $N$ of those, and these are where your length is longest. If $|tantheta|>1$, just use the $y$ lengths instead.
- Once you have the $x$ boundaries of any interval, choose the midpoint, calculate the $y$ position (from the tangent formula), then figure out in which $y$ interval it lands. Similarly, just switch $y$ and $x$ if you calculated the $y$ intervals.
answered Feb 4 at 4:51
AndreiAndrei
12k21126
$endgroup$
add a comment |
1
1
1
$begingroup$
You are lucky. I've spent weeks coming out with an algorithm for solving this type of problem. Here is how you should approach it:
- Notice that you have a regular grid in both $x$ and $y$ directions. In your particular drawings you have vertical planes at $x_j=2j+1$, with $jinmathbb Z$, or more exactly in a subset of that, from $j_{min}$ to $j_{max}$. Similarly, your horizontal planes have $y_k=2k+1$.
- Calculate the intersections of the lines with your horizontal and vertical planes. Use $$tan theta=frac yx$$ That means that the intersections with vertical planes occur at $(x_j,x_jtantheta)$, and the intersections with vertical planes are at $(y_kcot theta,y_k)$. Choose only the ones that occur inside (or on the border) of your tiles.
- If $|tantheta|<1$, then your line is mostly horizontal. Then sort your intersections by the $x$ coordinate, and calculate the length along $x$ between your intersections. Choose the largest $N$ of those, and these are where your length is longest. If $|tantheta|>1$, just use the $y$ lengths instead.
- Once you have the $x$ boundaries of any interval, choose the midpoint, calculate the $y$ position (from the tangent formula), then figure out in which $y$ interval it lands. Similarly, just switch $y$ and $x$ if you calculated the $y$ intervals.
answered Feb 4 at 4:51
AndreiAndrei
12k21126
$endgroup$
You are lucky. I've spent weeks coming out with an algorithm for solving this type of problem. Here is how you should approach it:
- Notice that you have a regular grid in both $x$ and $y$ directions. In your particular drawings you have vertical planes at $x_j=2j+1$, with $jinmathbb Z$, or more exactly in a subset of that, from $j_{min}$ to $j_{max}$. Similarly, your horizontal planes have $y_k=2k+1$.
- Calculate the intersections of the lines with your horizontal and vertical planes. Use $$tan theta=frac yx$$ That means that the intersections with vertical planes occur at $(x_j,x_jtantheta)$, and the intersections with vertical planes are at $(y_kcot theta,y_k)$. Choose only the ones that occur inside (or on the border) of your tiles.
- If $|tantheta|<1$, then your line is mostly horizontal. Then sort your intersections by the $x$ coordinate, and calculate the length along $x$ between your intersections. Choose the largest $N$ of those, and these are where your length is longest. If $|tantheta|>1$, just use the $y$ lengths instead.
- Once you have the $x$ boundaries of any interval, choose the midpoint, calculate the $y$ position (from the tangent formula), then figure out in which $y$ interval it lands. Similarly, just switch $y$ and $x$ if you calculated the $y$ intervals.
answered Feb 4 at 4:51
AndreiAndrei
12k21126
answered Feb 4 at 4:51
AndreiAndrei
12k21126
answered Feb 4 at 4:51
AndreiAndrei
12k21126
answered Feb 4 at 4:51
AndreiAndrei
12k21126
12k21126
add a comment |
add a comment |
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3075528%2fmapping-line-segments-to-2-dimensional-area%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
$begingroup$
Define “majority of the line’s path,” (or in the image, “spends the most area on”).
$endgroup$
– amd
Jan 17 at 0:30