Locating the point of intersection within a polygon with itself

Question

Locating the point of intersection within a polygon with itself

I am attempting to identify instances of self-intersection in a polygon in order to prevent users from creating them. Users are only permitted to draw the polygon on a plane formed by connecting the coplanar points they plot in 3D space.

My initial approach involved aligning these points parallel to the X-Z plane and then checking for intersections between line segments. While I could successfully detect intersections in 2D, rotating these points did not maintain their shape or alignment with the XZ axis, leading to issues during intersection testing.

Before rotation: https://i.sstatic.net/Yr35i.png

After rotation https://i.sstatic.net/LaFUE.png

This is my current rotation method.

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);

The goal is to rotate the vertices so that they align parallel to the XZ axes without distorting their original shape. As a newcomer to three.js, I believe there may be something crucial missing from my implementation.

How can I accurately rotate the vertices to achieve parallel alignment with the XZ axes while preserving the shape?

javascript vector three.js 3d

Answer 1

Answer №1

My goal was to determine the self-intersection of a polygon to prevent users from creating polygons with self-intersections. To achieve this, I implemented a method that involves projecting the polygon onto a 2D coordinate system and checking for any intersecting line segments.

To project vectors in 3D, you can utilize the Vector3.project(camera) function, which returns the projection in xy coordinates. Subsequently, you can employ line-segment intersection algorithms to detect intersections.

Below is a brief code snippet demonstrating this process:

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.Camera} camera
 * @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 projection: ", projection, intersecting);

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

  return intersecting;
}

//credits: https://jsfiddle.net/justin_c_rounds/Gd2S2/light/
function checkLineIntersection(v1, v2, v3, v4) {
  // algorithm to check for line intersection

  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,
    };

  // calculation logic for intersection
  ...

  return result.onLine1 && result.onLine2;
}

For a complete example of polygon area calculation using Three.js, visit the demo on CodeSandbox (press Shift key to start drawing).

Answer 2

My goal was to determine the self-intersection of a polygon to prevent users from creating polygons with self-intersections. To achieve this, I implemented a method that involves projecting the polygon onto a 2D coordinate system and checking for any intersecting line segments.

To project vectors in 3D, you can utilize the Vector3.project(camera) function, which returns the projection in xy coordinates. Subsequently, you can employ line-segment intersection algorithms to detect intersections.

Below is a brief code snippet demonstrating this process:

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.Camera} camera
 * @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 projection: ", projection, intersecting);

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

  return intersecting;
}

//credits: https://jsfiddle.net/justin_c_rounds/Gd2S2/light/
function checkLineIntersection(v1, v2, v3, v4) {
  // algorithm to check for line intersection

  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,
    };

  // calculation logic for intersection
  ...

  return result.onLine1 && result.onLine2;
}

For a complete example of polygon area calculation using Three.js, visit the demo on CodeSandbox (press Shift key to start drawing).

Locating the point of intersection within a polygon with itself

Answer №1

Similar questions

Lock the three.js camera to the top-down orientation of a vehicle

Tips for managing the react-bootstrap carousel using personalized buttons

What is the process for connecting controls to Canvas sprites?

Using jQuery to retrieve the id with [id^=''] when making an AJAX request, then populating and generating a table based on the retrieved data

merge a pair of scopes within Angular

A method to retrieve the content of an input field and assign it to an onclick event

Node.js server encountering a cross-domain error

Performing a jQuery ajax request by passing data obtained from iterating through elements

Determine which link the user has clicked on using JavaScript

Iterating Through Multiple Dimensions

What is the best way to insert a button at the end of the last row in the first column and also at the

Incorporate a binary document into a JSPdf file

"Scotchy McScotchface's to-do list application powered

Errors caused by Typescript transpilation only manifest on the production server

"Complete with Style: Expand Your Horizons with Material-UI

Spirit.py navigates using javascript

Transforming the text to be "unreadable"

Implementing a special class for the currently selected navigation item as a solution to the Bootstrap limitation

What is the best way to save my photo on the server?

Error encountered when serving tiles using Node JS and Leaflet from the same domain