2

I am already implemented Graham scan, but i see that the bottleneck of my program is the sorting (80% of the time). I want to improve in it, now I am doing the following:

 std::sort(intersections.begin() + 1, intersections.end(), [&minElement](Point const& a, Point const& b)
 {return angle (minElement - a, XAxis) < angle (minElement - b,XAxis);});

Which gives me the exact angle, but it's not cheap because my angle function looks like the following:

float angle (const Point& v1, const Point& v2) {
    return dot (v1, v2) / (v1.Length () * v2.Length ());
}

In the Length function I have to do a square root, which is one of the most expensive operations. But this way I get a good ordering.

I tried ordering the array by Slope, dot, ccw, and even only removing sqrt from my compare, but none of that provides me the same ordering. Can you give me any advice?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Ryper
  • 338
  • 3
  • 15
  • Not an answer, but could graham scan be replaced by monotone chain? I mean, the sort in monotone chain is done by the coordinates, not the angle, which makes it a little faster. – Juan Lopes Jan 12 '17 at 22:25

2 Answers2

3

When you're sorting the points by their relative angles, you don't need to know the exact angle the two points make. Rather, you just need to know whether one point is to the left or to the right of the other.

Image, for example, you want to compare two points (x1, y1) and (x2, y2), assuming that the bottommost point is at (xp, yp). Look at the two vectors v1 = (x1 - xp, y1 - yp) and v2 = (x2 - xp, y2 - yp). To determine whether v1 is to the left or to the right of v2, which means you want to look at the sign of the angle made going from v1 to v2. If it's positive, then v2 is on the left of v1, and if it's negative, then v1 is on the left of v2.

The 2D cross product has the nice property that

v1 × v2 = |v1| |v2| sin(θ)

where θ is the angle made by going from v1 to v2. This means that θ > 0 if v1 is to the right of v2 and vice-versa, which is nice because that lets you compare which one goes where purely by taking a cross product!

In other words:

  • If v1 × v2 > 0, then v2 is to the left of v1.
  • If v1 × v2 = 0, then the points are collinear.
  • If v1 × v2 < 0, then v2 is to the right of v1.

The 2D cross product formula is given by

(Δx1, Δy1) × (Δx2, Δy2) = (Δx1 Δy2 - Δx2 Δy1)

Where, here, Δx1 represents x1 - xp, etc.

So you could compute the above quantity, then look at its sign to determine how the two points relate to one another. No square roots needed!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Yeah I tried this, the only thing i missed is that my function was returning an integer, not a float. So thank you. (I am working with floats) Also, what if the angles are the same, but the cross product is not? – Ryper Jan 13 '17 at 11:58
  • Can you clarify your question about angles? I didn't quite catch that. – templatetypedef Jan 13 '17 at 15:34
  • @templatetypedef But i think OP needed the sort functions for sorting all the points wrt the angle they make with the x-axis. For that `sin` doesn't work as it's not monotonic from [0, `pi`] radians. That's he was using `cosine` function in computing the angle. – Joe Black Jul 18 '21 at 03:01
0

You can make ad hoc optimization through caching.

First, Length() can cache its result in member variable. You only need to invalidate this value in case point is changed (and probably it's not the case). You can make lazy calculation, so Length will check if it has value and calculate/store if it doesn't, then return stored value.

Second, for given minElement and xAxis, angle (minElement - a, XAxis) becomes function of 1 argument, so you can save (cache) values of it for each point before sorting and use comparator on prepared values.

Naive approach to these things: use subclass of Point in main algo, so every point already has necessary methods and place for cached values.

Alexander Anikin
  • 1,108
  • 6
  • 14