查找多边形的自相交部分。

huangapple go评论90阅读模式
英文:

Finding self intersection for a polygon

问题

我试图找出多边形中的自相交,以防止用户这样做。用户只能在由用户在3D空间中绘制的共面点构成的平面上绘制此多边形。

我的第一个想法是使这些点平行于X-Z平面,然后检查线段之间的相交。我能够检查2D中的相交,但旋转这些点不会保持形状,也不会平行于XZ轴,这会导致在测试相交时出现问题。

旋转前:
查找多边形的自相交部分。

旋转后:
查找多边形的自相交部分。

这是我如何进行旋转的代码。

const angle = pos.angleTo(new THREE.Vector3(0, 1, 0)) // 这里的pos表示圆的位置向量
const rotationMatrix = new THREE.Matrix4().makeRotationAxis(new THREE.Vector3(1, 0, 0), -angle); // 绕x轴旋转
rotationMatrix.makeRotationAxis(new THREE.Vector3(0, 0, 1), -angle) // 绕z轴旋转
circle.applyMatrix4(rotationMatrix);

它应该将在与XZ轴平行的任何平面上绘制的点旋转,但目前并没有发生这种情况。我对Three.js相当新手,在这里可能遗漏了某些内容。

如何正确旋转顶点,使其平行于XZ轴,同时不失去其形状?

英文:

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?

答案1

得分: 0

以下是翻译好的代码部分:

// 将三维向量投影到二维坐标系
function projectFromCamera(vertices, camera) {
  const projection = vertices.map((p) => p.clone().project(camera));
  return projection.map((p) => new THREE.Vector2(p.x, p.y));
}

/**
 * 检查最后一条线段是否与其他线段相交
 *
 * @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[projection.length - 2],
      projection[projection.length - 1],
      projection[x],
      projection[x + 1]
    );
    if (intersecting) break;
  }

  return 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++) {
    // 检查由第一个点和最后一个点组成的线段是否与其他线段相交
    intersecting = checkLineIntersection(
      projection[0],
      projection[projection.length - 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) {
  // 如果线段相交,结果包含交点的x和y坐标(将线段视为无限延伸),以及线段1和线段2是否包含交点的布尔值

  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;

  // 如果我们将这些线段无限延伸,它们在此交点处相交:
  result.x = line1StartX + a * (line1EndX - line1StartX);
  result.y = line1StartY + a * (line1EndY - line1StartY);

  // 如果line1是线段,而line2是无限线,它们相交如果:
  if (a > 0 && a < 1) {
    result.onLine1 = true;
  }
  // 如果line2是线段,而line1是无限线,它们相交如果:
  if (b > 0 && b < 1) {
    result.onLine2 = true;
  }
  // 如果line1和line2都是线段,它们相交如果上述两者都为真
  return result.onLine1 && result.onLine2;
}

希望这对你有所帮助。如果你需要更多的信息或有其他问题,请随时提问。

英文:

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) =&gt; p.clone().project(camera));
  return projection.map((p) =&gt; 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 &lt; 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(&quot;actual projectin: &quot;, projection, intersecting);

  for (let x = 1; x &lt; 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(&quot;intersecting: &quot;, x, intersecting);

    // console.log(&quot;actual: &quot;, 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 &amp;&amp; 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 &gt; 0 &amp;&amp; a &lt; 1) {
    result.onLine1 = true;
  }
  // if line2 is a segment and line1 is infinite, they intersect if:
  if (b &gt; 0 &amp;&amp; b &lt; 1) {
    result.onLine2 = true;
  }
  // if line1 and line2 are segments, they intersect if both of the above are true
  return result.onLine1 &amp;&amp; result.onLine2;
}

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

huangapple
  • 本文由 发表于 2023年6月26日 01:24:02
  • 转载请务必保留本文链接:https://go.coder-hub.com/76551631.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定