Geometric sort using Visual C++ ...?

My problem is to sort vertices in order to get a polygon rather than scattered areas. Currently I am wondering about planes, not 3d. I am out of math quiet some time, so please be as easy as possible, provide links, examples, etc. thanks you for your efforts in advance:

Please also check out the commented image at

http://www.flickr.com/photos/45608711@N0%E2%80%A6

to answer my question.

Here is some sample code, which is not gaining desired results:

The points are random generated. I want to sort them in a way that they describe a polygon. Currently I tried sorting by x and by y coordinates. The following examples shows how I sort

using x-coordinates as order criterium. The call to qsort and the compare function are further down.

#include <windows.h>

const POINT globalPointArray[] ={

{rand() % 800 , rand() % 600},

{rand() % 800 , rand() % 600},

{rand() % 800 , rand() % 600},

{rand() % 800 , rand() % 600},

{rand() % 800 , rand() % 600},

{rand() % 800 , rand() % 600},

{rand() % 800 , rand() % 600},

};

// this would be a function call to the Win GDI Polygon function!!!!

void fct(HDC hdc) {

Polygon(hdc, globalPointArray, 7);

}

static int compare(const void *a, const void *b)

{

POINT *ptA = (POINT *)a,

*ptB = (POINT *)b;

return ptA->x - ptB->x;

}

This is the compare function I am currently using for the quicksort. As u can see, the sort order is by x coordinates.

qsort(globalPointArray, iCounter, sizeof(POINT), compare);

Thank you.

Update:

In case you have problems viewing the image, try this link please, it should work:

http://www.flickr.com/photos/45608711@N07/43571615...

2 Answers

Relevance
  • 1 decade ago
    Favourite answer

    I'm not certain what answer you're after. What you have is technically a polygon, it just happens to be a complex one (i.e. concave and self-intersection).

    If I'm reading you correctly, you just want to reorder the points so that it's no longer self-intersecting (though possibly concave). If so, there is no unique answer to a given problem.

    My suggestion is to compute the convex hull of the points first (see first link). Once you've got that, for each of the remaining points, associate them with one of the edges of the convex hull (say, by perpendicular distance). Finally, for each edge in the convex hull, sort the points that are associated with that edge by the intersection point between the edge and the perpendicular. CGAL (see second link) has all of the basic algorithms that you need.

  • Anonymous
    6 years ago

    extremely tough situation. look in a search engine. that could help!

Still have questions? Get answers by asking now.