نوشته شده توسط
amintt
دوستان راهنمایی کنید
نقشه شما در اتوکد تشکیل شده از یکسری نقاط که تشکیل یک چند ضلعی نامنتظم رو میده. مثلا :
private List<PointF> _points = new List<PointF>();
private void Form1_Load(object sender, EventArgs e)
{
_points.Add(new PointF(109, 125));
_points.Add(new PointF(249, 67));
_points.Add(new PointF(367, 103));
_points.Add(new PointF(423, 217));
_points.Add(new PointF(373, 259));
_points.Add(new PointF(416, 333));
_points.Add(new PointF(261, 355));
_points.Add(new PointF(142, 292));
}
area01.png
و محاسبه مساحت یک چند ضلعی نامنتظم که نقاط اش مشخصه هم فرمول ساده ای داره :
private static float CalcArea(List<PointF> points)
{
if (points.Count < 3)
{
return 0;
}
var area = points[points.Count - 1].X * points[0].Y - points[points.Count - 1].Y * points[0].X;
for (var i = 0; i < points.Count - 1; i++)
{
area += points[i].X * points[i + 1].Y - points[i].Y * points[i + 1].X;
}
return area / 2f;
}
حالا مساله ما اینجا است که می خواهیم از این چند ضلعی بخشی رو جدا کنیم که مساحتش فرضا 50 درصد مساحت کل باشه، و نیاز به الگوریتم ای داریم که نقاط اون چند ضلعی رو بدست بیاره.
کار ساده است، فرض می کنیم که با یک خط عمودی چند ضلعی رو به دو قسمت تقسیم کنیم که اون خط عمودی در موقعیت x باشه. تمامی نقاطی که سمت چپ این x باشند رو درج می کنیم،
تمامی نقاطی که در سمت راست این x باشند حذف می کنیم و محل تقاطع هر خطی که از یک طرف به طرف دیگه این خط عمودی گذر می کنه رو درج می کنیم.
یک چند ضلعی بدست میاد که درست از خط عمودی در موقعیت x برش خورده و سمت راستش حذف شده. مساحت این چند ضلعی جدید رو حساب می کنیم، اگر از اون درصد مورد نظر بیشتر شد x رو کمتر می کنیم و اگر بیشتر از اون درصد مورد نظر شد x رو بیشتر می کنیم.
الگوریتم شبیه روش جستجو در آرایه مرتب شده است :
private static List<PointF> GetPercentagePoints(List<PointF> points, int percentage)
{
var minX = points[0].X;
var maxX = points[0].X;
for (var i = 1; i < points.Count; i++)
{
if (points[i].X < minX)
{
minX = points[i].X;
}
else if (points[i].X > maxX)
{
maxX = points[i].X;
}
}
var fullArea = CalcArea(points);
var output = new List<PointF>();
while (minX < maxX)
{
var x = (minX + maxX) / 2f;
output.Clear();
var prevIndex = points.Count - 1;
for (var i = 0; i < points.Count; i++)
{
if (points[i].X <= x)
{
output.Add(points[i]);
}
else
{
if (points[prevIndex].X <= x)
{
var delta = (points[i].Y - points[prevIndex].Y) / (points[i].X - points[prevIndex].X);
output.Add(new PointF(x, delta * (x - points[prevIndex].X) + points[prevIndex].Y));
}
var nextIndex = (i + 1) % points.Count;
if (points[nextIndex].X <= x)
{
var delta = (points[nextIndex].Y - points[i].Y) / (points[nextIndex].X - points[i].X);
output.Add(new PointF(x, delta * (x - points[i].X) + points[i].Y));
}
}
prevIndex = (prevIndex + 1) % points.Count;
}
var area = CalcArea(output);
if (100f * area / fullArea > percentage)
{
maxX = x - 1;
}
else
{
minX = x + 1;
}
}
return output;
}
area02.png
برای رسم به مثال پیوستی مراجعه کنید :
AreaPercentage.rar