3

我在2D工作。

我的用户可以绘制一些线和线段，我将它们存储在自定义对象类中，但基本上在 startX-Y 和 endX-Y 中。

现在我想找到，实际上只有球在里面的多边形，但是在阅读和研究了一些算法等之后。我想我必须找到所有的多边形，然后找到正确的多边形。

有没有人有一些示例代码，c#，java Objective-c！？我用一些伪代码解释尝试了几次，我不明白。

例如我的情况是什么

4

1 回答 1

2

概述

这里有许多不同的有趣问题：

1.给定屏幕上有一组线，用户将手指从任意点拖动到任意端点，我们需要形成一条不与线交叉的新线，起点和终点在哪里端点实际上位于现有线或边界上。

2. 下一个问题是我们如何维护一组活动的“相关”线段，这些线段形成了球所在的凸包。

3. 最后给定我们有一组活动的线段，我们如何找到这个形状的面积。

现在看来您已经回答了第 1 部分。所以我们专注于第 2 部分和第 3 部分。

对于第 2 部分，我们还将有兴趣询问：

4. 如果我们有一个凸包和一个点，我们如何确定该点是否在凸包中。

我们参考这里的解决方案 4查找一个点是否在一组点的凸包内而不计算包本身

如果您小心使用所使用的数据结构，则可以有效地完成完整的实现。这是一个简单的练习。如果我在这里做错了什么或者你不明白，请告诉我。我期待在您的游戏准备就绪时玩您的游戏！

第 3 部分的解决方案

实际上 3 比 2 容易，因为如果我们知道包含球的活动线段集（这是一个元组对列表 ((x_1start,y_1start), (x_1end, y1_end))），有两种方法可以计算面积。首先是做一个简单的算法来计算由这个元组列表中的所有起点和终点形成的凸包的面积。查找更复杂的面积算法，但如果找不到，请注意具有 n 边的船体有 n-2 个不重叠的三角形，三角形的面积很容易计算（http://www.mathopenref.com /polygontriangles.html）。笔记：

area = abs((x1-x2)*(y1-y3)-(y1-y2)*(x1-x3)) for triangle (x1,y1)(x2,y2)(x3,y3)

现在，如果您按所有 (x,y) 点围绕正 x 轴的角度对所有点进行排序，那么我们只需固定第一个点，然后连续遍历剩余的点对并找到这些三角形的面积。作为一个简单的练习，为什么需要这个排序步骤（提示：画一幅画）。

第 2 部分的解决方案

现在最困难的部分是 2。鉴于我们有一组活动的线段包围着球，我们如何添加一条新线，然后调整我们的活动组内的线段的大小和数量。请注意，在游戏开始时，活动集中恰好有 4 行是屏幕的边界（如果您喜欢归纳，这将是我们的基本情况）。

现在假设我们有一个包含球的任意活动集，并且用户添加了一条新线，我们假设它正好碰到两个现有的线段并且不跨越任何线段（通过第 1 部分算法）。现在我们需要修改活动集。通过算法 1，我们知道该点击中了哪些线段。所以活动集可以改变的唯一方法是，如果这点命中的两条线段都在活动集中（画一张图来看看这个事实）。

现在假设新的线段命中活动集中的两条线（这意味着它实质上将活动集分成两个凸包）。如果我们以旋转顺序维护我们的活动集（也就是说，我们确保它始终按关于正 x 轴的角度排序），我们只需以保持这种排序顺序的方式添加我们的新点。因此，例如假设我们的活动集点（将线段折叠为单线）是：

[(x1, y1), (x2, y2), (x3, y3), ..., (xn, yn), (x1, y1)]

我们要添加新的线段 ((x', y'), (x'', y''))，我们的新集合看起来像：

[(x1, y1), (x2, y2), (x', y'), (x3, y3), ..., (xn, yn), (x'', y''), (x1, y1)]

然后现在形成了两个凸包：

1. [(x1, y1), (x2, y2), (x', y'), (x'', y''), (x1, y1)]
2. [(x', y'), (x3, y3), ..., (xn, yn), (x'', y'')]

所以剩下的唯一问题是哪个是我们的新活动集。只需使用算法 4。

第 2 部分的数据结构

首先，我们需要类线段和点（为了简单起见，我避免实现诸如等于、哈希码之类的东西）：

class Point {
    public int x;
    public int y;
}

class LineSegment {
    public Point lineStart;
    public Point lineEnd;
}

现在我们可以表示我们的活动集数据结构：

class ActiveSet {
    public List<Line> thesortedlist;
}

现在我们首先用四行初始化我们的活动集，并将屏幕中心表示为 (0,0)：

LineSegment TopBorder = new LineSegment(new Point(10, 10), new Point(-10, 10));
LineSegment LftBorder = new LineSegment(new Point(-10, 10), new Point(-10, -10));
LineSegment BtmBorder = new LineSegment(new Point(-10, -10), new Point(10, -10));
LineSegment RightBorder = new LineSegment(new Point(10, -10), new Point(10, 10));

ActiveSet activeset = new ActiveSet();
activeSet.theActiveLines.add(TopBorder);
activeSet.theActiveLines.add(LftBorder);
activeSet.theActiveLines.add(BtmBorder);
activeSet.theActiveLines.add(RightBorder);

现在假设用户添加了一条从点 (0, 10) 到 (10, 0) 的线，所以这是一条对角线（称为 newSegment），新的活动集将如下所示：

------
-     -
-       -
-        -
-         -
-         -
-  B      -
-         -
-----------

注意右上角的切口，B 表示球。现在通过算法 1，我们知道行 TopBorder 和 RightBorder 被命中。现在这两个都在活动集中（我们可以使用哈希图更快地测试成员资格）。现在我们需要形成两个活动集，如下所示：

ActiveSet activesetLeft = new ActiveSet();
ActiveSet activesetRight = new ActiveSet();

现在，为了构建这些集合，请执行以下操作：

List<LineSegment> leftsegments = activeset.GetSegmentsBetween(TopBorder,
                                                              RightBorder);

List<RightSegment> rightsegments = activeset.GetSegmentsBetween(RightBorder,
                                                                TopBorder);

此函数 GetSegmentsBetween(LineSegment firstline, LineSegment secondline) 应该只定位列表中的第一行，然后返回所有元素，直到找到第二行（这可能需要两次遍历列表）。它不应在其返回值中包含这些第一行或第二行。现在假设我们有 activesetLeft 和 activesetright，我们需要执行以下操作：

activesetLeft.append(new Line(secondLine.lineStart, newSegment.lineStart));
activesetLeft.append(newSegment);
activesetLeft.append(new Line(newSegment.lineEnd, firstLine.lineEnd));

activesetRight.append(new Line(firstLine.lineStart, newSegment.lineEnd));
activesetRight.append(new Line(newSegment.lineEnd, newSegment.lineStart));
activesetRight.append(new Line(newSegment.lineStart, secondLine.lineEnd));

在代码中真的很难理解，但是上面所有内容的顺序很重要，因为我们希望保持按逆时针顺序排序。

留作练习如何加快速度（实际上，您不需要构建两个活动集，只需首先确定球是在新段的上方还是下方，然后相应地构建左侧或右侧的活动集）。

于 2013-04-10T14:14:19.030 回答