java - 计算与二维多边形相交的线段的长度

Question

给定线段S和多边形P，是否有一种快速算法可以返回S与多边形P相交的子线段的总长度？

注意:P 由闭合 LineString 定义(即:第一个点和最后一个点相等的点数组)。 P 没有任何“孔”，但可以是凹的和/或自相交的。

注意:最终目标是所有相交子段的总长度，如果可以更快地完成此操作，而无需检索所有子段的显式数组，那就更好了。

加分:该算法的 Java 实现。使用像 JTS 这样的库是可以的，只要生成的解决方案很快。

使用 JTS 的简单解决方案已经存在，但不支持自相交多边形，而且我相信这不是最快的。该解决方案涉及创建一个 Polygon 对象(对于 P)、一个 2 点 LineString 对象(对于 S)，并获取所得交点的长度。

这是执行此操作的代码:

    GeometryFactory fact = new GeometryFactory();
    WKTReader wktRdr = new WKTReader(fact);

    String wktP = "POLYGON((40 100, 40 20, 120 20, 120 100, 60 40, 40 100))";
    String wktS = "LINESTRING(20 60, 160 60)";
    Geometry pl = wktRdr.read(wktP);
    Geometry ls = wktRdr.read(wktS);
    Geometry in = pl.intersection(ls);
    System.out.println("P = " + pl);
    System.out.println("S = " + ls);
    System.out.println("P intersection S = " + in);
    System.out.println("S length = " + ls.getLength());
    System.out.println("P intersection S length = " + in.getLength());

编辑:对自相交多边形的考虑:解决方案虽然可能不是最快的，但可能涉及通过将自相交多边形分割成多个非自相交多边形来对其进行预处理。

关于这个问题的一些解释和一些伪代码在这里: Algorithm to split self-intersected Path2D into several not self-intersected paths?

Answer 1

在 O(n*log n) 内查找非自相交多边形的交集长度。

伪代码:

function intersecting_segment_length(set P, segment S):
  let starting_point = the bottom-most, left-most point in P.
  let E1, E2 = the edges of starting_point

  let intersections = new array.
  do:
     while E1 != E2 and E1 does not cross S:
        E1++ //move E1 "clockwise" around P
     while E2 != E1 and E2 does not cross S:
        E2-- //move E2 "counterclockwise" around P
     if E1 != E2:
        p1 = the intersection of E1 and S
        p2 = the intersection of E2 and S
        intersections.add(new line segment from p1 and p2)
  until E1 == E2.

  return sweepline(intersections)

扫描线伪代码:

function sweepline(array segments):
  let points = start and end points of all segments
  sort points as they intersect S

  let last_point = points.first()
  let num_segments = 0 //num segments intersected by sweepline
  let length = 0

  for each point p in points - last_point:
     if p is the leading point in p.owning_segment:
        num_segments++
     else: //trailing point
        num_segments--
        if num_segments % 2 == 0: //I think
           length += distance between p and last_point
     last_point = p

  return length

复杂性:

• P 中的行走边:O(n)，其中 n 是 P 中的边/顶点数。
• 对交点进行排序:O(m*log m)，其中 m 是 P 与 S 的交集数量。
• 使用扫描线求总长度:O(m)。
• 不幸的是，我们可以构造一个与 S 有 O(n) 次交集的“梳状多边形”，因此总复杂度为 O(n*log n)在最坏的情况下。

注意:

• 如果您可以确定 P 的自相交(例如，当您在 P 周围行走时)，您可以将这些事件注入(inject)扫描线并相应地修改其算法。结果可能可以在O(n*log n)内完成。
• 有关扫描线实现示例(较少伪代码)，您可以查看 this answer .