Finding self intersection for a polygon

Question

I am trying to find the self-intersection in a polygon in-order to prevent the user from doing so. The user will only be allowed to draw this polygon on a plane which is made by taking the co-planar points plotted by the user in the 3d space.

My first Idea was to make these points parallel to the X-Z plane and then check intersection between line-segments. I am able to check for intersection in 2d, but rotating these points doesn't preserve the shape nor rotate parallel to XZ axis, which inturn causes problems when testing for intersection

Before rotation:

After rotation

This is how I am rotating.

const angle = pos.angleTo(new THREE.Vector3(0, 1, 0)) // pos here represents the position vector of the circle
const rotationMatrix = new THREE.Matrix4().makeRotationAxis(new THREE.Vector3(1, 0, 0), -angle); // rotate around x Axis
rotationMatrix.makeRotationAxis(new THREE.Vector3(0, 0, 1), -angle) // rotate around z axis
circle.applyMatrix4(rotationMatrix);

Its supposed to rotate points drawn on any plane parallel to XZ axis, which isn't whats happening currently. I am pretty new to threejs and am missing something here.

How can I correctly rotate the vertices such that it becomes parallel to to XZ axes without losing its shape?

Answer 1

I was trying to find the self intersection of the polygon in order to prevent user from creating a polygon with self intersection. So one of the easiest way to solve this was to project it to 2d coordinate system and check if any of the line segments intersect with each other.

To project vectors 3d you can make use of the Vector3.project(camera), this would give you the return the projection in xy coordinates. You can then use the line-segment intersection code to check for intersection.

here's a small snippet

function projectFromCamera(vertices, camera) {
  const projection = vertices.map((p) => p.clone().project(camera));
  return projection.map((p) => new THREE.Vector2(p.x, p.y));
}

/**
 * Checks if the last line segment intersects with any other segment
 *
 * @param {THREE.Vector3 []} vertices
 * @param {THREE.Vector3} point
 * @param {THREE.Plane} plane
 * @returns
 */
export function isPointIntersectingPolygon(vertices, camera) {
  const projection = projectFromCamera(vertices, camera);

  let intersecting = false;
  for (let x = 0; x < projection.length - 3; x++) {
    intersecting = checkLineIntersection(
      projection.at(-2),
      projection.at(-1),
      projection[x],
      projection[x + 1],
    );
    if (intersecting) break;
  }

  return intersecting;
}

/**
 * Checks if the polygon is self intersecting
 *
 * @param {THREE.Vector3} vertices
 * @param {THREE.Camera} camera
 * @returns
 */
export function checkPolygonSelfIntersecting(vertices, camera) {
  const projection = projectFromCamera(vertices, camera);

  let intersecting = isPointIntersectingPolygon(vertices, camera);

  console.log("actual projectin: ", projection, intersecting);

  for (let x = 1; x < projection.length - 2; x++) {
    // checks if the line segment made by first and last points intersects with any other segment
    intersecting = checkLineIntersection(
      projection.at(0),
      projection.at(-1),
      projection[x],
      projection[x + 1],
    );
    console.log("intersecting: ", x, intersecting);

    // console.log("actual: ", intersecting, start1, end1, start2, end2)
    if (intersecting) break;
  }

  return intersecting;
}

//credits: https://jsfiddle.net/justin_c_rounds/Gd2S2/light/
function checkLineIntersection(v1, v2, v3, v4) {
  // if the lines intersect, the result contains the x and y of the intersection (treating the lines as infinite) and booleans for whether line segment 1 or line segment 2 contain the point

  let line1StartX = v1.x;
  let line1StartY = v1.y;
  let line1EndX = v2.x;
  let line1EndY = v2.y;
  let line2StartX = v3.x;
  let line2StartY = v3.y;
  let line2EndX = v4.x;
  let line2EndY = v4.y;

  let denominator,
    a,
    b,
    numerator1,
    numerator2,
    result = {
      x: null,
      y: null,
      onLine1: false,
      onLine2: false,
    };
  denominator =
    (line2EndY - line2StartY) * (line1EndX - line1StartX) -
    (line2EndX - line2StartX) * (line1EndY - line1StartY);
  if (denominator == 0) {
    return result.onLine1 && result.onLine2;
  }
  a = line1StartY - line2StartY;
  b = line1StartX - line2StartX;
  numerator1 = (line2EndX - line2StartX) * a - (line2EndY - line2StartY) * b;
  numerator2 = (line1EndX - line1StartX) * a - (line1EndY - line1StartY) * b;
  a = numerator1 / denominator;
  b = numerator2 / denominator;

  // if we cast these lines infinitely in both directions, they intersect here:
  result.x = line1StartX + a * (line1EndX - line1StartX);
  result.y = line1StartY + a * (line1EndY - line1StartY);

  // if line1 is a segment and line2 is infinite, they intersect if:
  if (a > 0 && a < 1) {
    result.onLine1 = true;
  }
  // if line2 is a segment and line1 is infinite, they intersect if:
  if (b > 0 && b < 1) {
    result.onLine2 = true;
  }
  // if line1 and line2 are segments, they intersect if both of the above are true
  return result.onLine1 && result.onLine2;
}

full example for polygon area in sandbox (press shift key to start drawing)