消除一条线不在附近的区域

Question

我有一张地图，上面标有一些死区（无法到达的区域）。

我的应用程序流程中有一点需要检查此地图上的某条线是否可达。

现在，我的线相交代码非常可靠，但我无法弄清楚如何限制需要检查的死区数量，因为其中一些将在地图的另一侧。

现在死区只是一个 List<Point>，其中 Point 是 x 和 y，都是 double 类型，我的行只是 2 个描述开始的独立点和行尾。

所以，在我调用它并针对所有死区进行处理的地方，这就是我正在做的事情：

DeadZones.All(dz => !FastPolygons.DoesLineIntersectPolygon(point1, point2, dz.Polygon));

首先，我认为我可以使用死区中的 MaxX 和 MaxY 来消除远处的点，但是如果两个点都位于死区之外，那么它们仍然会被处理并且它将需要线两端的一个点实际位于死区中，以便消除该死区。

我写了一个方法，我可以在我的 linq 语句的 Where 中使用它来尝试这个，然后我才意识到这是行不通的。这就是我的尝试

private static bool ZoneCouldNotOverlap(Point point, Zone zone)
{
    return (zone.MaxX < point.X || zone.MaxY < point.Y) || (zone.MinX > point.X || zone.MinY > point.Y);
}

然后 Linq 语句变成了这样：

DeadZones.Where(x=> ZoneCouldNotOverlap(point1,x) || ZoneCouldNotOverlap(point2,x)).All(dz => !FastPolygons.DoesLineIntersectPolygon(point1, point2, dz.Polygon));

所以我已经到了可以消除大部分地图的地步，因此不处理我不感兴趣的地图部分的死区，但我似乎无法在我的 Linq 语句中了解如何执行此操作。非常感谢任何帮助。

编辑： 我也非常欢迎提供有关如何在此处应用并行化的最佳建议

Answer 1

因此，这将处理 5000 次迭代所需的时间缩短了约 30 秒，因此这似乎是一个足够的答案。

我所做的是创建一条 struct 调用线来代替一对点。

看起来像这样：

 public struct Line
 {
     public List<Point> Points { get; private set; }
     public double MaxX { get; private set; }
     public double MinX { get; private set; }
     public double MinY { get; private set; }
     public double MaxY { get; private set; }

     public Line(Point start, Point end) : this()
     {
         Points = new List<Point>();
         Points.AddRange(new[] {start, end});
         var xs = Points.Select(p => p.X);
         var ys = Points.Select(p => p.Y);
         MaxX = xs.Max();
         MinX = xs.Min();
         MaxY = ys.Max();
         MinY = ys.Min();
     }
 }

然后我在一个名为 ZoneCouldNotOverlapLine() 的新方法中使用了它，看起来像这样：

 private static bool ZoneCouldNotOverlapLine(Line line, Zone zone)
 {
     return (line.MinX > zone.MaxX || line.MaxX < zone.MinX) && (line.MaxY < zone.MinY || line.MinY > zone.MaxY);
 }

反过来，我在我的 Linq 语句中使用如下：

DeadZones.Where(z=> !ZoneCouldNotOverlapLine(line,z))
.All(dz => !FastPolygons.DoesLineIntersectPolygon(point1, point2, dz.Polygon));

这是有效的说法，只看整条线不在区域单侧的死区。在我的代码中还有一些地方可以像这样进行优化，并且解决这个问题将帮助我无休止地解决这些问题。

消除一条线不在附近的区域

Eliminate zones that a line is nowhere near

c#

.net

linq

geometry