Linear-time algorithms for sorting vertices in polygon contours

Question

I figured out an algorithm that lets me turn my holed polygons into trapezoids in linear time if I have vertex indices sorted from lowest coordinate to highest.

I get simple polygons as contours. They have certain order that might be exploited most of the time.

So giving these conditions, is there a near-linear-time algorithm on sorting?

Answer 1

Sorting algorithms that run in linear time are counting sort, radix sort and bucket sort.

Wiki is also helpful: Sorting algorithms

Answer 2

I'm not sure what you mean by "certain order" and "most of the time". For simple (i.e. non-convex) general polygons I'm afraid there might be no solution since the points may be in any order with respect to their coordinates (you can have very odd shaped "simple" polygons...)

If you're dealing with convex polygons of course, linear-time sorting with respect to the y coordinate would be simple: Just find the lowest point and "walk up" on the left and the right side in parallel...

Anyway, unless you have really big polygons, a well implemented O(n log n) algorithm may be as fast or even faster than some linear-time algorithm (e.g. if the constant factor of the linear algorithm is bigger than log n ...)

Answer 3

Your question is a little vague, but assuming the following:

1. The polygons are in 2D
2. You want to sort the vertices along a specific axis (x or y)
3. The polygons are defined as a connected outline

You could do the following:

1. Walk along the vertices
2. For the first vertex add it to a range
3. For every other vertex, if the vertex is "higher" than the previous add it to the current range, otherwise create a new range with the vertex in it.
4. We now have a list of sorted ranges, merge the ranges with each other: http://en.wikipedia.org/wiki/Merge_algorithm

Answer 4

I think the answer you want is "no", but I also think you might want to consider your question more carefully.

The problem is that you are using continuous coordinates, so in principle you can't use a linear sort. (In practice, you can use use, say, a radix sort to handle a fixed-size coordinate, but in practice this may actually be slower than a standard O(N log N) sort, due to the overhead involved...)

The theoretical rule is: whenever you have a situation where you can only compare your values, a general sort cannot be faster than O(N log N).

You mentioned an unspecified property that "might be exploited most of the time". The problem is that O() notation is an asymptotic, worst-case, theoretical property, so "most of the time" won't make a difference. A specific property of the input can often be exploited in this way, but:

• the O() speedup is very sensitive to exactly what your property is
• an algorithm with a better O() might be much slower for your practical application
• the most effective technique to practically exploit your input is often very different from the technique with the best asymptotic properties

Unfortunately, when tweaking your algorithm to exploit your input, it is easy to miss an obscure worst-case scenario which will kill your performance in unexpected ways, long after you have released it. The most important thing about the O() of your algorithm is to stop it from blowing up badly like this.

Note that, for this purpose, O(N log N) is near-linear, and using a standard, well-behaved library sort may well be the right choice.