2D의 다각형과 교차하는 세그먼트의 길이 계산

Question

세그먼트 S와 폴리곤 P가 주어지면 S 교차 교차 폴리곤 P의 서브 세그먼트의 총 길이를 반환하는 빠른 알고리즘이 있습니까?

참고 : P는 닫힌 LineString (즉, 첫 번째 점과 마지막 점이 같은 점의 배열)에 의해 정의됩니다. P는 어떤 "구멍"도 가지지 않지만, 오목하거나 자기 교차 할 수 있습니다.

참고 : 최종 목표는 교차하는 모든 하위 세그먼트의 총 길이이며, 모든 하위 세그먼트를 명시 적으로 검색하지 않고 더 빨리 수행 할 수 있다면 더 좋습니다.

보너스 포인트 : 상기 알고리즘에 대한 Java 구현. 결과 솔루션이 빠르면 JTS와 같은 라이브러리를 사용할 수 있습니다.

JTS를 사용하는 간단한 솔루션은 이미 존재하지만 자체 교차 폴리곤을 지원하지 않으며, 가장 빠르지 않습니다. 이 솔루션에는 다각형 객체 (P의 경우), 두 점의 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

는 (N * 로그 n) O 비 - 자기 교차 다각형의 교차 길이를 찾기.

의사 코드 :

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) 

Sweepline 의사 코드 :

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의 정점.
• 교차점 정렬 : 은 P와 S의 교차 수입니다.
• 전체 길이를 찾기 위해 스윕 라인 사용 : O(m).
• 불행히도 우리는 O(n) 개의 S와 교차하는 "빗 모양의 다각형"을 만들 수 있으므로 최악의 경우 총 복잡도는 O(n*log n)입니다.

참고 : P의 자기 교차점을 확인할 수있는 경우 (당신이 P 주위를 산책하는 동안 예를 들어,)

• , 당신은 sweepline에 해당 이벤트를 주입하고 그에 따라 알고리즘의 수정할 수 있습니다 . 결과는 일 수 있고 일 수 있습니다. O(n*log n)입니다.
• 샘플 sweepline 구현 (의사 코드가 적음)의 경우 this answer을 볼 수 있습니다.