병렬 (유사) 폴리선을 함께 그룹화하십시오.

Question

두 폴리 라인이 평행한지 확인하려면 어떻게해야합니까? 그들은 exacly 수 평행 필요는 없지만이 같은 방향

@Edit 내가 조금 다 더 뒤에 아이디어를 설명 할 필요가 있다고 생각

에 가고 있다는 점에서 유사해야합니다. 입력으로 나는 많은 폴리 ​​라인을 얻는다. 내가하고 싶은 것은 폴리 라인을 서로 평행하게 그룹화하는 것입니다 (일반적으로 비슷한 방향으로). 결과는 비슷한 폴리선 그룹입니다.

폴리 라인은 어떻게 생겼습니까? 그들은 일반적으로 위쪽이나 왼쪽 또는 오른쪽으로 직선으로 이동합니다. 같은 y 값에서 시작하지 않아도됩니다. 폴리 라인의 점은 일반적으로 동일한 높이가 아니며 다른 y 값을 가짐을 의미합니다. 폴리 라인이 일정한 간격으로 평행하고 자주 달라지기 시작하면서 간격 경계를 찾고이 간격으로 폴리 라인의 일부를 정의하고 싶습니다. 물론 간격이 작아서는 안됩니다.

이제 예제를 설명하고 내가 원하는 결과를 보여 드리겠습니다. 파란색으로 표시된 4 개의 폴리선 P1 ~ P4로 시작합니다. 인간의 경우 P1 ~ P3의 선은 빨간 선 b1까지 평행합니다. 따라서 이것은 병렬 폴리 라인의 첫 번째 그룹 G1 일 수 있습니다. 수정 지시 b1 이후에는 평행 폴리선 P1 및 P4가 있습니다. 따라서 그룹 G2를 구축합니다. 폴리선 P3은 다른 어떤 것과도 평행하지 않으므로 G3 그룹에만 속합니다.

: 는 그림이 병렬로 선언해야 두 개의 폴리 라인의

예를 도움이되기를 바랍니다. 두 개의 폴리 라인

예 I이 결과를 얻을 입력 폴리 라인에 더글라스 peuker 알고리즘을 적용한 후에

@Edit 2

NOT 평행

선언되어야한다. 이제 병렬 폴리 라인을 함께 그룹화하려고합니다. 비교할 항목을 찾으려면 어떻게합니까? 그림 "세그먼트를 비교하는 방법"에서 볼 수 있듯이 폴리선 1과 2는 간격 [b1, b2]에만 그룹화해야합니다. 이 간격은 어떻게 찾습니까? 사실은 비교할 세그먼트를 찾아야한다는 의미입니다. 내가 그들을 비교하고 평행하지 않으면 나는 평행하지 않은 것으로 분류한다. 평행선이라면 평행선 구간을 찾아야합니다. 하나의 폴리선이 다른 하나를 시작하고 끝낼 수 있기 때문입니다.

Answer 1

먼저 모든 교차점을 거부하십시오.

그런 다음 선을 선형 회귀하십시오. "대략 병렬"에 대한 임계 값을 설정하십시오. 이제 하나의 폴리선을 선택하고 가장 잘 맞는 선에서 가장 먼 지점을 가져옵니다 (끝 점이 다음 점을 선택한 경우). 이제 "최상의 적합성"(다른 지역 편차를 허용하고 가능하다면 모서리 점을 잘라 내기 위해 약간의 경사가있는 거리)의 지점에서 다른 폴리 라인을 분할합니다.

선분이 폴리 라인이 될 때까지 반복하고 거리 및 방향 임계 값을 상당히 적용하십시오.

Answer 2

폴리 라인 A의 각 정점에 대해 폴리 라인 B에서 가장 가까운 점을 찾고이 두 점 사이의 거리를 출력합니다. 가장 가까운 버텍스를 대신 사용하는 것이 좋습니다.) A와 관련하여 B에 대해 동일한 작업을 수행하십시오.

이제 거리에 대해 선형 회귀를 수행하십시오. 대략 수평선이 있어야합니다. 이 검사에 대한 임계 값을 정의하십시오.

Answer 3

예를 들어 각 선분 쌍이 y 축 좌표를 공유하므로 인덱스가 인 것을 알 수 있습니다. 또한 선은 예제마다 연속적입니다.

각 끝점에서 두 줄 사이의 거리 (y 좌표)를 알고 있습니다. 그래서 : 당신의 라인

입니다 당신이 이 평행 방법에 비례 할 것이다이 곡선 아래의 음이 아닌 곡선, 지역이있을 것이다

for y in 0:n 
    delta_x[y] = abs(blue_x[y] - red_x[y]) 

은 당신은 그들 모두에서 가장 작은 delta_x [Y]를 뺄 경우

더 적은 평행 한 영역,
더 평행하지 않은 영역이 더 작음
완전히 평행 한 영역이 없습니다.

하지만 임계 값 만 선택할 수 있습니다.

Answer 4

이중 공간에서 문제를 볼 수 있습니다. 이미지 처리에 사용되는 Hough transform을 보았을 수 있습니다. 이것은 선을 점으로 매핑하고 점 집합을 이중 공간이라고합니다.

기본 아이디어는 숫자 쌍 (m, c)으로 직선 y = m x + c를 매개 변수화 할 수 있다는 것입니다. 각 폴리 라인의 각 세그먼트에 대해이 작업을 수행 할 수 있습니다. 이것들은 각 세그먼트에 대해 포인트 세트를 제공합니다. 이 점들은 (m1, c1)과 (m2, c2)를 중심으로 두 개의 클러스터를 형성해야합니다. 선이 평행 할 경우 m1 = m2가됩니다.

이것은 클러스터링 알고리즘 (k-means)을 필요로하기 때문에 컴퓨터 비전 툴킷을 필요로 할 수 있습니다. 선을 매개 변수화하려면 (m, c)를 사용하지 않으려합니다. 수직 선에서는 사용할 수 없기 때문입니다. 일부 알고리즘은 선의 각도와 점으로부터의 거리를 사용합니다.

폴리 라인의 부분에 선분을 맞춰보십시오. 선 세그먼트의 길이를 정의한 다음이 길이의 폴리선의 하위 세트를 찾을 수 있습니다.
이러한 하위 집합을 사용하면 선형 회귀라는 일부 라인 맞춤을 수행합니다. 이 맞춤 선을 사용하면 이중 매개 변수를 사용하여 맞춤 선을 비교할 수 있습니다. 우리가 듀얼 공간에서 선과 점을 생각하면

---

는

normal space <---> dual space 

line   <--->  point 
point   <--->  line 

그래서 모든 라인이 점에 해당하는 관계가 모든 점은 라인에 해당합니다.

우리가 듀얼 공간으로 폴리 라인을 매핑 할 경우 우리는이는 애큐 리트도 아니다

같은 것을 얻을 수 있습니다. 각 선분은 점이되고 각 점은 선이됩니다. 당신이 발견 할 수있는 것은 듀얼 스페이스가 적합 라인을 대표하는 이중 공간을 감싼다는 것입니다.