the king
سه شنبه 24 دی 1398, 12:45 عصر
دوستان راهنمایی کنید
نقشه شما در اتوکد تشکیل شده از یکسری نقاط که تشکیل یک چند ضلعی نامنتظم رو میده. مثلا :
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));
}
151254
و محاسبه مساحت یک چند ضلعی نامنتظم که نقاط اش مشخصه هم فرمول ساده ای داره :
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;
}
151255
برای رسم به مثال پیوستی مراجعه کنید :
151256