Databases
StackOverflow2013
Postsdbo
POFind the better intersection of two moving objects
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFind the better intersection of two moving objects
    primarykey
    data
    text
    <p>I would like to optimize dramaticaly one of my algorithm, i will try to explain it the best way that i can.</p> <h2>The subject</h2> <p>We are in a 2D euclidian system at the time <em>t = 0</em>. In this system there is two object : <strong>O1</strong> and <strong>O2</strong>.</p> <p><strong>O1</strong> and <strong>O2</strong> are respectively situated at the point <strong>PA</strong> and <strong>PC</strong>.</p> <p><strong>O1</strong> moves at a <strong>constant and known</strong> speed in direction of the point <strong>PB</strong>. The object will stop when it reach PB.</p> <p><strong>O2</strong> can move at a <strong>constant and known</strong> speed <em>different or not</em> of O1's in any direction. At the time 0, O2 has <strong>no direction</strong>, we will need to find one for it.</p> <p>The knowns parameters:</p> <ul> <li>O1 : Position, direction, speed</li> <li>O2 : Position, speed</li> </ul> <p>Here is a little diagram of the system.</p> <p><img src="https://i.stack.imgur.com/hbe4v.png" alt="Diagram of the system"></p> <p>We would like to find the point <strong>PI</strong> and the time <strong>ti</strong> for which : <code>Position of O1 at the time ti = Position of O2 at the time ti = PI</code>. Then we will make the object O2 move to the point PI to get the <strong>O2 direction</strong>.</p> <p>When the direction of O2 (the point PI) is chosen and both objects O1 and O2 are on the move, <strong>the objects will never stop or wait</strong> for each other.</p> <p>In this case, the result would be something like this (PI is noted D on this picture). <img src="https://i.stack.imgur.com/l86ev.png" alt="Best intersection"></p> <h2>The algorithm</h2> <p>You can find the working algorithm written in JS at this <a href="http://jsfiddle.net/mamadrood/86n9f/" rel="noreferrer">jsfiddle</a>, it is also a great way to understand the problem.</p> <p>At this time i use a simple algorithm who works, but can take a lot of operations, i will get the best intersection time, and get the intersection position afterwards.</p> <p>To get this time, i will check the position of O1 at a moment, and check if O2 could possibly go to this position at this time. If O2 could not reach the object in time, we will increase the time by 150%, however if O2 could cross the O1-B line at the time, we will decrease the time by 50%.</p> <p>Eventually, after many approximations, we will find the perfect time where both objects could meet.</p> <p><em>PseudoCode</em></p> <pre><code>function getOptimalIntersectionTime time if distance between O1 and O2 at the time `time` &lt; 1 return time else if O2 could not reach the object O1 at the time `time` return getOptimalIntersectionTime time * 1.5 else return getOptimalIntersectionTime time * 0.5 </code></pre> <h2>Why am I concern ?</h2> <p>My algorithm works, but in some case (e.g. the "Reverse Case" in the jsFiddle) it will take a large amount of calculus to find the best point.</p> <p>In this jsFiddle, we are using little values for position (-1000 to 1000) and speed (1-200) but this algorithm is dramaticaly slower with bigger numbers.</p> <p>I know that premature optimization is a bad idea, but I'm at the end of the project (which consists on databases insertions / selection and data analysis, including this algorithm called many many times) and this algorithm take up to 80% of the project system ressources in certain cases so an improvement could really improve the stability and the responsiveness of the system.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USGeorge Bailey
    1. USmamadrood
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFind the better intersection of two moving objects
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFind the better intersection of two moving objects
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFind the better intersection of two moving objects
      1. This table or related slice is empty.
      1. VTUpMod
    1. COwhat are the constraints? Without constraints it's _always_ possible to pick some velocity vector for O2 that'll meet up with O1 at PI.
      singulars
      1. POFind the better intersection of two moving objects
      1. USAlnitak
    2. COYour diagrams are nice. Thanks. I have a question, though: is the speed of O2 constrained? Because, if it isn't, then O2 can just shoot off really fast and hit O1 before O1 even has a chance to move. But I suspect that I have slightly misunderstood your question. For my benefit, would you clarify?
      singulars
      1. POFind the better intersection of two moving objects
      1. USthb
    3. COWhat do you mean by _the nearest point PI_? nearest to PA, PB, or PC?
      singulars
      1. POFind the better intersection of two moving objects
      1. USIslam Hassan
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload