4
\$\begingroup\$

I'm doing a light engine (c++, using sfml), and to connect the light vertices, I thought about drawing a triangle fan. Here is a representation of a triangle fan (sfml documentation):

enter image description here

The points HAVE TO be "ordered" to draw the shape correctly, otherwise it would mess the shape I suppose.

I drew the desired effect in ms paint:

As you can probably see, there is a central point, a light, and other points that I want to connect together. The problem is that the points are not always ... "In a row/Ordered" ? Let's see an example and simplify this problem.

In the example above, I can't connect the points from 0 to 8 because it would mess the shape.

I would like to reorder the points so I can connect them properly, like :

Do you have any ideas ?

I thought about doing something based on the "point in polygon" algorithm, like checking if the point is "on the right/left" but it seems complicated.

I don't necessarily need code (if you have time it would be nice) but I can try to do some, I just need ideas. Thanks

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Check this stackoverflow.com/questions/6989100/… \$\endgroup\$ Commented Dec 16, 2015 at 15:21
  • 2
    \$\begingroup\$ I find this site has lots of good tutorials/algorithms and 2D visibility is one of them redblobgames.com/articles/visibility There are also some examples of implementation in various languages \$\endgroup\$ Commented Dec 16, 2015 at 15:32
  • \$\begingroup\$ Thanks to both of you. (Counter)Clockwise sorting, this is what I wanted. Gonna check it out now and give a feedback! By the way, these links are pretty great, @Malrig 's one is golden \$\endgroup\$ Commented Dec 16, 2015 at 17:13
  • 2
    \$\begingroup\$ If you solved your own problem you should post it as an answer rather than editing your own question. This makes it easier to see that the problem has been solved and for people to find a possible solution if they have a similar problem. \$\endgroup\$ Commented Dec 21, 2015 at 23:18

1 Answer 1

Reset to default
3
\$\begingroup\$

I finally did it and found a quite simple solution, seems fast enough, I post it if anyone wants the solution.

I created a class Point

class Point { public: sf::Vector2f myPosition; float myAngle; Point(sf::Vector2f thePosition = {}) { myPosition = thePosition; } };

I made a vector of points : std::vector<Point> lightPoints

then, I retreived the angle of each point in the vector

for (size_t i = 0; i < lightPoints.size(); i++) { lightPoints[i].myAngle = getAngle(lights[ii].position,lightPoints[i].myPosition); }

(By the way, my getAngle function look like this)

float getAngle(sf::Vector2f a, sf::Vector2f b, bool inDegrees = false) { if (inDegrees) return (float)(atan2(b.y - a.y, b.x - a.x) * 180 / pi); return (float)(atan2(b.y - a.y, b.x - a.x)); }

And after getting all the angles, I sorted the vector:

std::sort(lightPoints.begin(), lightPoints.end(), [](const Point& p1, const Point& p2) { return p1.myAngle < p2.myAngle; });

And the sorting works like a charm.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Since this has resurfaced, here's a small opportunity for optimisation: You don't need to calculate the angles. atan is monotonic increasing -- that means if a > b, atan(a) > atan(b). atan2 is a bit more complicated, but you still should be able to sort them without any trig. Having said that, you've already said your solution is "fast enough", in which case there's no reason to change anything :) \$\endgroup\$ Commented Jun 14, 2016 at 6:48
  • \$\begingroup\$ Thanks for joining in, it is always interesting to receive feedback ! The light engine works really fine, unfortunately I made it real fast just to test stuff, I'll have to redo it, It's not super optimised and it's a mess down here, captain :D (I saw the archeologist badge, I tried but the thread wasn't old enough, I feel guilty now :c). Keeping that aside, this is brilliant, I never thought of that, so this code would work fine right ? (dy0/dx0) > (dy1/dx1) I'll just have to convert it to atan2 I guess. I'll keep in mind when i'll come to this again, this is really apreciated, regards :) \$\endgroup\$ Commented Jun 19, 2016 at 23:26
  • \$\begingroup\$ Haha, yeah, nothing wrong with trying to get the badges, I think :) Yeah, that code should work fine. Getting the full range of atan2 means you'll want to compare their quadrants before comparing their gradients, which means a bunch more comparisons during the sort (whether you want the gradient to be > or < depends on what quadrant you're in), but, assuming you use a typically (n log n) sort, that should still be faster than n atan2's for n of a few hundred or less (at a guess) \$\endgroup\$ Commented Jun 20, 2016 at 2:32

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.