반응형

다각형 내부/외부 판별

 

 

어떤 다각형에 대해 주어진 점이 다각형 내부에 있는지 외부에 있는지 판별하는 것을 다각형의 내부 외부 판별이라고 한다.

 

이때 왼쪽의 그림은 초록색 점이 다각형 내부에 있음을 알 수 있고, 오른족 그림은 외부에 있음을 알 수 있다.

이는 사람의 눈으로 보기에는 쉽게 알 수 있지만, 어떻게 컴퓨터로 알 수 있을지 생각해보아야한다.

 

 

Point in polygon 알고리즘

 

2차원 좌표 내에 다각형이 존재할 때 특정 좌표가 다각형 내부에 있는지 외부에 있는지 판별해주는 알고리즘이다.

 

우선 다각형 내에 좌표가 존재하는지 확인하는 방법은

 

해당 점의 왼쪽으로 반직선을 그었을 때(혹은 오른쪽으로 반직선을 그었을 때) 다각형과 마주치는 부분이

홀수개이면 다각형 내부에 존재하는 것이고 짝수개이면 다각형 외부에 존재하는 것이다.

 

 

 

첫번째 그림을 보자.

빨간점은 왼쪽으로 5개의 선분과 만나고, 오른쪽으로 3개의 선분과 만나니 이는 다각형 내에 존재하는 것이다.

 

두번째 그림을 보자.

왼쪽, 오른쪽으로 각각 2개씩 만나기에 이는 다각형 내에 존재하지 않는 좌표이다.

 

마지막 그림을 보면 왼쪽, 오른쪽에 각각 1개씩이기에 홀수이므로 다각형 내의 좌표이다.

 

 

아래에 다각형을 판별하는 좋은 내용이 담겨있고 코드도 수록되어있다.

 

참고로 아래 사이트에서 알려주는 알고리즘을 이용하게 되면

 

- 시계 방향, 반시계 방향으로 구성된 폴리곤 모두 적용 할 수 있다.

- 이미 if문에서 예외처리(0으로 나누는 것)을 막아두었기에 안전하다.

 

http://alienryderflex.com/polygon/

 

Determining Whether A Point Is Inside A Complex Polygon

//  Globals which should be set before calling these functions: // //  int    polyCorners  =  how many corners the polygon has (no repeats) //  float  polyX[]      =  horizontal coordinates of corners //  float  polyY[]      =  vertical coordinates of corn

alienryderflex.com

 

 

Point in polygon algorithm code

class Polygon {	
	private ArrayList<PointF> mPointList = new ArrayList<PointF>();
	
	public void addPoint(float x, float y) {
		mPointList.add(new PointF(x, y));
	}

	public boolean isPointInPolygon(float x, float y) {
		int size = mPointList.size();
		
		// 점이 3개 이하로 이루어진 polygon은 없다.
		if (size < 3) {
			return false;
		}
		
		int prev = size- 1;
		boolean isInnerPoint = false;

		// Point in polygon algorithm
		for (int cur = 0; cur < size; cur++) {
			PointF curPoint = mPointList.get(cur);
			PointF prevPoint = mPointList.get(followIndex);
			
			/*
			 * y - y1 = M * (x - x1)
			 * M = (y2 - y1) / (x2 - x1)
			 */
			if (curPoint.y < y && prevPoint.y >= y || prevPoint.y < y && curPoint.y >= y) {
				if (curPoint.x + (y - curPoint.y) / (prevPoint.y - curPoint.y) * (prevPoint.x - curPoint.x) < x) {
					isInnerPoint = !isInnerPoint;
				}
			}

			followIndex = cur;
		}

		return isInnerPoint;
	}
}

 

 

이때 c로는 진행해보지 않아 정확히 모르지만,

안드로이드에서 해당 알고리즘을 이용하기 위해서는 Point가 아닌 PointF를 사용해야만 한다.

 

그 이유는 Point를 이용하면 앱에서 보여지는 터치 좌표계의 오차가 심해져 polygon에서

내부/외부 판별을 제대로 하지 못하는 경우가 발생한다.

반응형