그리기

이 같은, (나는 C# 및 그래픽을 사용하고) 내가 100 점을 가지고 있고 closedcurve을 그리려는 말을 교차하지 않도록 라인을 포인트를 기준으로 모양의 점들과 선들이 교차함에 따라 점들이 - 당신은 이것으로 단단한 모습을 얻지 못할 것입니다.그리기

견고한 그림을 얻기 위해 포인트를 던지는 데 도움이되는 알고리즘이 있습니까? 아래 그림은 내가 원하는 것을 시각화하는 데 도움이되는 (hehe만큼 열심히 노력한) 그림입니다.

enter image description here

2011-11-27 abolotnov

예를 들어, 교차없는 초승달 모양의 경우 어떻게해야합니까? – Per

동일한 질문의 문구를 다시 말하자면 - 내가 포인트 배열을 가지고 있다면 어떻게 순서대로 연결하면 하나의 솔리드 모양 (선이 교차하지 않음)으로 끝나는 방식으로 "토스 (toss)"합니까? – abolotnov

@Per, 아무 것도 아니고 다른 어떤 것과 마찬가지로 정상적인 모양입니다. – abolotnov

음, O에 별 모양의 다각형을 떠나, 당신은 점의 중심을 계산하고 그 중심에 대한 각의 순서로 정렬 할 수있는 시간 (N 로그 n). 그것은 효율적이지만 당신의 포인트의 순서를 너무 많이 망칠 것입니다.

TSP (설명 here)에 대한 2-OPT 방법의 결과가 더 좋을 것 같습니다. 2-OPT는 실제로 최악의 지수 지수이지만 다항식 시간입니다.

2011-11-27 19:00:59 Per

답변