A lightweight geometry library


A couple of months back, we released a beta version of the question type Image Upload. It allows authors and students to upload an image and students to add annotations to mark their responses. For maximum flexibility, we needed a tool that authors can use to create various geometrical shapes to mark the response areas, i.e. the areas where students are expected to add their responses. For example, a question could be “On the map of Australia, please mark NSW”, and the author will need to be able to mark around the NSW border.

Image 1:NSWSelected

If a student adds an annotation within the response area, the answer will be marked as correct (see image 2 for a correct answer).

Image 2:CorrectAnswer

From a technical perspective, the drawing of the response area is implemented via the jsgl vector graphics library (www.jsgl.org). The image is added as background to a jsgl panel, and the polyline and polygon are rendered through jsgl’s polyline and polygon interfaces.

In order to validate a student’s response, we needed an algorithm to determine if the response lies within the specified response area, i.e. an algorithm to solve the ‘point in polygon’ problem. After researching a couple of freely available JavaScript geometry libraries, which offer implementations for the ‘point in polygon’ problem, we decided to implement the required algorithms ourselves. This is because we wanted to have a very lightweight library and also because some of the available implementations do not handle specific edge cases very well.

There are two main algorithms we needed to implement in our geometry library: 

Line-Line intersection

A line segment in our Geometry Library is given by a starting point P1 and an end point P2. Both points consist of an x and y coordinate. The standard line equation in variables x and y

Ax + By = C

can be derived from these points by setting:

A = P2.y - P1.y
B = P1.x – P2.x
C = A * P1.x + B * P1.y

If two line equations are given in the form

(1) A1x + B1y = C1
(2) A2x + B2y = C2

we can find their point of intersection by solving for the two unknowns x and y and then checking if the resulting point actually lies on both line segments. Solving for x and y can be done by multiplying equation (1) with B2 and equation (2) with B1:

(3) A1B2x + B1B2y = B2C1
(4) A2B1x + B1B2y = B1C2

and then subtracting equation (4) from (3):

A1B2x - A2B1x = x * (A1B2 - A2B1) = B2C1 - B1C2

If the value of (A1B2 – A2B1) is equal to 0, it means that the two lines are parallel and the algorithm needs to check if the line segments overlap anywhere. Otherwise, the value for x can be calculated by dividing both sides of the equation by (A1B2 – A2B1). In a similar manner, the value for y can be derived.

In JavaScript the implementation of the algorithm is as follows:  

/**
* This function determines if two line segments (specified by their start
* and end points) intersect
* The algorithm simply solves the equation system for the two line equations:
* delta1_y * x + delta1_x * y = constant1
* delta2_y * x + delta2_x * y = constant2
* where delta1_y = a2.y - a1.y, delta1_x = a1.x - a2x, constant1 = delta1_y * a1.x
* + delta1_x * a1.y
* (similar for the second line)
*
* For more information on the algorithm research Line-Line intersection algorithms
*
* @param a1 start point of line 1, given by an object with an x and y float
* @param a2 end point of line 1, given by an object with an x and y float
* @param b1 start point of line 2, given by an object with an x and y float
* @param b2 end point of line 2, given by an object with an x and y float
* @returns true if the lines intersect or if they have the same slope and
* some points in common
* false otherwise
*/
intersectLineLine: function(a1, a2, b1, b2) {
  // allow for a certain tolerance as float operations
  // are not exact
  var delta1_y = a2.y - a1.y;
  var delta1_x = a1.x - a2.x;
  var constant1 = (delta1_y * a1.x) + (delta1_x * a1.y);
  var delta2_y = b2.y - b1.y;
  var delta2_x = b1.x - b2.x;
  var constant2 = (delta2_y * b1.x) + (delta2_x * b1.y);
  var determinant = (delta1_y * delta2_x) - (delta1_x * delta2_y);
  var intersect_x;
  var intersect_y;
  var max_x_a = Math.max(a1.x, a2.x);
  var min_x_a = Math.min(a1.x, a2.x);
  var max_y_a = Math.max(a1.y, a2.y);
  var min_y_a = Math.min(a1.y, a2.y);
  var max_x_b = Math.max(b1.x, b2.x);
  var min_x_b = Math.min(b1.x, b2.x);
  var max_y_b = Math.max(b1.y, b2.y);
  var min_y_b = Math.min(b1.y, b2.y);

  if (Math.abs(determinant) < this.tolerance) {
    // Lines are parallel. Do they have a segment in common?
    var sameLine = false;
    if (delta1_x !== 0 && delta2_x !== 0) {
      var ya_atZero = constant1 / delta1_x;
      var yb_atZero = constant2 / delta2_x;
      if (Math.abs(ya_atZero - yb_atZero) < this.tolerance) {
        sameLine = true;
      }
    } else {
      var xa_atZero = constant1 / delta1_y;
      var xb_atZero = constant2 / delta2_y;
      if (Math.abs(xa_atZero - xb_atZero) < this.tolerance) {
        sameLine = true;
      }
    }

    if (sameLine) {
      // segments lie on the same line. Do they have an overlap on the x axis
      if ((Math.abs(max_x_b - min_x_a) < this.tolerance || max_x_b > min_x_a) &&
        (Math.abs(max_y_b - min_y_a) < this.tolerance || max_y_b > min_y_a)) {
        return true;
      }
    }
    return false;
  } else {
    intersect_x = (delta2_x * constant1 - delta1_x * constant2) / determinant;
    intersect_y = (delta1_y * constant2 - delta2_y * constant1) / determinant;

    // Check if the point lies on both lines, allowing for tolerance
    if ((Math.abs(intersect_x - min_x_a) < this.tolerance || intersect_x > min_x_a) &&
      (Math.abs(intersect_x - max_x_a) < this.tolerance || intersect_x < max_x_a) &&
      (Math.abs(intersect_y - min_y_a) < this.tolerance || intersect_y > min_y_a) &&
      (Math.abs(intersect_y - max_y_a) < this.tolerance || intersect_y < max_y_a) &&
      (Math.abs(intersect_x - min_x_b) < this.tolerance || intersect_x > min_x_b) &&
      (Math.abs(intersect_x - max_x_b) < this.tolerance || intersect_x < max_x_b) &&
      (Math.abs(intersect_y - min_y_b) < this.tolerance || intersect_y > min_y_b) &&
      (Math.abs(intersect_y - max_y_b) < this.tolerance || intersect_y < max_y_b)) {
        return true;
    }
    return false;
  }
}

 

Point in Polygon

The algorithm to determine if a point is inside of a polygon is based on the observation that if a point moves along a ray from the probe point to infinity, and if it crosses the boundary of a polygon (possibly several times), then it alternately goes from the outside to the inside, then from the inside to the outside, etc. (This observation may be mathematically proved using the Jordan curve theorem.) So we can conclude that the probe point is inside the polygon, if the ray to infinity intersects an odd number of polygon edges (see image 3 for illustration), and outside the polygon, if it intersects an even number of polygon edges (see image 4 for illustration).

Image 3: if a point is inside the polygon, the ray to infinity intersects an odd number of edges (3 in this case)PointInsidePolygon

Image 4: if a point is outside the polygon, the ray to infinity intersects an even number of edges (4 in this case)PointOutsidePolygon

There are a couple of edge cases that have to be considered to make the algorithm robust. The first edge case is that the probe point lies on one of the polygon’s edges. This can be tested by applying the ‘point on line’ algorithm to each of the polygon’s edges.

The second edge case is that the ray to infinity intersects the polygon exactly in one or more of its vertices.

Image 5: edge case 2, ray intersecting two verticesRayOnVertex

In order to handle this edge case, two scenarios have to be differentiated. The first scenario involves the edges of the intersected vertex pointing in the same direction (as seen from the ray to infinity). In this case, the two vertices do not need to be counted – if the ray to infinity was outside the polygon before hitting the vertex, it will be outside afterwards. If it was inside the polygon before hitting the vertex, it will still be inside after hitting the vertex. In the second scenario, the edges of the intersected vertex point in different directions and the ray will move from the inside to the outside, or from the outside to the inside of the polygon. This is seen in image 5 in the second intersection. In this case, we have to add 1 to the intersection count.

The last edge case is that the ray to infinity overlaps one or more edges of the polygon:

Image 6: Ray overlapping with several of the polygon’s edgesRayOverlap

The overlapping edges should not be considered at all. Instead, one can move the point on the ray forward to the next edge which is not parallel to the ray and apply the logic for edge case two explained above. For example in Image 6, the first intersection should not be counted, because the edge before the overlap points up and the edge after the overlap points up as well. In the second intersection however, the edges point up and then down, so the intersection count needs to be incremented.

If these edge cases are taken into consideration, the point-in-polygon algorithm can be easily implemented based on the line-line-intersection algorithm. In our implementation, the code looks like this:  

/*
* Checks if a point is on a line
* @param point object with an x and y attributes
* @param a1 start point of the line
* @param a2 end point of the line
* @returns truf if the point is on the line, false otherwise
*/
pointOnLine: function (point, a1, a2) {
  var max_x_a = Math.max(a1.x, a2.x);
  var min_x_a = Math.min(a1.x, a2.x);
  var max_y_a = Math.max(a1.y, a2.y);
  var min_y_a = Math.min(a1.y, a2.y);

  if (point.x < min_x_a ||
    point.x > max_x_a ||
    point.y < min_y_a ||
    point.y > max_y_a) {
      return false;
  }

  var delta_y = a2.y - a1.y;
  var delta_x = a1.x - a2.x;
  var constant1 = (delta_y * a1.x) + (delta_x * a1.y);
  var constant2 = (delta_y * point.x) + (delta_x * point.y);
  if (Math.abs(constant2 - constant1) < this.tolerance) {
    return true;
  }
  return false;
},

/**
* Checks if a point is within a given polygon
* The idea is that a point is within a polygon if and only if a horizontal line
* from the point towards positive infinity intersects an odd number of polygon edges
*
* We need to be careful if we hit a vertex. Then the following needs to be done:
* Suppose we draw a horizontal line going through the point and follow
* that line to positive infinity. If we hit a vertex and both edges of the
* vertex lie to our right or our left, then both edges can be counted.
* If one edge lies to the right and one lies to the left of the point,
* only one (let's say the right one) should be counted
* Last complication is, if one of the edges of the vertex is also horizontal.
* In that case we need to go forward to the next point where the edge is not horizontal
*
* @param point object with x and y coordinate
* @param polygon array of points defining the polygon
* @returns true if point is in polygon, false otherwise
*/
pointInPolygon: function(point, polygon) {
  var maxX = Number.MIN_VALUE;
  var maxY = Number.MIN_VALUE;
  var minX = Number.MAX_VALUE;
  var minY = Number.MAX_VALUE;
  var numberOfPoints = polygon.length;
  var i = 0;
  var currentPoint;
  var pointAfter;
  var pointBefore;
  var counter = 0;
  var countDown;

  // Sanity check that point's x and y coordinates are
  // within the range of the polygon and that the point
  // is not a vertex or lies on an edge
  for (i; i < numberOfPoints; i++) {
    currentPoint = polygon[i];
    if (currentPoint.x == point.x && currentPoint.y == point.y) {
      return true;
    }
    pointAfter = polygon[(i + 1) % numberOfPoints];
    if (this.pointOnLine(point, currentPoint, pointAfter)) {
      return true;
    }
    maxX = Math.max(maxX, currentPoint.x);
    maxY = Math.max(maxY, currentPoint.y);
    minX = Math.min(minX, currentPoint.x);
    minY = Math.min(minY, currentPoint.y);
  }
  if (point.x < minX || point.x > maxX || point.y < minY || point.y > maxY) {
    return false;
  }

  // Now the actual algorithm
  for (i = 0; i < numberOfPoints; i++) {
    currentPoint = polygon[i];
    pointAfter = polygon[(i + 1) % numberOfPoints];
    if (this.intersectLineLine(point, {x: maxX + 1, y: point.y},
        currentPoint,
        pointAfter)) {

      // Let's check if the current vertex is intersected
      if (Math.abs(point.y - currentPoint.y) < this.tolerance) {

        // Check if this edge is horizontal
        if (Math.abs(point.y - pointAfter.y) < this.tolerance) {
          continue;
        }

        // Do the current edge and the last non-horizontal edge
        // point in in the same direction?
        countDown = 1;
        pointBefore = polygon[(i - countDown) % numberOfPoints];
        while (Math.abs(pointBefore.y - currentPoint.y) < this.tolerance) {
          ++countDown;
          var index = (i - countDown) % numberOfPoints;
          if (index < 0) {
            index = index + numberOfPoints;
          }
          pointBefore = polygon[index];
        }
        if ((pointBefore.y > currentPoint.y && pointAfter.y > currentPoint.y) ||
            (pointBefore.y < currentPoint.y && pointAfter.y < currentPoint.y)) {
          counter = counter + 2;
          continue;
        }
        if (pointAfter.y < currentPoint.y) {
          counter++;
          continue;
        }
      }

      // If the vertex after is intersected, it will be dealt with in
      // the next iteration
      if (point.y == pointAfter.y) {
        continue;
      }
      counter ++;
    }
  }
  return (counter % 2 == 1);
}

If you find any errors in our implementation, please point them out to us. Otherwise, we hope that the description of our implementation was interesting and possibly useful for you.


This post was posted in , , by on