■ 포인트 리스트를 둘러싸는 외곽선(Convex Hull)을 구하는 방법을 보여준다.
▶ 예제 코드 (PY)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
def getOrientation(pointTuple1, pointTuple2, pointTuple3): value = (pointTuple2[1] - pointTuple1[1]) * (pointTuple3[0] - pointTuple2[0]) - (pointTuple2[0] - pointTuple1[0]) * (pointTuple3[1] - pointTuple2[1]) if value == 0: return 0 # 일직선 상에 위치한 경우 elif value > 0: return 1 # 반시계 방향인 경우 else: return 2 # 시계 방향인 경우 def getConvexHullPointTupleList(sourcePointTupleList): sourcePointTupleListLength = len(sourcePointTupleList) if sourcePointTupleListLength < 3: return None convexHullPointTupleList = [] mostLeftIndex = 0 for pointIndex2 in range(1, sourcePointTupleListLength): if sourcePointTupleList[pointIndex2][0] < sourcePointTupleList[mostLeftIndex][0]: mostLeftIndex = pointIndex2 elif sourcePointTupleList[pointIndex2][0] == sourcePointTupleList[mostLeftIndex][0] and sourcePointTupleList[pointIndex2][1] < sourcePointTupleList[mostLeftIndex][1]: mostLeftIndex = pointIndex2 pointIndex1 = mostLeftIndex pointIndex3 = None while True: convexHullPointTupleList.append(sourcePointTupleList[pointIndex1]) pointIndex3 = (pointIndex1 + 1) % sourcePointTupleListLength for pointIndex2 in range(sourcePointTupleListLength): if getOrientation(sourcePointTupleList[pointIndex1], sourcePointTupleList[pointIndex2], sourcePointTupleList[pointIndex3]) == 2: pointIndex3 = pointIndex2 pointIndex1 = pointIndex3 if pointIndex1 == mostLeftIndex: break return convexHullPointTupleList sourcePointTupleList = [(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)] convexHullPointTupleList = getConvexHullPointTupleList(sourcePointTupleList) print(convexHullPointTupleList) # [(0, 0), (3, 1), (4, 4), (0, 3)] |