2 차원 기하학 푸시 알고리즘

Question

나는 직사각형 보드를 가지고 있으며 그 안에 직사각형, 다각형 및 원호/선 가장자리가있는 단순한 모양과 같은 더 복잡한 형상과 같은 일부 분리 된 2D 모양이 있습니다. 일반적으로 크기는 작지만 일부 모양의 경우 회전 또는 번역 할 수 있습니다. 주어진 방향에 따라 하나의 지오메트리를 이동하면 인접한 지오메트리도 이동하거나 회전해야합니다. 첫 번째 지오메트리가 두 번째 지오메트리를 푸시하는 것처럼 보입니다. 두 x 째 기하학은 다른 두 기하학을 밀어 낼 수 있습니다. 마지막으로, 우리는 또 다른 안정된 국가를 성취 할 수도 있고, 추진할 여지가 없다.

기존 조사가 있습니까? 우선, 볼록 및 비 볼록의 단순한 다각형에 집중하겠습니다. 푸시는 어떤 방향이 될 수도 있습니다. example image

일부 조사를하고 있지만이 주제에 대한 기존 논문을 찾을 수 없습니다. 역학이나 역학을 통해 시뮬레이션 할 수 있습니까? 아니면 순수한 기하학 알고리즘?

종이 검색을위한 몇 가지 키워드는 매우 유용합니다.

EDA의 자동 푸시 개념과 비슷합니다. 사용자는 회로의 한 요소 (핀/와이어)를 이동할 수 있으며, 그러면 소프트웨어가 자동으로 인접 요소를 밀어서 토폴로지가 유지되고 설계 규칙을 충족시킵니다.

적어도 움직이는 방향을 계산하기 위해 역학에서 몇 가지 개념을 사용할 수 있다고 생각합니다. 다각형 A와 다각형 B의 연결된 부분이 점인 경우 A를 한 방향으로 밀면 B를 따라 힘이 생성됩니다 법선 방향. 그러나 그 힘은 움직일 수 없다. 얼마나 많은 부분을 움직일 수 있는지 확인하기 위해 모든 부분을 반복하거나 경계에 도달해야합니다. 먼저 회전을 무시합시다.

Answer 1

댓글에 대한 평판이 충분하지 않아 답변을 게시합니다. 문제를 오해하지 않으면 기하학적으로 충돌 감지 문제로 들립니다. 지오메트리에 변형 (회전, 회전)을 적용하고이 새 위치가 다른 지오메트리와 겹치는 지 확인해야합니다. 이 경우 두 번째 변환에 다른 변환을 적용해야합니다. 충돌 감지는 게임과 시뮬레이션에서 큰 주제입니다.