在矩形的边缘上获取两个点

Question

我有一个矩形，我想：

在一侧（任意一侧）上随机取一个点。
在一侧（先前选择的除外）获得一个随机点。

我最初的方法是为每个可能的边创建数组。

var arr:Array = [[{x:0,y:0},           // Top
                  {x:width,y:0}],      //
                 [{x:width,y:0},       // Right
                  {x:width,y:height}], //
                 [{x:width,y:height},  // Bottom
                  {x:0,y:height}],     //
                 [{x:0,y:height},      // Left
                  {x:0,y:0}]];         //

然后，我得到双方。 rand 是 Rand 的一个实例并且有以下方法： .next() 提供介于 0 和 1 之间的随机数 .between(x,y) 其中 returns x 和 y 之间的随机数。

var firstSide:Array = arr[rand.next() * arr.length];
var secondSide:Array;
do {
    secondSide = arr[rand.next() * arr.length];
} while(secondSide.equals(firstSide));

最后，我计算我的分数。

var pointOnFirstSide:Object = {x:rand.between(firstSide[0].x, firstSide[1].x),
                               y:rand.between(firstSide[0].y, firstSide[1].y};
var pointOnSecondSide:Object = {x:rand.between(secondSide[0].x, secondSide[1].x),
                                y:rand.between(secondSide[0].y, secondSide[1].y};

我认为这不是解决此问题的最有效方法。

你会怎么做？

Answer 1

假设我们有以下接口和类型：

interface Rand {
  next(): number;
  between(x: number, y: number): number;
}
interface Point {
  x: number;
  y: number;
}
type PointPair = readonly [Point, Point];

并相信您在评论中所说的程序是：首先随机选择两侧，然后在这些两侧随机选择点...首先让我们看看随机选择两侧涉及什么：

  const s1 = Math.floor(rand.between(0, arr.length));
  const s2 = (Math.floor(rand.between(1, arr.length)) + s1) % arr.length;

s1 和 s2 代表我们选择的 arr 的索引。第一个选择 0 和比数组长度小一之间的整数。我们通过在 0 和数组长度之间选择一个实数（好吧，浮点数，随便什么），然后取 floor of that real number. Since the length is 4, what we are doing is picking a real number uniformly between 0 and 4. One quarter of those numbers are between 0 and 1, another quarter between 1 and 2, another quarter between 2 and 3, and the last quarter are between 3 and 4. That means you have a 25% chance of choosing each of 0, 1, 2 and 3. (The chance of choosing 4 is essentially 0, or perhaps exactly 0 if rand is implemented in the normal way which excludes the upper bound).

来做到这一点

对于s2，我们现在选择一个介于1和数组长度之间的数字。在这种情况下，我们选择 1、2 或 3，每个概率为 33%。我们将该数字添加到 s1，然后在除以 4 时取 remainder。将我们正在做的事情想象成从第一面 s1 开始，然后顺时针移动 1、2 或 3 面（比方说）以选择下一面。这样就彻底杜绝了两次选择同一边的可能性。

下面我们看看在线段上随机取一个点（可以定义为一个PointPair，对应线段的两端p1和p2线段）给定一个 Rand 实例：

function randomPointOnSide([p1, p2]: PointPair, rand: Rand): Point {
  const frac = rand.next(); // between 0 and 1
  return { x: (p2.x - p1.x) * frac + p1.x, y: (p2.y - p1.y) * frac + p1.y };
}

这里我们要做的是选择一个随机数 frac，代表我们想要从 p1 到 p2 的距离。如果 frac 是 0，我们选择 p1。如果 frac 是 1，我们选择 p2。如果 frac 是 0.5，我们选择 p1 和 p2 之间的中间值。一般公式是给定 frac.

p1 和 p2 之间的线性插值

希望在这两者之间，您可以实现您正在寻找的算法。祝你好运！

Link to code

Answer 2

jcalz 已经给出了很好的答案。这是我在评论中询问的变体的替代版本：当您希望在周边的两侧均匀选择点时，如果您的 w : h 比率是 4 : 1，则第一个点是躺在水平一侧的可能性是垂直一侧的四倍。（这意味着击中两个相反的长边的机会是 24/45；两个相反的短边，1/45；和每一个，20/45——通过一个简单但有点乏味的计算。）

const rand = {
  next: () => Math. random (),
  between: (lo, hi) => lo + (hi - lo) * Math .random (),
}

const vertices = (w, h) => [ {x: 0, y: h}, {x: w, y: h}, {x: w, y: 0}, {x: 0, y: 0} ]

const edges = ([v1, v2, v3, v4]) => [ [v1, v2], [v2, v3], [v3, v4], [v4, v1] ]

const randomPoint = ([v1, v2], rand) => ({
  x: v1 .x + rand .next () * (v2 .x - v1 .x),
  y: v1 .y + rand .next () * (v2 .y - v1 .y),
})

const getIndex = (w, h, x) => x < w ? 0 : x < w + h ? 1 : x < w + h + w ? 2 : 3

const twoPoints = (w, h, rand) => {
  const es = edges (vertices (w, h) )
  const perimeter = 2 * w + 2 * h
  const r1 = rand .between (0, perimeter)
  const idx1 = getIndex (w, h, r1)
  const r2 = (
    rand. between (0, perimeter - (idx1 % 2 == 0 ? w : h)) +
      Math .ceil ((idx1 + 1) / 2) * w + Math .floor ((idx1 + 1) / 2) * h
  ) % perimeter
  const idx2 = getIndex (w, h, r2)
  return {p1: randomPoint (es [idx1], rand), p2: randomPoint (es [idx2], rand)}
}

console .log (
  // Ten random pairs on rectangle with width 5 and height 2
  Array (10) .fill () .map (() => twoPoints (5, 2, rand))
)

唯一比较复杂的是r2的计算。我们通过将所有四个边加在一起并减去当前边的长度来计算 0 和剩余三个边的总长度之间的随机数，width 如果 idx 是偶数，height 如果它很奇怪。然后我们将它添加到边的总长度中，直到并包括索引（其中 ceil 和 floor 调用只是计算水平和垂直边的数量，这些值乘以宽度和高度, 并相加) 最后用周长取结果的浮点模数。这与 jcalz 的回答中的技术相同，但通过处理边长而不是简单的计数变得更加复杂。

我没有让 rand 成为任何 class 或接口的实例，实际上也没有在这里做任何 Typescript，但您可以很容易地自己添加它。

在矩形的边缘上获取两个点

Getting two points on the edges of a rectangle

javascript

language-agnostic

arrays

math

typescript