저는 비교적 단순한 해결책이 있어야한다고 생각하는 계산 기하학 문제가 있습니다. 그러나 나는 그것을 이해할 수 없습니다.선분 집합의 볼록하지 않은 선체를 결정하십시오.
여러 선분으로 정의 된 영역의 비 볼록 윤곽을 결정해야합니다.
다양한 비 convex 선체 알고리즘 (예 : 알파 셰이프)을 알고 있지만 대부분의 경우 선분이 고유 한 솔루션을 정의하기 때문에 완전히 일반적인 알고리즘이 필요하지 않습니다.
@ Jean-FrançoisCorbett이 지적한 바와 같이, 여러 가지 해결책이있는 경우가 있습니다. 나는 분명히 내 정의에 대해 더 생각할 필요가있다.
그러나 내가하려는 것은 리버스 엔지니어링이며 독점적 인 파일 형식을 사용하므로 자신과 다른 사람이 수집 한 데이터에 대한 기본 분석을 실행할 수 있습니다. 파일 형식은 간단하지만 경계를 정의하는 알고리즘을 결정하는 것은 상당히 어렵습니다.
고유하지 않은 솔루션으로 이어질 수있는 많은 경우를두면 문제의 소프트웨어가 경고없이 충돌하거나 자동으로 파일을 읽지 못하게됩니다.
따라서 여러 솔루션이있는 경우 수용 가능한 솔루션 중 하나를 생성하거나 여러 솔루션이 있다고 판단 할 수 있습니다.
문제 정의 :
는다각형의 윤곽은 세그먼트의 교차해서는 안 및 세그먼트 '모든 엔드 포인트에 합류 라인을 형성한다. 모든 세그먼트는 다각형의 경계 내부 또는 경계를 따라 위치해야합니다. 윤곽선에서 끝점을 두 번 이상 사용할 수 없습니다 (다각형을 닫아야하는 소프트웨어 라이브러리의 끝에 첫 번째 점을 추가하여 다각형을 "닫음"무시).
이 기준을 충족하는 솔루션이 여러 개인 경우 해당 솔루션 중 하나를 사용해도됩니다. (그것은 솔루션은 고유하지 않은시기를 결정 할 수 있도록 좋은 것입니다, 그러나 이것은 엄격하게 필요하지 않습니다.)
예 : 예를 들어
, 나는이 라인을 따라 뭔가를 : 
그리고 나는 다음과 같은 영역의 윤곽을 싶습니다 
또한 교차하지 않는 세그먼트에 대한 작동합니다. 예 : 
나는 생각 (?) 기준 개요 이전에 따라 각각의 경우에 고유 한 솔루션이있다. (편집 : @ Jean-FrançoisCorbett이 지적했듯이 일반적으로 유일한 해결책은 없습니다. 그러나 여전히 받아 들일 수있는 솔루션 중 하나를 생성하는 알고리즘에 관심이 있습니다.)
테스트 케이스
테스트 케이스를 들어, 여기에 위의 수치를 생성하는 코드입니다. 저는 여기 파이썬을 사용하고 있습니다,하지만 질문은 언어에 구애받지 않습니다.
import matplotlib.pyplot as plt
def main():
test1()
test2()
plt.show()
def test1():
"""Intersecting segments."""
segments = [[(1, 1), (1, 3)],
[(3.7, 1), (2, 4)],
[(2, 0), (3.7, 3)],
[(4, 0), (4, 4)],
[(4.3, 1), (4.3, 3)],
[(0, 2), (6, 3)]]
desired_outline = [segments[0][0], segments[5][0], segments[0][1],
segments[1][1], segments[2][1], segments[3][1],
segments[4][1], segments[5][1], segments[4][0],
segments[3][0], segments[1][0], segments[2][0],
segments[0][0]]
plot(segments, desired_outline)
def test2():
"""Non-intersecting segments."""
segments = [[(0, 1), (0, 3)],
[(1, 0), (1, 4)],
[(2, 1), (2, 3)],
[(3, 0), (3, 4)]]
desired_outline = [segments[0][0], segments[0][1], segments[1][1],
segments[2][1], segments[3][1], segments[3][0],
segments[2][0], segments[1][0], segments[0][0]]
plot(segments, desired_outline)
def plot(segments, desired_outline):
fig, ax = plt.subplots()
plot_segments(ax, segments)
ax.set_title('Segments')
fig, ax = plt.subplots()
ax.fill(*zip(*desired_outline), facecolor='gray')
plot_segments(ax, segments)
ax.set_title('Desired Outline')
def plot_segments(ax, segments):
for segment in segments:
ax.plot(*zip(*segment), marker='o', linestyle='-')
xmin, xmax, ymin, ymax = ax.axis()
ax.axis([xmin - 0.5, xmax + 0.5, ymin - 0.5, ymax + 0.5])
if __name__ == '__main__':
main()
아이디어가 있으십니까?
내가 재현하려는 소프트웨어가 "내부"좌표계 (예 : x-prime 및 y-prime이있는 좌표계)에서 방사형 스윕 알고리즘을 사용한다고 의심되기 시작했습니다. 포인트의 확산에 의해 정의 된 주축. 이것은 문제를보다 "원형"으로 만든다.) 그러나, 많은 경우 아웃 라인이 선분과 교차하는 솔루션을 생성한다. 이것을 감지하고 거기에서 무차별 대입하는 것은 쉽지만 확실하게 더 좋은 방법이 있습니까?
"막대가 고유하게 솔루션을 정의합니다"라고 말하면 막대가 모두 최종 다각형 안에 있어야한다는 의미입니까? –
예! 정보에 그 정보를 추가해야했습니다. 감사! –
Mark de Berg와 CGAL 라이브러리 "Computational Geometry"책보기 효율적인 알고리즘을 찾을 수있을 것입니다. – mitch