Hi all,
I'm trying to compute a convex hull from a set of points using Jarvis' March. As part of the algorithm I'm computing for each point, its angle in relation to the other points. I compute this information in the datatable and then sort it using a dataview. Sometimes the dataview sorts correctly, sometimes it .. doesn't? I'll find most of the rows sorted correctly according to angle, but maybe three rows in strange places. This throws off the whole algorithm obviously. Anyone know what's going on? I appreciate any help at all.
Code:
do
{
for (i = 0; i < dv.Count; i++)
{
if(m_dt2.Rows.Count < 2)
dv[i][2] = getAngle(basePoint.X, basePoint.Y, Convert.ToInt32(dv[i][0].ToString()), Convert.ToInt32(dv[i][1].ToString()));
else
{
a = new Point(Convert.ToInt16(m_dt2.Rows[m_dt2.Rows.Count-2][0]), Convert.ToInt16(m_dt2.Rows[m_dt2.Rows.Count-2][1]));
b = new Point(Convert.ToInt16(m_dt2.Rows[m_dt2.Rows.Count-1][0]), Convert.ToInt16(m_dt2.Rows[m_dt2.Rows.Count-1][1]));
c = new Point(Convert.ToInt16(dv[i][0].ToString()), Convert.ToInt16(dv[i][1].ToString()));
ab = Math.Sqrt(((b.X - a.X)*(b.X - a.X)) + ((b.Y - a.Y)*(b.Y - a.Y)));
bc = Math.Sqrt(((c.X - b.X)*(c.X - b.X)) + ((c.Y - b.Y)*(c.Y - b.Y)));
ac = Math.Sqrt(((c.X - a.X)*(c.X - a.X)) + ((c.Y - a.Y)*(c.Y - a.Y)));
dv[i][2] = Convert.ToDouble(Math.Acos((ab*ab+bc*bc-ac*ac)/(2*ab*bc)));
}
}
if(m_dt2.Rows.Count < 2)
dv.Sort = "angle ASC";
else
dv.Sort = "angle DESC";
dgPoints.DataSource = dv;
Push(Convert.ToInt32(dv[0][0].ToString()), Convert.ToInt32(dv[0][1].ToString()));
basePoint = new Point(Convert.ToInt32(dv[0][0].ToString()),Convert.ToInt32(dv[0][1].ToString()));
dv[0].Delete();
}while(basePoint.X != baseX && basePoint.Y != baseY);
Dataview bug? or code error..
