Sorting points to form contoure

[BeKinect]

In my software I get the coordinates of points of a contour stored in a vector matrix. This vector consist of n rows and three columns (xyz). So now I want to restore the contour. So my first thought was to use the atan2 function. But this just works for convex contours.
So my new attempt is to find the nearest poin to a start point. So I start with a function to calculate the distance of two points

  double distancepoints(vector<double> const& s1, vector<double> const& s2)
{
	return sqrt( (s1[0] - s2[0])*(s1[0] - s2[0]) + (s1[1] - s2[1])*(s1[1] - s2[1]) );
}

Based on this I want to calculate the index of the nearest point of a given point in the vector matrix.

int closestpoint(vector<double> const& p, begin, end)
{
	double d=0;
	
	while(begin != end)
	{
		double d2 = distancepoints(p, *begin);
		if(d2 < d)
		{
			d = d2;
			result = begin;
		}
	}

	return result;
}

In this function I have to pass the beginning of the vector matrix and the end of the vector. But I do not know how to pass this arguments and how to return the index of the calculated point. So I think this function has to be changed completly to get the index, but how I could change it, is my real problem.

In the end I would use this as code

vector<vector<double> > startpoint;

for(size_t i=0; i<startpoint.size(); i++) {
    startpoint[i].resize(spalte);
}

startpoint[0][0]=matrix[0][0];
startpoint[0][1]=matrix[0][1];
startpoint[0][2]=matrix[0][2];

matrix.erase(matrix.begin() );


while(matrix.size()) {
	int it = closestpoint(startpoint, matrix.begin(), matrix.end());
	// Store nearest point 
	hull.push_back(std::vector<double>(3, 0));
	int r = hull.size()-1;
	hull[r][0] = matrix[it][0];
	hull[r][1] = matrix[it][1];
	hull[r][2] = matrix[it][2];
	
        // Our new p is the point we just found
	startpoint[0][0] = matrix[it][0];
	startpoint[0][1] = matrix[it][1];
	startpoint[0][2] = matrix[it][2];

	// Remove the point we just found from the vector of points
	matrix.erase(matrix[it]);
}

Does someone have an idea or a hint for me, how to return the index of the nearest point?

[coder777]

It would be better to use a struct like

struct point
{
  double x;
  double y;
  double z;
};

instead of a vector.

In your case the parameter for closestpoint(...) would look like this:

int closestpoint(vector<double> const& p, vector<vector<double> >::iterator begin, vector<vector<double> >::iterator end)
{
	double d=0;

	vector<vector<double> >::iterator it = begin;
	for(; begin != end; ++it)
	{
		double d2 = distancepoints(p, *it); // Note: it
		if(d2 < d)
		{
			d = d2;
			result = begin;
		}
	}

	return std::distance(begin, it);
}

For std::distance() see:
http://www.cplusplus.com/reference/iterator/distance/?kw=distance

[TheIdeasMan]

Hi,

Google "Delaunay Triangulation", there are some sites with explanations on how it works, along with some code to look at.

Basically, one doesn't sort points, instead start with a bounding box of all the points and make 2 triangles from it, then add points. New points will always be inside an existing triangle (or on a triangle boundary), the order the points are added is independent of the result.

Sorting for this isn't very efficient - even for small amount of data, but imagine if you had 1 million points: the amount of sorting quickly gets out of hand. I have used software (that is capable of dealing with Point Clouds) to triangulate 3.2 million points, it was probably capable of dealing with much more than that.

The thing with Point Clouds is the data structure used to store the points. Whatever flat structure traditional software uses doesn't cut it. One technique is to use a RTree (Rectangle Tree), for sparsely populated sets there is a rectangle for each discrete group of points. For densely populated sets, the concept of Tiles is a specialisation of RTree.

Good Luck !!