objective-c - 从一组线中查找多边形

Question

我在二维空间工作。
我的用户可以绘制一些直线和线段，我将它们存储在自定义对象类中，但基本上是在startx-y和endx-y中。
现在我只想找到球在里面的多边形，但是在阅读和研究了一些算法等之后，我想我必须找到所有的多边形，然后找到正确的多边形。
有没有人有一些示例代码，c，java objective-c！是吗？
我试了好几次用伪代码解释，我不明白。

Answer 1

概述
这里有很多有趣的问题：
一。假设你在屏幕上有一组线，而用户把他们的手指从任意点放置并拖动到任意端点，我们需要形成一条新的线，它不跨越线，并且起点和终点实际上位于现有的线或边界上。
2.下一个问题是我们如何保持一组活跃的“相关”线段，形成球所在的凸包。
三。最后给出了一组活动线段，我们如何找到这个形状的面积。
现在看来你已经回答了第一部分。所以我们关注第二部分和第三部分。
对于第2部分，我们还想问：
四。如果我们有一个凸壳和一个点，我们如何确定这个点是否在壳中。
关于4Find if a point is inside a convex hull for a set of points without computing the hull itself
如果您对使用的数据结构非常小心，则可以有效地实现完全实现。这只是一个简单的练习。如果我做了不正确的事情，或者你不明白，请告诉我。我期待着你的比赛准备好了！
第3部分的解决方案
事实上，3从2是容易的，因为如果我们知道包含球的线段的活动集合（这是一对元组的列表（（XY1START，YY1START），（XY1结束，Y1Y端）），则有两种计算区域的方法。第一个是做一个简单的算法来计算由这个元组列表中的所有开始和结束点形成的凸包区域。查找更复杂的区域算法，但如果找不到，则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轴的角度对所有（x，y）点进行排序，那么我们只需先确定第一个点，然后连续地穿过剩下的对，找出这些三角形的面积。作为一个简单的练习，为什么需要这个排序步骤（提示：画一张图片）。
第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部分的数据结构
首先，我们需要类的线段和点（为了简单起见，我避免实现equals和hashcode之类的东西）：

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

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

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

class ActiveSet {
    public List<Line> thesortedlist;
}

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

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，我们知道线TopEnter和RightBorder命中。现在这两个都在ActuestEnter中（我们可以通过使用HASMAP更快地测试成员资格）。现在，我们需要形成如下两个条件：

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

现在，为了建立这些集合，进行如下：

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

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

此函数getSegmentsBetween（线段第一行，线段第二行）应该只定位列表中的第一行，然后返回所有元素，直到找到第二行（这可能需要两次遍历列表）。它不应该在返回值中包含这些第一行或第二行。现在假设我们已经有了子查询和子查询，我们需要执行以下操作：

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)); 

在代码中很难理解，但是上面所有的顺序都很重要，我们希望保持逆时针顺序排序。
这是一个练习，你如何加快速度（事实上，你不需要建立两个活动集，只是先弄清楚球是否在新的段之上或下面，并相应地构建左或右活动集）。