[algorithm] 겹치는 직사각형을 간격을 두는 알고리즘?

비슷한 것이 필요했기 때문에 이것에 대해 약간 작업했지만 알고리즘 개발을 지연 시켰습니다. 당신은 내가 약간의 충동을 얻도록 도와주었습니다 : D

소스 코드도 필요했기 때문에 여기에 있습니다. Mathematica에서 작업했지만 기능적 기능을 많이 사용하지 않았기 때문에 어떤 절차 언어로도 쉽게 번역 할 수있을 것 같습니다.

역사적인 관점

먼저 교차점을 계산하기 쉽기 때문에 원 알고리즘을 개발하기로 결정했습니다. 중심과 반경에 따라 다릅니다.

Mathematica 방정식 솔버를 사용할 수 있었고 성능도 훌륭했습니다.

그냥보세요 :

쉬웠 어. 다음 문제로 솔버를로드했습니다.

For each circle
 Solve[
  Find new coördinates for the circle
  Minimizing the distance to the geometric center of the image
  Taking in account that
      Distance between centers > R1+R2 *for all other circles
      Move the circle in a line between its center and the
                                         geometric center of the drawing
   ]

그렇게 간단하고 Mathematica가 모든 작업을 수행했습니다.

나는 “Ha! 쉽습니다. 이제 직사각형으로 가자!” 그러나 나는 틀렸다 …

직사각형 블루스

직사각형의 주요 문제는 교차로를 쿼리하는 것이 불쾌한 기능이라는 것입니다. 다음과 같은 것 :

그래서 방정식에 대한 이러한 많은 조건을 Mathematica에 공급하려고했을 때 성능이 너무 나빠서 절차적인 작업을하기로 결정했습니다.

내 알고리즘은 다음과 같이 끝났습니다.

Expand each rectangle size by a few points to get gaps in final configuration
While There are intersections
    sort list of rectangles by number of intersections
    push most intersected rectangle on stack, and remove it from list
// Now all remaining rectangles doesn't intersect each other
While stack not empty
    pop  rectangle from stack and re-insert it into list
    find the geometric center G of the chart (each time!)
    find the movement vector M (from G to rectangle center)
    move the rectangle incrementally in the direction of M (both sides)
                                                 until no intersections
Shrink the rectangles to its original size

“가장 작은 움직임”조건이 완전히 만족되지 않는다는 것을 알 수 있습니다 (한 방향으로 만). 하지만 사각형을 원하는 방향으로 움직이면 사용자에게 혼란스러운지도가 변경되는 경우가 있습니다.

사용자 인터페이스를 디자인 할 때 직사각형을 조금 더 이동하지만 더 예측 가능한 방식으로 이동합니다. 훨씬 더 까다로울 수 있지만 빈 장소가 발견 될 때까지 현재 위치를 둘러싼 모든 각도와 모든 반경을 검사하도록 알고리즘을 변경할 수 있습니다.

어쨌든 다음은 결과의 예입니다 (전 / 후).

편집> 여기에 더 많은 예

보시다시피 “최소 움직임”은 만족스럽지 않지만 결과는 충분합니다.

SVN 저장소에 문제가 있으므로 여기에 코드를 게시하겠습니다. 문제가 해결되면 제거하겠습니다.

편집하다:

R-Tree를 사용할 수도 있습니다.직사각형 교차점을 찾기 를 있지만 적은 수의 직사각형을 처리하는 것은 과잉으로 보입니다. 그리고 이미 구현 된 알고리즘이 없습니다. 다른 사람이 선택한 플랫폼의 기존 구현을 알려줄 수 있습니다.

경고! 코드는 첫 번째 접근 방식입니다. 아직 품질이 좋지는 않지만 확실히 버그가 있습니다.

Mathematica입니다.

(*Define some functions first*)

Clear["Global`*"];
rn[x_] := RandomReal[{0, x}];
rnR[x_] := RandomReal[{1, x}];
rndCol[] := RGBColor[rn[1], rn[1], rn[1]];

minX[l_, i_] := l[[i]][[1]][[1]]; (*just for easy reading*)
maxX[l_, i_] := l[[i]][[1]][[2]];
minY[l_, i_] := l[[i]][[2]][[1]];
maxY[l_, i_] := l[[i]][[2]][[2]];
color[l_, i_]:= l[[i]][[3]];

intersectsQ[l_, i_, j_] := (* l list, (i,j) indexes,
                              list={{x1,x2},{y1,y2}} *)
                           (*A rect does intesect with itself*)
          If[Max[minX[l, i], minX[l, j]] < Min[maxX[l, i], maxX[l, j]] &&
             Max[minY[l, i], minY[l, j]] < Min[maxY[l, i], maxY[l, j]],
                                                           True,False];

(* Number of Intersects for a Rectangle *)
(* With i as index*)
countIntersects[l_, i_] :=
          Count[Table[intersectsQ[l, i, j], {j, 1, Length[l]}], True]-1;

(*And With r as rectangle *)
countIntersectsR[l_, r_] := (
    Return[Count[Table[intersectsQ[Append[l, r], Length[l] + 1, j],
                       {j, 1, Length[l] + 1}], True] - 2];)

(* Get the maximum intersections for all rectangles*)
findMaxIntesections[l_] := Max[Table[countIntersects[l, i],
                                       {i, 1, Length[l]}]];

(* Get the rectangle center *)
rectCenter[l_, i_] := {1/2 (maxX[l, i] + minX[l, i] ),
                       1/2 (maxY[l, i] + minY[l, i] )};

(* Get the Geom center of the whole figure (list), to move aesthetically*)
geometryCenter[l_] :=  (* returs {x,y} *)
                      Mean[Table[rectCenter[l, i], {i, Length[l]}]];

(* Increment or decr. size of all rects by a bit (put/remove borders)*)
changeSize[l_, incr_] :=
                 Table[{{minX[l, i] - incr, maxX[l, i] + incr},
                        {minY[l, i] - incr, maxY[l, i] + incr},
                        color[l, i]},
                        {i, Length[l]}];

sortListByIntersections[l_] := (* Order list by most intersecting Rects*)
        Module[{a, b},
               a = MapIndexed[{countIntersectsR[l, #1], #2} &, l];
               b = SortBy[a, -#[[1]] &];
               Return[Table[l[[b[[i]][[2]][[1]]]], {i, Length[b]}]];
        ];

(* Utility Functions*)
deb[x_] := (Print["--------"]; Print[x]; Print["---------"];)(* for debug *)
tableForPlot[l_] := (*for plotting*)
                Table[{color[l, i], Rectangle[{minX[l, i], minY[l, i]},
                {maxX[l, i], maxY[l, i]}]}, {i, Length[l]}];

genList[nonOverlap_, Overlap_] :=    (* Generate initial lists of rects*)
      Module[{alist, blist, a, b},
          (alist = (* Generate non overlapping - Tabuloid *)
                Table[{{Mod[i, 3], Mod[i, 3] + .8},
                       {Mod[i, 4], Mod[i, 4] + .8},
                       rndCol[]}, {i, nonOverlap}];
           blist = (* Random overlapping *)
                Table[{{a = rnR[3], a + rnR[2]}, {b = rnR[3], b + rnR[2]},
                      rndCol[]}, {Overlap}];
           Return[Join[alist, blist] (* Join both *)];)
      ];

본관

clist = genList[6, 4]; (* Generate a mix fixed & random set *)

incr = 0.05; (* may be some heuristics needed to determine best increment*)

clist = changeSize[clist,incr]; (* expand rects so that borders does not
                                                         touch each other*)

(* Now remove all intercepting rectangles until no more intersections *)

workList = {}; (* the stack*)

While[findMaxIntesections[clist] > 0,
                                      (*Iterate until no intersections *)
    clist    = sortListByIntersections[clist];
                                      (*Put the most intersected first*)
    PrependTo[workList, First[clist]];
                                      (* Push workList with intersected *)
    clist    = Delete[clist, 1];      (* and Drop it from clist *)
];

(* There are no intersections now, lets pop the stack*)

While [workList != {},

    PrependTo[clist, First[workList]];
                                 (*Push first element in front of clist*)
    workList = Delete[workList, 1];
                                 (* and Drop it from worklist *)

    toMoveIndex = 1;
                                 (*Will move the most intersected Rect*)
    g = geometryCenter[clist];
                                 (*so the geom. perception is preserved*)
    vectorToMove = rectCenter[clist, toMoveIndex] - g;
    If [Norm[vectorToMove] < 0.01, vectorToMove = {1,1}]; (*just in case*)
    vectorToMove = vectorToMove/Norm[vectorToMove];
                                            (*to manage step size wisely*)

    (*Now iterate finding minimum move first one way, then the other*)

    i = 1; (*movement quantity*)

    While[countIntersects[clist, toMoveIndex] != 0,
                                           (*If the Rect still intersects*)
                                           (*move it alternating ways (-1)^n *)

      clist[[toMoveIndex]][[1]] += (-1)^i i incr vectorToMove[[1]];(*X coords*)
      clist[[toMoveIndex]][[2]] += (-1)^i i incr vectorToMove[[2]];(*Y coords*)

            i++;
    ];
];
clist = changeSize[clist, -incr](* restore original sizes*);

HTH!

편집 : 다중 각도 검색

모든 방향으로 검색 할 수 있도록 알고리즘을 변경했지만 기하학적 대칭에 의해 부과 된 축을 선호했습니다.
더 많은 사이클을 희생시키면서 아래에서 볼 수 있듯이 최종 구성이 더 간결 해졌습니다.

여기에 더 많은 샘플이 있습니다 .

메인 루프의 의사 코드가 다음과 같이 변경되었습니다.

Expand each rectangle size by a few points to get gaps in final configuration
While There are intersections
    sort list of rectangles by number of intersections
    push most intersected rectangle on stack, and remove it from list
// Now all remaining rectangles doesn't intersect each other
While stack not empty
    find the geometric center G of the chart (each time!)
    find the PREFERRED movement vector M (from G to rectangle center)
    pop  rectangle from stack
    With the rectangle
         While there are intersections (list+rectangle)
              For increasing movement modulus
                 For increasing angle (0, Pi/4)
                    rotate vector M expanding the angle alongside M
                    (* angle, -angle, Pi + angle, Pi-angle*)
                    re-position the rectangle accorging to M
    Re-insert modified vector into list
Shrink the rectangles to its original size

간결함을 위해 소스 코드를 포함하지 않았지만 사용할 수 있다고 생각되면 요청하십시오. 이런 식으로 가면 R- 트리로 전환하는 것이 더 낫다고 생각합니다 (여기에 많은 간격 테스트가 필요합니다).