Bouncing off the walls

A project log for Cardware

An educational system designed to bring AI and complex robotics into the home and school on a budget.

Morning.StarMorning.Star 11/23/2017 at 16:290 Comments

Mapping is the next big push, mathematically speaking. Luckily I have a head-start on that, I had begun working on it with the original AIME, and have some scrappy code snippets I found randomly on the 'net. I dont know who authored this piece of logic, but they deserve a medal.

bool pinside(poly2d poly, double x, double y) {

  int   i, j=poly.nodes-1;
  bool  oddNodes=false;

  for (i=0; i<poly.nodes; i++) {
    if ((poly.coord[i].y< y && poly.coord[j].y>=y
    ||   poly.coord[j].y< y && poly.coord[i].y>=y)
    &&  (poly.coord[i].x<=x || poly.coord[j].x<=x)) {
      oddNodes^=(poly.coord[i].x+(y-poly.coord[i].y)/(poly.coord[j].y-poly.coord[i].y)*(poly.coord[j].x-poly.coord[i].x)<x); }
    j=i; }

  return oddNodes; }

What it does, is establish whether a point is inside or outside of a complex polygon. Simple polygons are easy, a rectangle particularly so because you can just test it as a matrix. Any cell with a negative index or greater than the width or height is obviously outside. Regular polygons are harder, but still fairly simple - checking the angles of the sides against the line between each corner and the test point to see if they are all larger than that angle is one way of doing it.

But what about horrible shapes like these (and they will be really easy to create by exploring...)

That second one is particularly nasty. Inkscape has a special routine to handle it in one of several ways depending on how you want it filled. This is default; areas that cross areas already used by the shape are considered outside, unless they are crossed again by a subsequent area. This is how the code snippet interprets a polygon like that, and its useful for making areas from paths for example.

It works by counting the number of boundaries crossed by exiting the polygon from the test point. Obviously a simple regular polygon like a hexagon would return 1 boundary crossed, an odd number of boundaries crossed will always indicate the test point being inside the shape, and an even number of boundaries crossed will indicate outside (providing the crossed-areas rule is observed.)

This is of particular use for sequential-turn mapping of an area, because it identifies the areas enclosed by the path that need exploring, as turns are generated by obstacles that might not be boundaries.