Convex Hull은 볼록한 껍데기로.. 무수히 많은 포인트를 감싸는 볼록한 영역으로 정의할 수 있습니다. 입력 데이터인 포인트는 SHP 파일로부터 제공받아, 이를 듀라맵에서 그 결과를 표시하도록 하였습니다. 아래는 그 결과 화면입니다.
무수히 많은 작은 포인트를 감싸는 Convex Hull이 반투명한 빨간색 폴리곤으로 표시되어져 있습니다. 이러한 Convex-Hull에 대한 구현에 대해 C# 클래스로 정의했으며 아래와 같습니다.
using System;
using System.Collections.Generic;
namespace tstConvexHull
{
public class ConvexHull
{
public class Point : IComparer
{
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
코드를 살짝 설명하면, 1~15번 코드는 SHP 파일로부터 포인트 데이터를 읽어와 Convex-Hull 알고리즘에 입력할 데이터를 준비하는 것이고, 17번 코드가 바로 Convex-Hull의 실행이며 19번 코드부터는 Convex-Hull의 결과를 그래픽 객체로 가시화시켜주는 코드들입니다.
