한 대학생이 Convex Hull 알고리즘 공부하다가 만든 프로그램

아오바·2025년 12월 23일

자잘한 토이 프로젝트 도서관

목록 보기
1/1
post-thumbnail

시작은 별 거 아니었다

2학년 2학기를 다니고 있는 대학생인 나는, 이번 학기에 들은 컴퓨터 그래픽스 과목의 OpenGL을 썩히고 싶지 않았다. 마침 종강도 했겠다, 가만히 놀지 말고 뭐라도 해볼까 싶긴 했지만 뭘 해야 할까 고민도 되고 막상 하려니까 아무 생각도 안 들었다. 그래서 백준을 풀고 있었는데, 그때 Convex Hull과 관련된 문제가 보였다. 분명 그래픽스에서도 다뤘던 것 같은데 하고 생각해보니, 마음만 먹으면 이걸 시각화할 수 있는 프로그램 정도는 만들 수 있지 않을까? 하는 생각이 들었다. 해당 문제의 링크 는 여기를 눌러 확인할 수 있다.

대략적인 인터페이스 구상

어쩌다 보니 모바일 모양처럼 되긴 했는데, 저걸 모두 구현하는 건 천천히 진행하더라도 일단 중요한 건,

  1. 점을 사용자가 임의대로 화면에 찍을 수 있게 하자.
  2. 해당 점들에 대하여 버튼을 클릭하면 Convex Hull 알고리즘으로 구현된 결과를 볼 수 있게 하자.
  3. 일괄적으로 지우거나 할 수 있는 버튼도 만들자.
  4. 사용자가 지정한 점 개수와 시드 번호를 통하여 랜덤하게 생성할 수 있게 하자.
  5. txt나 csv 등의 파일로 파일 입출력을 지원할 수 있게 하자.

이 정도는 무조건 구현해보자는 생각이 들었다.

그렇게 만들어진 결과


생각보다 마음에 드는 결과가 나왔다. 위쪽의 Import/Export 버튼을 활용하여 .csv 파일로 내보내기도 가능하고, 오른쪽 상단에서 시드 값과 점의 개수 역시 지정할 수 있다. 화면에서는 점을 사용자가 임의대로 찍을 수 있고, 아래의 Get Convex Hull 버튼을 통하여 결과를 확인할 수 있다. Erase All 버튼으로 전부 지울 수도 있다.


위 csv 파일의 값처럼 저장되는데, x축과 y축을 각각 픽셀 개수로 지정하였다. -1부터 1까지의 normalized coordinate를 사용할 수도 있었지만, 사용자의 입력을 받기 위해서는 생각보다 정규화 좌표계를 쓰는 것은 소수점이 길어지거나 근사값으로 입력해야 하기 때문에 원하는 결과를 보기 어려울 거라는 생각이 들어 픽셀을 선택하게 되었다.

만들면서 생각한 것들

#1 OpenGL Shading Language와 OpenGL

OpenGL을 다루면서 사실 HLSL 코드를 그렇게 잘 아는 것도 아니고, 이런저런 자료들을 인터넷에서 찾으려면 낮은 버전을 활용할 수도 있었겠지만 그래픽스 강의를 들으면서 배운 것은 #version 410 core로 시작하는 OpenGL Shading Language였기 때문에 그걸 활용해보기로 결정했다.

#version 410 core
layout (location = 0) in vec2 aPos;
void main() {
	gl_Position = vec4(aPos.x, aPos.y, 0.0, 1.0)
}

데이터를 버퍼와 VAO(Vertex Array Object)를 기반으로 관리해야 하기 때문에 셰이더 코드를 다음과 같이 작성하였고, 파일 입출력 시에는 사용자 친화를 위해 픽셀 좌표를 활용하여 렌더링 직전에 다시 변환하는 방식을 택하였다.

inline void exportPoints(const std::string& filename, const std::vector<Point>& points, float width, float height) {
    std::ofstream outFile(filename);
    if (outFile.is_open()) {
        for (const auto& p : points) {
            float px = (p.x + 1.f) * (width / 2.0f);
            float py = (1.f - p.y) * (height / 2.0f);
            outFile << px << ',' << py << "\n";
        }
        outFile.close();
        std::cout << "Points exported to " << filename << std::endl;
    }                                                              
    else {
        std::cerr << "Failed to open file for export: " << filename << std::endl;
    }
}

위 코드는 특히 export 과정을 다루는데, 잘 보면 normalized coordinate로 옮겨지기 전의 상태와 아닌 상태를 구분하기 위하여 계산 과정을 걸치는 것을 볼 수 있다. 이렇게 하게 된다면 픽셀 좌표는 음수나 실수 형태를 만들지 않아도 되기 때문에 사용자가 메모장으로 csv 파일을 직접 열어서 좌표를 수정하는 것도 어렵지 않게 된다.

#2 Convex Hull 알고리즘

이 프로그램의 핵심 로직인데, 여러 알고리즘 중에서 가장 직관적이고 효율적으로 볼 수 있다고 생각하는 Graham Scan 알고리즘을 활용하였다. 가장 중요한 포인트는 세 점에 대한 방향성, 즉 CCW(Counter-ClockWise)를 판별하는 것이다. convexhull.h 파일에 별도로 이 부분들이 관리되어 있다.

inline float counterClockWise(Point a, Point b, Point c) {
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline float distSquared(Point p1, Point p2) {
	return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

inline bool compare(Point a, Point b) {
	float order = counterClockWise(pivot, a, b);
	if (order == 0) return distSquared(pivot, a) < distSquared(pivot, b);
	return order > 0;
}

점을 발견하여 기준점을 잡고 각도 순서로 정렬한 뒤, 스택 구조를 활용하여 정확한 상황을 혹인한 뒤 외곽선으로 인정하게 되는 과정인데, 이것을 실질적으로 시각화하기 위한 것이 이번 프로그램을 만들게 된 목적이었기 때문에 일직선상에 놓이는 점의 예외 케이스 처리를 위하여 거리 계산이 추가되는 등 생각보다 시각화에서는 디테일한 예외 처리도 필수적인 요소였다.

#3 인터페이스 제작을 위한 ImGui

기본 시안으로서 프로토타입 인터페이스를 대략 잡고, 그걸 구현하는 과정에서 ImGui라는 것을 알게 되었다. imgui(dear imgui)는 게임 엔진의 개발 등에도 널리 쓰이는 immediate mode gui 라이브러리인데, 어플리케이션의 디버그 인터페이스나 개발 도구 및 실험적인 UI를 빠르게 추가하는 데 사용하며 특히 게임 개발이나 그래픽 프로그래밍 같은 실시간 어플리케이션의 개발에서 많이 사용한다고 한다. Win32 API나 다른 UI 라이브러리보다 훨씬 가볍게 OpenGL에 얹을 수 있기에 사용하기에 훨씬 좋았다고 생각한다.

    IMGUI_CHECKVERSION();
    CreateContext();
    ImGuiIO& io = GetIO();

    io.Fonts->AddFontDefault();
    io.FontGlobalScale = 1.5f;

    ImGui_ImplGlfw_InitForOpenGL(window, true);
    ImGui_ImplOpenGL3_Init("#version 410");

    StyleColorsDark();
    ImGuiStyle& style = GetStyle();
    
    style.WindowRounding = 5.0f;
    style.FrameRounding = 5.0f;
    style.Colors[ImGuiCol_Button] = ImVec4(0.2f, 0.2f, 0.2f, 1.0f);
    style.Colors[ImGuiCol_ButtonHovered] = ImVec4(0.3f, 0.3f, 0.3f, 1.0f);

메인 파트에서 초기화와 함께 기본 설정을 하는 부분인데, 생각보다 직관적으로 사용할 수 있는 경우가 많았고 그럼에도 확실한 기반을 만들 수 있다는 것이 굉장히 편리한 것 같다.

    Begin("TopBar", nullptr, ImGuiWindowFlags_NoTitleBar | ImGuiWindowFlags_NoResize | ImGuiWindowFlags_NoMove | ImGuiWindowFlags_NoScrollbar);
    Text("Convex Hull Tool with OpenGL 4.1 Core");

    SameLine(600);
    if (Button("Import with .csv", ImVec2(180, 25)))
        importPoints("points.csv", userPoints, hullPoints, screenW, screenH);
    SameLine();
    if (Button("Export with .csv", ImVec2(180, 25)))
        exportPoints("points.csv", userPoints, screenW, screenH);

    SameLine(screenW - 150);
    TextDisabled("%zu Points", userPoints.size());
    End();

특히 Begin()과 End() 안쪽에 상세한 것을 설정하는 방식은 왜인지는 모르겠지만 양쪽의 bracket 안에 파트를 나눠 인터페이스를 제작하는 방식의 HTML 역시 생각나게 하는 것 같았다. 그래서인지 조금 더 직관적으로 어떤 방식으로 코드를 짜면 될 지 생각하기 좋았다.

#4 C++과 모듈화

프로젝트의 구조적인 완성도를 위하여 모듈화를 확실히 했는데, 모든 코드를 main.cpp에 때려박을 수도 있었지만 일단 하면서 내 스스로부터가 뭔가 정리하기도 영 애매해지는 걸 느꼈고, 기능의 추가를 이렇게 번거롭게 한 코드 내에서 #include문 넣고, 아래로 내려가서 함수 만들고, 뭐 하고... 하는 그런 과정은 영 마음에 들지 않았다. 그래서 역할별로 헤더 파일을 분리해 구획화하였다.

  • myshader.h는 셰이더를 컴파일하고 프로그램을 로드하는 것을 관리하는 헤더 파일이다.
  • convexhull.h는 순수 수학적 알고리즘 로직을 분리하여 convex hull 알고리즘을 조금 더 직관적으로 구현하기 위하여 만든 헤더 파일이다.
  • fileio.h는 파일 시스템에 접근하여 데이터를 읽거나 써서 내보내는 변환을 거치는 헤더 파일이다.

이런 방식을 채택한다면 이후에 새로운 기능을 만들거나 추가해보더라도 더 쉽게 디벨롭이 가능할 것 같다.

더 해보려고 하는 것

  • 특정 점을 기준점으로 잡아 그 기준점에서 convex hull을 뻗어나가는 방식을 애니메이션으로 보여주는 것은 어떨까?
  • 일정 범위에 대해서 주어진 (가령, -10에서 10 사이) 좌표들에 대해서 자체적으로 스케일을 조절하여 시각화해주는 건 어떨까?
  • 인터페이스 내에서 선 색 조절, 점 크기 조절 등 조금 더 사용자 친화적인 인터페이스를 만들 수 있지 않을까?
  • 사용자의 마우스 커서가 특정 점에 가까워지면, 그 점에 대한 좌표 정보나 convex hull 포함 여부 등의 정보를 제공하는 작은 창을 띄우는 건 어떨까?

링크

깃허브의 아래 링크에서 프로그램을 직접 확인해볼 수 있다!
👉 Convex Hull 구해주는 프로그램 (깃헙/Github)

profile
아오바
느긋하게 개발하며 앞으로 나아가는 대학생 / 팀 프로젝트, 포스팅 관련 질문 등은 이메일 혹은 댓글로 얼마든지 부담 없이 연락 주셔도 됩니다.

0개의 댓글