Question 314190 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – A JS algorithm to find point's location by checking if it is within fixed-size circles

So, I have a point in an unknown location, which I need to programmaticaly find. The only way we can try to find it’s location is is by calling a special isThePointWithin500MetersOfLocation(x, y) function, which will return true if the point is within 500 meters of the passed location. I need to find out where the point is, or at least as close to it as possible. What algorithms could be used for this?

The isThePointWithin500MetersOfLocation function takes ~30 seconds to execute, so the less calls to it there are – the better.

Tags:

2

Answers


  1. 0

    Here is testing for a point within a radius of another point.

    testForPointInCircle = function(cx,cy, radius, tx,ty) {
        var dx = tx - cx;
        var dy = ty - cy;
        var distance = dx * dx + dy * dy;
        return distance < (radius * radius);
}
    
var p1 = {x:0, y:500};
var p2 = {x:25, y:450};

window.console.log( testForPointInCircle(p1.x,p1.y, 70, p2.x,p2.y) + "   " + 
testForPointInCircle(p1.x,p1.y, 10, p2.x,p2.y) + "  " + p1.y );

var p3 = {x:10, y:1000};

//If you don't know the test point, you could call the function in a loop with a guess until you get true.

while( !testForPointInCircle(p3.x,p3.y, 25, p1.x,p1.y) ) {
    p1.y += 5;
}
window.console.log(p1.y);
    Login or Signup to reply.
  2. 0

    Let’s skip over how you’re going to find the first result for isThePointWithin500MetersOfLocation, because this sounds a little too much of a toy problem to fully solve, but once you have your first, start binary searching. Or since we’re dealing with circles, and initial trinary searching: any circle of radius r can be fully covered by three circles with the same radius, with their centers on the original circle, and their centers each 120 degrees apart.

    So let’s do that:

    customElements.whenDefined(`graphics-element`).then(() => {

const graphics = document.getElementById(`illustration`);
  let code = circleGraphics.toString();
  code = code.substring(code.indexOf(`{`)+1, code.lastIndexOf(`}`));
  graphics.loadSource(code);
});

function circleGraphics() {
  let p, circles = [], current, a=0, s=TAU/3, nextButton, matches = [];
  let bisecting = false;

  function setup() {
    setSize(150, 150);
    let angle = random(0,TAU);
    let radius = random(0, 40);
    p = new Point(50, 50);
    current = new Circle(75, 75, 50)
    circles.push(current);
    matches.push(current);
    nextButton = addButton(`next`, tryNext);
  }

  function draw() {
    clear();
    setColor(`black`);
    point(p.x, p.y);
  
    if (bisecting) {
      matches.forEach(c => {
        setFill(c.fill ?? `#F001`);
        circle(c.x, c.y, c.r);
      });
      showBisection();
    } else {
      circles.forEach(c => {
        setFill(c.fill ?? `#F001`);
        circle(c.x, c.y, c.r);
      });
    }
    
    if (matches.length === 2 && !bisecting) {
      nextButton.remove();
      nextButton = addButton(`bisect this`, () => {
        nextButton.remove();
        bisecting = true;
        redraw();
      });
    }
  }
  
  function showBisection() {
    // At this point we have reduced the area our
    // point can be in. How can we best bisect that?
    // By placing more circles, of course.
    //
    // And because the circles are the same radius,
    // finding the intersections is very easy:
    const [c1,c2] = matches;
    const { r } = c1;
    const a = atan2(c1.y - c2.y, c1.x - c2.x);
    setColor(`black`);
    const p1 = new Point(
      c1.x + r * cos(a - s),
      c1.y + r * sin(a - s),
    );
    const p2 = new Point(
      c1.x + r * cos(a + s),
      c1.y + r * sin(a + s),
    );
    let dx = p2.x - p1.x;
    let dy = p2.y - p1.y;
    const mag = (dx**2 + dy**2)**0.5;
    dx /= mag;
    dy /= mag;
    line(p1.x - 100 * dx, p1.y - 100 * dy, p2.x + 100 * dx, p2.y + 100 * dy); 
  }  
  
  function tryNext() {
    const { x, y, r } = current;
    // Place a circle on the original circle perimeter, and
    // see if the point is in that new circle. If so, we've
    // narrowed the area it can be in.
    const c = new Circle(x + r * cos(a), y + r * sin(a), r);
    circles.push(c);
    const d = dist(c.x, c.y, p.x, p.y);
    const pointIsInCircle = d < c.r;
    if (pointIsInCircle) {
      c.fill = `#0F01`;
      matches.push(c);
      a = 0;
    } else {
      // no good, try next circle       
      a += s;
    }
    redraw();
  } 
}
    <script type="module" src="https://pomax.github.io/custom-graphics-element/dist/graphics-element.js"></script>
<link ref="stylesheet" href="https://pomax.github.io/custom-graphics-element/dist/graphics-element.css">
<graphics-element id="illustration"></graphics-element>

    This is, of course, only the first iteration: once we have a two-circle overlap, we now get to figure out where to place two new circles that we can use to bisect the area of overlap. The trigonometry required to find the two centers of those circles, I will leave up to you.

    Evaluating each of these two circles will either result in "point is in 1 of them", which will yield a "triangle-ish" shape, or "point is in both of them", in which case we have the exact same situation we were just in, just with a much smaller shape.

    We can trisect and bisect those shapes, respectively, and thus we can get closer and closer and closer to the "true" location of our point. The implementation of which is an exercise for the reader poster =)

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search