2

给定一个段 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？

4

1 回答 1

2

在 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 周围走动时），您可以将这些事件注入扫描线并相应地修改它的算法。结果大概可以在O(n*log n).
  • 对于示例扫描线实现（较少的伪代码），您可以查看此答案。
于 2012-08-30T14:09:33.327 回答