Algorithm for on road key points detection Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) The Ask Question Wizard is Live! Data science time! April 2019 and salary with experience Should we burninate the [wrap] tag?What is the best algorithm for an overridden System.Object.GetHashCode?What algorithms compute directions from point A to point B on a map?Easy interview question got harder: given numbers 1..100, find the missing number(s)Graph auto-layout algorithmUkkonen's suffix tree algorithm in plain EnglishImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionHow to find time complexity of an algorithmGiven two point sets A and B, how do you find the point in A farthest away from B?What is the optimal algorithm for the game 2048?Considering Start point and end point on edge, not Node of graph in Path finding algorithm for Road Network Graph
What is the musical term for a note that continously plays through a melody?
Doubts about chords
Is the address of a local variable a constexpr?
How to motivate offshore teams and trust them to deliver?
What is the longest distance a 13th-level monk can jump while attacking on the same turn?
Should I discuss the type of campaign with my players?
How can I make names more distinctive without making them longer?
Is there a service that would inform me whenever a new direct route is scheduled from a given airport?
Why does Python start at index -1 when indexing a list from the end?
How does cp -a work
Bonus calculation: Am I making a mountain out of a molehill?
What are 'alternative tunings' of a guitar and why would you use them? Doesn't it make it more difficult to play?
G-Code for resetting to 100% speed
What is a Meta algorithm?
Did Xerox really develop the first LAN?
Is there a documented rationale why the House Ways and Means chairman can demand tax info?
What does the "x" in "x86" represent?
Letter Boxed validator
Why is black pepper both grey and black?
Are my PIs rude or am I just being too sensitive?
Can Pao de Queijo, and similar foods, be kosher for Passover?
How do I mention the quality of my school without bragging
What causes the vertical darker bands in my photo?
What would be the ideal power source for a cybernetic eye?
Algorithm for on road key points detection
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
The Ask Question Wizard is Live!
Data science time! April 2019 and salary with experience
Should we burninate the [wrap] tag?What is the best algorithm for an overridden System.Object.GetHashCode?What algorithms compute directions from point A to point B on a map?Easy interview question got harder: given numbers 1..100, find the missing number(s)Graph auto-layout algorithmUkkonen's suffix tree algorithm in plain EnglishImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionHow to find time complexity of an algorithmGiven two point sets A and B, how do you find the point in A farthest away from B?What is the optimal algorithm for the game 2048?Considering Start point and end point on edge, not Node of graph in Path finding algorithm for Road Network Graph
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
I have a problem with algorithm for detection points which leg on the road between source and destination points.
There are a few assumptions for this:
- Starting from p0 (starting point) I want to move to pk (destination point)
- I have constraints for time and distance
- All of key points (p1, p2, p3, ..., pn) have weight (profit) corresponding to them (w1, w2, w3, ..., wn)
The question is how to detect which points are the most profitable? When I choose some points I would like to ask google navigation API if constraints are fulfilled but requests are expensive so it would be better for me not to do many of these.
Do you know any algorithm which is designed for solving such a problem?
---EDIT 1---
If I well understood you I should modify my problem to graph.
Still I don't know algorithm which allows me to solve this problem.
This is two-way graph (excluding connection to point p0 and pk). I would like to maximize profit and keep distance restrictions. Do you know any formal algorithm which could help me with it?
Example paths could be:
p0->3->2->1->pk
p0->1->pk
algorithm
asked Mar 8 at 16:16
konradokonrado
184
add a comment |
I have a problem with algorithm for detection points which leg on the road between source and destination points.
There are a few assumptions for this:
- Starting from p0 (starting point) I want to move to pk (destination point)
- I have constraints for time and distance
- All of key points (p1, p2, p3, ..., pn) have weight (profit) corresponding to them (w1, w2, w3, ..., wn)
The question is how to detect which points are the most profitable? When I choose some points I would like to ask google navigation API if constraints are fulfilled but requests are expensive so it would be better for me not to do many of these.
Do you know any algorithm which is designed for solving such a problem?
---EDIT 1---
If I well understood you I should modify my problem to graph.
Still I don't know algorithm which allows me to solve this problem.
This is two-way graph (excluding connection to point p0 and pk). I would like to maximize profit and keep distance restrictions. Do you know any formal algorithm which could help me with it?
Example paths could be:
p0->3->2->1->pk
p0->1->pk
algorithm
asked Mar 8 at 16:16
konradokonrado
184
Is there any reason why Dijkstra's would not work here?
– Mitchel Paulin
Mar 8 at 16:46
1
If you can approximate time and distance using point coordinates (which should be reasonably cheap), you can calculate a preliminary profit-maximizing path given your constraints. Then, look up the real distances and times for the edges on your path and update. Iterate until you get a path that has the real distances and times.
– Nico Schertler
Mar 8 at 16:52
Dijkstra works for graph. Here is situation where I have real road. I know only distances in straight line between points but not real. To know real distance I have to send request for google but I would like to avoid it to ask for all of roads.
– konrado
Mar 8 at 16:58
@NicoSchertler Do you have any proposals how to approximate real distance between two coordinates? Important thing is that distance between points could be very small (0.5 km)
– konrado
Mar 8 at 17:36
Just direct distance, measured through air.
– Nico Schertler
Mar 8 at 17:40
add a comment |
I have a problem with algorithm for detection points which leg on the road between source and destination points.
There are a few assumptions for this:
- Starting from p0 (starting point) I want to move to pk (destination point)
- I have constraints for time and distance
- All of key points (p1, p2, p3, ..., pn) have weight (profit) corresponding to them (w1, w2, w3, ..., wn)
The question is how to detect which points are the most profitable? When I choose some points I would like to ask google navigation API if constraints are fulfilled but requests are expensive so it would be better for me not to do many of these.
Do you know any algorithm which is designed for solving such a problem?
---EDIT 1---
If I well understood you I should modify my problem to graph.
Still I don't know algorithm which allows me to solve this problem.
This is two-way graph (excluding connection to point p0 and pk). I would like to maximize profit and keep distance restrictions. Do you know any formal algorithm which could help me with it?
Example paths could be:
p0->3->2->1->pk
p0->1->pk
algorithm
asked Mar 8 at 16:16
konradokonrado
184
I have a problem with algorithm for detection points which leg on the road between source and destination points.
There are a few assumptions for this:
- Starting from p0 (starting point) I want to move to pk (destination point)
- I have constraints for time and distance
- All of key points (p1, p2, p3, ..., pn) have weight (profit) corresponding to them (w1, w2, w3, ..., wn)
The question is how to detect which points are the most profitable? When I choose some points I would like to ask google navigation API if constraints are fulfilled but requests are expensive so it would be better for me not to do many of these.
Do you know any algorithm which is designed for solving such a problem?
---EDIT 1---
If I well understood you I should modify my problem to graph.
Still I don't know algorithm which allows me to solve this problem.
This is two-way graph (excluding connection to point p0 and pk). I would like to maximize profit and keep distance restrictions. Do you know any formal algorithm which could help me with it?
Example paths could be:
p0->3->2->1->pk
p0->1->pk
algorithm
algorithm
asked Mar 8 at 16:16
konradokonrado
184
asked Mar 8 at 16:16
konradokonrado
184
edited Mar 9 at 8:46
konrado
asked Mar 8 at 16:16
konradokonrado
184
asked Mar 8 at 16:16
konradokonrado
184
asked Mar 8 at 16:16
konradokonrado
184
184
Is there any reason why Dijkstra's would not work here?
– Mitchel Paulin
Mar 8 at 16:46
1
If you can approximate time and distance using point coordinates (which should be reasonably cheap), you can calculate a preliminary profit-maximizing path given your constraints. Then, look up the real distances and times for the edges on your path and update. Iterate until you get a path that has the real distances and times.
– Nico Schertler
Mar 8 at 16:52
Dijkstra works for graph. Here is situation where I have real road. I know only distances in straight line between points but not real. To know real distance I have to send request for google but I would like to avoid it to ask for all of roads.
– konrado
Mar 8 at 16:58
@NicoSchertler Do you have any proposals how to approximate real distance between two coordinates? Important thing is that distance between points could be very small (0.5 km)
– konrado
Mar 8 at 17:36
Just direct distance, measured through air.
– Nico Schertler
Mar 8 at 17:40
add a comment |
Is there any reason why Dijkstra's would not work here?
– Mitchel Paulin
Mar 8 at 16:46
1
If you can approximate time and distance using point coordinates (which should be reasonably cheap), you can calculate a preliminary profit-maximizing path given your constraints. Then, look up the real distances and times for the edges on your path and update. Iterate until you get a path that has the real distances and times.
– Nico Schertler
Mar 8 at 16:52
Dijkstra works for graph. Here is situation where I have real road. I know only distances in straight line between points but not real. To know real distance I have to send request for google but I would like to avoid it to ask for all of roads.
– konrado
Mar 8 at 16:58
@NicoSchertler Do you have any proposals how to approximate real distance between two coordinates? Important thing is that distance between points could be very small (0.5 km)
– konrado
Mar 8 at 17:36
Just direct distance, measured through air.
– Nico Schertler
Mar 8 at 17:40
Is there any reason why Dijkstra's would not work here?
– Mitchel Paulin
Mar 8 at 16:46
Is there any reason why Dijkstra's would not work here?
– Mitchel Paulin
Mar 8 at 16:46
1
1
If you can approximate time and distance using point coordinates (which should be reasonably cheap), you can calculate a preliminary profit-maximizing path given your constraints. Then, look up the real distances and times for the edges on your path and update. Iterate until you get a path that has the real distances and times.
– Nico Schertler
Mar 8 at 16:52
If you can approximate time and distance using point coordinates (which should be reasonably cheap), you can calculate a preliminary profit-maximizing path given your constraints. Then, look up the real distances and times for the edges on your path and update. Iterate until you get a path that has the real distances and times.
– Nico Schertler
Mar 8 at 16:52
Dijkstra works for graph. Here is situation where I have real road. I know only distances in straight line between points but not real. To know real distance I have to send request for google but I would like to avoid it to ask for all of roads.
– konrado
Mar 8 at 16:58
Dijkstra works for graph. Here is situation where I have real road. I know only distances in straight line between points but not real. To know real distance I have to send request for google but I would like to avoid it to ask for all of roads.
– konrado
Mar 8 at 16:58
@NicoSchertler Do you have any proposals how to approximate real distance between two coordinates? Important thing is that distance between points could be very small (0.5 km)
– konrado
Mar 8 at 17:36
@NicoSchertler Do you have any proposals how to approximate real distance between two coordinates? Important thing is that distance between points could be very small (0.5 km)
– konrado
Mar 8 at 17:36
Just direct distance, measured through air.
– Nico Schertler
Mar 8 at 17:40
Just direct distance, measured through air.
– Nico Schertler
Mar 8 at 17:40
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
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
,
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%2fstackoverflow.com%2fquestions%2f55067046%2falgorithm-for-on-road-key-points-detection%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f55067046%2falgorithm-for-on-road-key-points-detection%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
Is there any reason why Dijkstra's would not work here?
– Mitchel Paulin
Mar 8 at 16:46
1
If you can approximate time and distance using point coordinates (which should be reasonably cheap), you can calculate a preliminary profit-maximizing path given your constraints. Then, look up the real distances and times for the edges on your path and update. Iterate until you get a path that has the real distances and times.
– Nico Schertler
Mar 8 at 16:52
Dijkstra works for graph. Here is situation where I have real road. I know only distances in straight line between points but not real. To know real distance I have to send request for google but I would like to avoid it to ask for all of roads.
– konrado
Mar 8 at 16:58
@NicoSchertler Do you have any proposals how to approximate real distance between two coordinates? Important thing is that distance between points could be very small (0.5 km)
– konrado
Mar 8 at 17:36
Just direct distance, measured through air.
– Nico Schertler
Mar 8 at 17:40