제안 된 포인트 인 폴리곤 알고리즘은 시계 반대 방향으로 만 작동합니다

Question

here 및 here으로 설명한 알고리즘을 테스트하고 나면 아래 주석과 같이 흥분했습니다.

그러나 내 테스트 케이스가 실패한 후 디버깅 및 추적이 많이 발생하여 정상적으로 작동 할 수있는 조건이 있다는 것을 깨달았습니다.

이 알고리즘은 다각형 List<Point>의 '점을 반 시계 방향으로 정렬해야합니다. 그렇지 않으면 출력이 올바르지 않습니다. 시계 반대 방향으로 정렬 된 포인트 :

다각형 (당신은 플롯 및 테스트 할 this을 사용할 수 있습니다) :

이 내 주장을 확인하는 아주 간단한 테스트 케이스이다.

inputPoints.Add(new Point(1, 3)); 
inputPoints.Add(new Point(2, 1)); 
inputPoints.Add(new Point(6, 2)); 
inputPoints.Add(new Point(3, 6)); 

테스트 포인트 :

Point testP1 = new Point(3, 3); //inside, algorithm output :correct 
Point testP2 = new Point(6, 3); //outside, algorithm output :correct 
Point testP3 = new Point(9, 9); //outside, algorithm output :correct 

다각형 : 시계 방향으로 정렬 포인트.

inputPoints.Add(new Point(1, 3)); 
inputPoints.Add(new Point(2, 1)); 
inputPoints.Add(new Point(6, 2)); 
inputPoints.Add(new Point(3, 6)); 

테스트 포인트 :

Point testP1 = new Point(3, 3); //inside, algorithm output :correct 
Point testP2 = new Point(6, 3); //outside, algorithm output :wrong answer 
Point testP3 = new Point(9, 9); //outside, algorithm output :correct 

다각형 : 임의의 순서 포인트 (그들은 단지 4 점을,하지만 크기를 조절할 때, 잘못도됩니다).

inputPoints.Add(new Point(2, 1)); 
inputPoints.Add(new Point(6, 2)); 
inputPoints.Add(new Point(1, 3)); 
inputPoints.Add(new Point(3, 6)); 

테스트 포인트 :

Point testP1 = new Point(3, 3); //inside, algorithm output :wrong answer 
Point testP2 = new Point(6, 3); //outside, algorithm output :correct 
Point testP3 = new Point(9, 9); //outside, algorithm output :correct 

Answer 1

이 내 자신의 경험에서 다각형 알고리즘의 형상과 포인트 꽤 표준 개념입니다.

예를 들어 SQL Server Spatial 라이브러리에도 가져온 GEOMETRY가 해당 기능을 사용하기 위해 올바르게 배치되도록하는 기능이 있습니다.

SQL 서버 공간 ReorientObject(geography) 방법 : https://msdn.microsoft.com/en-us/library/ff929311.aspx