1

我有一个相当复杂的几何问题需要解决，我想知道是否有人可以指出资源来解决它。

我有一个不规则的形状，由垂直和水平的喜欢组成。它由一系列顺时针方向的 x,y 点描述，形成一条路径。最后一点连接到第一个点以形成形状的边界。没有一条线会相互交叉。当我在屏幕上绘制形状时，我使用沿 Y 轴的经典扫描线算法将形状变成一系列我填充的矩形。

但是现在我希望用户能够通过使用水平线或垂直线再次绘制从边界上的一个点到边界上的另一个点的路径，将形状分成两部分。在图中，用户从 1 开始绘制并最终在 2 处进行切片。

所以这里有一些我必须削减的东西的例子。使用用户绘制的红色切割路径将原始形状切割成部分 A 和 B。请注意，不能保证用户将按照与我的区域相同的顺时针方向进行切割（即下面的 1 和 2 可以颠倒）所以我必须处理这个问题。

带有路径的示例形状

该线将完全包含在边界形状内，并且不会越过自身。即当我用路径切割形状时，它将产生恰好2个新形状。

大声思考我认为这个伪代码可能是这样的：

  1. 将形状描述为一系列 x、y 点，编号为 0 到 N。N 连接到 0 以闭合形状。
  2. 允许用户绘制在形状路径上某处开始和结束的剪切路径。UI 可防止用户越过自己的线条或在形状之外绘图。
  3. 计算出切割路径开始和结束的形状中的哪些线索引。线索引由点索引 0->1, 1->2, ... N-1->N, N->0 描述
  4. 为确保用户的剪切路径与形状的方向相同，如果出现以下情况，请反转其路径：a) 最终形状线索引 < 起始形状线索引 b) 或形状结束线索引 == 形状起始线索引但结束切割点更接近线索引起点
  5. 构造两个点列表。a) lines >= end index and <= start index + Cut Path, 在切割点修剪开始/结束线 b) Cut path + lines >= start and <= end index, 在切割点修剪开始/结束线
  6. 从点列表创建新区域。

我认为这可能会奏效，但显然如果那里有实际的代码已经这样做了，那会更容易！

4

1 回答 1

1

我不知道那里的代码已经完成了这项工作。

实际上，您需要为两个新形状之一反转切割路径，而不是为另一个反转切割路径。（如果您所说的关于顺时针遍历的所有形状是正确的。）我认为查看您想要为每个形状采用该路径的最简单方法是：（1）从 UI 交互中，您将知道在哪里切割路径的形状；(2a) 从切割路径的一端开始，顺时针绕着形状走，直到碰到另一端，然后沿着切割路径回到第一端，给你一个形状；(2b) 现在从原来的一端开始，沿着另一个方向的切割路径，绕着形状顺时针走，直到你回到原来的切割路径端点，给你另一个形状。

除此之外，您的伪代码对我来说看起来不错。

于 2012-05-01T09:05:35.473 回答