Closed7

多角形の内外判定

exitexit

単純に標準入力された値が四角形の範囲内かを見ればいいとは思うが，せっかくだから他の方法で解いてみたい

exitexit

外積はなんとか出た
最初全然正負が合わず，なんでかと思ったら，四角形の頂点を反時計回りに並べていなかったからだった
気を付けないといけない......
下記サイトの記事を参考にさせてもらいました．
https://kunassy.com/python-polygon-inside-outside-judgment/#toc7

const n = Number(lines[0]);
  const points = lines
    .slice(1, n + 3)
    .map((line) => line.split(" ").map(Number))
    .map((points) => ({ x: points[0], y: points[1] }));
  console.log(points);
  const [xs, xt] = [points[n].x, points[n].y];
  const [ys, yt] = [points[n + 1].x, points[n + 1].y];

  const A = { x: xs, y: ys };
  const B = { x: xt, y: ys };
  const C = { x: xt, y: yt };
  const D = { x: xs, y: yt };

  const vector_AB = createVector(A, B);
  const vector_BC = createVector(B, C);
  const vector_CD = createVector(C, D);
  const vector_DA = createVector(D, A);

  let count = 0;

  function cross(v1, v2) {
    return v1.x * v2.y - v1.y * v2.x;
  }

  function createVector(a, b) {
    return { x: b.x - a.x, y: b.y - a.y };
  }

  for (let index = 0; index < n; index++) {
    let vector_AE = createVector(A, points[index]);
    let vector_BE = createVector(B, points[index]);
    let vector_CE = createVector(C, points[index]);
    let vector_DE = createVector(D, points[index]);

    let vector_cross_AB_AE = cross(vector_AB, vector_AE);
    let vector_cross_BC_BE = cross(vector_BC, vector_BE);
    let vector_cross_CD_CE = cross(vector_CD, vector_CE);
    let vector_cross_DA_DE = cross(vector_DA, vector_DE);

    console.log(
      vector_cross_AB_AE,
      vector_cross_BC_BE,
      vector_cross_CD_CE,
      vector_cross_DA_DE
    );
}
exitexit

符号が一つでも違うと，点は外にある，と判定できるけど，これ辺の上に点がある場合は弾かれてしまうっぽい
辺上にあっても内部判定するように修正しないといけない
そう考えると，外積より多角形の内部にある点と頂点が成す角の和が360°になるほうを採用したほうが楽なのかな　要検証ではある

exitexit

とりあえずPaizaでは次のコードで合格．もっとキレイに書けるとは思うけどとりあえずコレで良しとする．

rectangle.js
  const n = Number(lines[0]);
  const points = lines
    .slice(1, n + 3)
    .map((line) => line.split(" ").map(Number))
    .map((points) => ({ x: points[0], y: points[1] }));
  //const pointsObject = points.map((point) => ({ x: point[0], y: point[1] }));
  console.log(points);
  //console.log(pointsObject);
  const [xs, xt] = [points[n].x, points[n].y];
  const [ys, yt] = [points[n + 1].x, points[n + 1].y];

  const A = { x: xs, y: ys };
  const B = { x: xt, y: ys };
  const C = { x: xt, y: yt };
  const D = { x: xs, y: yt };

  const vector_AB = createVector(A, B);
  const vector_BC = createVector(B, C);
  const vector_CD = createVector(C, D);
  const vector_DA = createVector(D, A);

  let count = 0;

  function cross(v1, v2) {
    return v1.x * v2.y - v1.y * v2.x;
  }

  function createVector(a, b) {
    return { x: b.x - a.x, y: b.y - a.y };
  }

  function judgeOnPointsOrLines(point, min, max) {
    return (
      min.x <= point.x &&
      point.x <= max.x &&
      min.y <= point.y &&
      point.y <= max.y
    );
  }

  for (let index = 0; index < n; index++) {
    let vector_AE = createVector(A, points[index]);
    let vector_BE = createVector(B, points[index]);
    let vector_CE = createVector(C, points[index]);
    let vector_DE = createVector(D, points[index]);

    let vector_cross_AB_AE = cross(vector_AB, vector_AE);
    let vector_cross_BC_BE = cross(vector_BC, vector_BE);
    let vector_cross_CD_CE = cross(vector_CD, vector_CE);
    let vector_cross_DA_DE = cross(vector_DA, vector_DE);

    // console.log(
    //   vector_cross_AB_AE,
    //   vector_cross_BC_BE,
    //   vector_cross_CD_CE,
    //   vector_cross_DA_DE
    // );

    if (
      vector_cross_AB_AE >= 0 &&
      judgeOnPointsOrLines(A, { x: xs, y: ys }, { x: xt, y: yt }) &&
      vector_cross_BC_BE >= 0 &&
      judgeOnPointsOrLines(B, { x: xs, y: ys }, { x: xt, y: yt }) &&
      vector_cross_CD_CE >= 0 &&
      judgeOnPointsOrLines(C, { x: xs, y: ys }, { x: xt, y: yt }) &&
      vector_cross_DA_DE >= 0 &&
      judgeOnPointsOrLines(D, { x: xs, y: ys }, { x: xt, y: yt })
    ) {
      count++;
    }
  }
  console.log(count);
このスクラップは2024/07/23にクローズされました