4

在二维平面中，我有一个由 4 个顶点、、A和定义的矩形。我现在希望找到落入 rectangle 的整数点（坐标是整数）。BCDABCD

在问之前，我所做的计算非常昂贵。简而言之，我正在枚举所有整数点并检查该点是否在矩形中。我发现在我的项目中使用它太残酷了，因为我有很多观点。

这应该如何优雅地完成？

更新：请注意，矩形可以是随机方向，具体取决于四个点的坐标。假设位置很好有点作弊。

4

2 回答 2

3

您的矩形应以四线为界。假设您有以下矩形

      A
      /\
     /  \
   B \   \ 
      \  /C
       \/
        D

现在画两条水平线，一条穿过 B，另一条穿过 C。这将矩形分成 3 个区域。

      A
      /\
     /__\P
   B \___\ 
     Q\  /C
       \/
        D

所有三个区域都由 2 组不同的线定义。

Top: AB to AP.
Middle: BQ to PC.
Bottom: QD to CD.

对于这些区域中的每一个，迭代满足边界线条件的 x 和 y 的整数值。比如A、B、D、C点分别是(0,10.5)、(-10.5, 0)、(0, -10.5)、(10.5, 0)，一个旋转的正方形，
应该只有1条水平线（X 轴）。

对于 Top 区域，循环可以如下所示（您可以为 python 修改它）：

for ( int y = 10; y >= 0; y-- )
  for ( int x = int(y-10.5); x <= int(10.5-y); x++ ) // the int an be changed to floor or ceiling.
    print( x, y );

复杂度顺序：O(N)，其中 N 是整数点的数量。

于 2013-10-16T10:26:04.400 回答
0

您可以在坐标轴上映射 4 个顶点。假设 A(x1, y1),B(x2, y1), C(x1, y2),D(x2, y2) 和 x1 <= x2 && y1 <= y2，当且仅当 x1<= x <= x2 和 y1 <= y <= y2，点 p(x,y) 落入矩形 ABCD。

于 2013-10-16T10:15:42.283 回答