提问人：Olin Kirkland 提问时间：7/30/2019 最后编辑：Olin Kirkland 更新时间：7/30/2019 访问量：276
在矩形的边缘上获取两个点
Getting two points on the edges of a rectangle
问：
我有一个矩形，想：
- 在一侧（任何）获得一个随机点。
- 在一侧（先前选择的除外）上获得一个随机点。
我最初的方法是为每个可能的一侧创建数组。
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） 返回 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};
我不认为这是解决这个问题的最有效方法。
你会怎么做？
答：
2赞
jcalz
7/30/2019
#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并代表我们选择的指数。第一个选择一个介于数组长度和小于数组长度 1 之间的整数。我们通过在数组的长度和长度之间选择一个实数（好吧，浮点数等），然后取该实数的底数来做到这一点。由于长度是 ，我们所做的是在 和 之间均匀地选择一个实数。这些数字中有四分之一介于 和 之间，另外四分之一介于 和 之间，最后一个季度介于 和 之间。这意味着您有 25% 的机会选择 、 和 。（选择的几率基本上是 0，或者如果以排除上限的正常方式实现，则可能正好为 0）。s2arr004040112233401234rand
因为我们现在在数组的长度和长度之间均匀地选择一个数字。在本例中，我们分别选择 、 或 33% 的几率。我们将该数字相加，然后在除以时取余数。把我们正在做的事情想象成从第一边开始，然后顺时针移动 1、2 或 3 边（比如说）以选择下一条边。这完全消除了两次选择同一侧的可能性。s21123s14s1
现在让我们看看在给定一个实例的情况下，在一条线段上随机选择一个点（可以定义为 ，对应于线段的两端和线段）涉及什么：PointPairp1p2Rand
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 };
}
在这里，我们要做的是选择一个随机数，表示从到我们想要走多远。如果是，我们选择 。如果是，我们选择 。如果 是 ，则在 和 之间选择中间位置。其一般公式是 和 给定之间的线性插值。fracp1p2frac0p1frac1p2frac0.5p1p2p1p2frac
希望在这两者之间，您可以实现您正在寻找的算法。祝你好运！
1赞
Scott Sauyet
7/30/2019
#2
Jcalz已经给出了一个很好的答案。这是我在评论中询问的变体的替代版本：当您希望在周长的两侧均匀选择点时，因此，如果您的比率为 ，则第一个点位于水平侧的可能性是垂直点的四倍。（这意味着击中两个相对的长边的几率是24/45;两个相对的短边是1/45;各一个是20/45 - 通过简单但略显乏味的计算。w : h4 : 1
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))
)其中唯一复杂的位是 的计算。我们计算一个介于 0 和其余三条边的总长度之间的随机数，方法是将所有四条边相加并减去当前边的长度，如果为偶数，则为奇数。然后，我们将其与边的总长度相加，直到并包括索引（其中 和 调用只是计算水平和垂直边的数量，这些值分别乘以宽度和高度，然后相加），最后取结果的浮点模数与周长。这与jcalz的答案中的技术相同，但通过处理边长而不是简单的计数而变得更加复杂。r2widthidxheightceilfloor
我没有创建任何类或接口的实例，实际上也没有在这里做任何 Typescript，但您可以自己轻松添加。rand
评论
!====tblr