GIS Developer, 공간정보시스템 개발 블로그 -
   GIS Developer, 공간정보시스템 개발 블로그  
Front Page
Notice | E-Mail | Admin | Write Article   
 
2016/05/23 22:53 2016/05/23 22:53
Convex-Hull 알고리즘 구현

Convex Hull은 볼록한 껍데기로.. 무수히 많은 포인트를 감싸는 볼록한 영역으로 정의할 수 있습니다. 입력 데이터인 포인트는 SHP 파일로부터 제공받아, 이를 듀라맵에서 그 결과를 표시하도록 하였습니다. 아래는 그 결과 화면입니다.

무수히 많은 작은 포인트를 감싸는 Convex Hull이 반투명한 빨간색 폴리곤으로 표시되어져 있습니다. 이러한 Convex-Hull에 대한 구현에 대해 C# 클래스로 정의했으며 아래와 같습니다.

using System;
using System.Collections.Generic;

namespace tstConvexHull
{
    public class ConvexHull
    {
        public class Point : IComparer<Point>
        {
            public double x;
            public double y;

            public Point()
            {
                x = 0.0;
                y = 0.0;
            }

            public Point(double x, double y)
            {
                this.x = x;
                this.y = y;
            }

            public int Compare(Point p1, Point p2)
            {
                if (p1.x == p2.x)
                {
                    return p1.y > p2.y ? 1 : p1.y < p2.y ? -1 : 0;
                }
                else
                {
                    return p1.x > p2.x ? 1 : p1.x < p2.x ? -1 : 0;
                }
            }
        }

        public static double Cross(Point O, Point A, Point B)
        {
            return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
        }

        public static Point[] Get(Point[] P)
        {
            if (P.Length > 1)
            {
                int n = P.Length, k = 0;
                Point[] H = new Point[2 * n];

                Array.Sort(P, new Point());

                for (int i = 0; i < n; ++i)
                {
                    while (k >= 2 && Cross(H[k - 2], H[k - 1], P[i]) <= 0)
                        k--;
                    H[k++] = P[i];
                }

                for (int i = n - 2, t = k + 1; i >= 0; i--)
                {
                    while (k >= t && Cross(H[k - 2], H[k - 1], P[i]) <= 0)
                        k--;
                    H[k++] = P[i];
                }

                if (k > 1)
                {
                    Point[] NewH = new Point[k - 1];
                    Array.Copy(H, NewH, k - 1);
                    H = NewH;
                }
                return H;
            }
            else if (P.Length <= 1)
            {
                return P;
            }
            else
            {
                return null;
            }
        }
    }
}

실제 위의 Convex-Hull 클래스에 대한 사용은 아래 코드와 같은데요. DuraMap-Xr에서 SHP 파일로부터 점 데이터를 읽어 입력 데이터를 구성하여 Convex-Hull을 실행하고 그 결과로 반투명 빨간색 폴리곤을 추가하는 코드 모두를 나타내고 있습니다.

XrMapLib.ShapeMapLayer lyr = axXr.Layers.GetLayerAsShapeMap("lyr");
XrMapLib.ShapeTable tbl = lyr.ShapeTable;
int cntRows = tbl.RowCount;

ConvexHull.Point[] pts = new ConvexHull.Point[cntRows];

for(int i=0; i<cntRows; i++)
{
    XrMapLib.ShapeRow row = tbl.GetRow(i);
    if (row.Load())
    {
        pts[i] = new ConvexHull.Point(row.Centroid.X, row.Centroid.Y);
        row.Unload();
    }
}

pts = ConvexHull.Get(pts);

axXr.Layers.AddGraphicLayer("gl", "");
axXr.WaitForAllConnections();

XrMapLib.IPolygonGraphicElement gr = new XrMapLib.PolygonGraphicElement();

XrMapLib.CoordListCollection clc = new XrMapLib.CoordListCollection();
XrMapLib.CoordList cl = new XrMapLib.CoordList();

for(int i=0; i< pts.Length; i++)
{
    cl.Add(pts[i].x, pts[i].y);
}

clc.Add(cl);

gr.SetPolygonList(clc);

gr.FillSymbol.Color = RGB(0, 0, 255);
gr.FillSymbol.Alpha = 110;
gr.LineSymbol.Alpha = 0;

XrMapLib.IGraphicLayer gl = axXr.Layers.GetLayerAsGraphic("gl");

gl.AddElement(3, gr as XrMapLib.GraphicElement);

axXr.Update();

코드를 살짝 설명하면, 1~15번 코드는 SHP 파일로부터 포인트 데이터를 읽어와 Convex-Hull 알고리즘에 입력할 데이터를 준비하는 것이고, 17번 코드가 바로 Convex-Hull의 실행이며 19번 코드부터는 Convex-Hull의 결과를 그래픽 객체로 가시화시켜주는 코드들입니다.

2016/05/10 19:36 2016/05/10 19:36
크로스 도메인(Cross Domain)을 허용하는 OpenAPI 개발을 위한 JSONP

AJAX 방식은 서로 다른 도메인간의 데이터를 받아 오는 것을 기본적으로 막고 있지만, JSONP라는 방법을 이용해 가능하게 됩니다. 이에 대해 정리해 봅니다. JSONP 방식의 OpenAPI를 제공하는 Java 서블릿 중 doGet 함수는 다음과 같습니다.

protected void doGet(HttpServletRequest request, HttpServletResponse response) 
    throws IOException
{
    String name = request.getParameter("name");
    String nameDecoded = URLDecoder.decode(name, "UTF-8");
    String callbackFunction = request.getParameter("callback");

    String responseData = "({\"Value\": \"Hello, " + nameDecoded + "\"})";
		
    String result = callbackFunction + "("+ responseData + ");";

    response.setContentType("application/json;charset=UTF-8");
    response.setCharacterEncoding("UTF-8");
    response.setStatus(HttpServletResponse.SC_OK);
		
    response.setContentType("text/javascript");
    PrintWriter out = response.getWriter();
    out.println(result);
}

위의 OpenAPI는 클라이언트 측에서 name과 callback이라는 파라메터를 전달해 준다라는 전제 조건을 갖습니다. 서버는 자신에게 전달된 name을 이용해 클라이언트에게 다시 Hello로 구성된 문자열을 결과로 전달해 줍니다. 여기서 전달 방식이 중요한데요. 그 전달방식이 바로 JavaScript 함수호출에 대한 코드입니다. 이 코드 문자열을 클라이언트가 받아 실행해 준다라는 것입니다. 실제로 위의 서블릿에 대해 웹 브러우저를 통해 호출해 보면 다음과 같습니다.

위의 URL 호출을 좀더 설명하면, name 파라메터에는 Dip2K를 지정했고, callback 파라메터에는 Test를 지정했습니다. 그 호출 결과는 Value를 키로 하고 Hello, Dip2K를 값으로 하는 객체를 인자로한 Test 함수의 호출 코드에 대한 문자열입니다. 클라이언트에서 이 문자열을 코드화하여 실행해주면 성공적으로 서버에서 전달한 데이터를 받아 처리할 수 있게 되는 것입니다.

실제로 아래의 코드는 jQuery를 이용해 JSONP 방식으로 크로스도메인 문제를 깔끔하게 해결해 데이터를 주고 받는 코드입니다.

var url = 'http://localhost:8079/OpenAPI?name=김형준&callback=?';

$.ajax({
    url: url,
    type: 'get',
    dataType: 'jsonp',
    success: function (data) {
        alert(data.Value);
    }
});

실행 결과는 'Hello, 김형준'을 표시하는 Alert 창 입니다.

BLOG main image
GIS Developer, 김형준 / (주)지오서비스 서비스개발팀 팀장 / '모바일 3D 그래픽스' 번역 및 출판 / '모바일 GIS 프로그래밍' 집필 및 출판
 Notice
 Category
전체 (754)
GIS 개발 (240)
공간DB 공유 (3)
프로그래밍 (298)
스치는 생각들 (146)
번역 또는 집필 (4)
 TAGS
GIS Xr OpenGL Shader BlackPoint FingerEyes C++ Algorithm Android Java DuraMap Map Engine WPF ActionScript C# ArcObjects ArcGIS 안드로이드 FingerEyes-Xr BlackPoint-Xr JavaScript HTML5 WPF 3D template Flex DuraMap-Xr OrangeMap Pattern Service .NET Graphic OpenGL ES XML Mr.Tiler-Xr OOD Mobile GIS XGE WebService Design GPS GIS Korea PSP KASS WKT PostGIS GeoService iOS 모바일 GIS Edit Web
 Recent Entries
Convex-Hull 알고리즘 구현
크로스 도메인(Cross Dom...
[JavaScript] 한글인가?,...
주소(도로명, 지번) 좌표... (34)
PostgreSQL에서 초성 얻기
 Archive
2016/05
2016/04
2016/03
 Visitor Statistics
Total : 4128214
Today : 285
Yesterday : 1189
태터툴즈 배너
rss