c++ – How to sort segments by their angle relative to the specific angle range?


I’m trying to implement a simple algorithm that will sort segments by their angle based on the given angle range. Each of these segments has one common end. These sorted segments will be later used in another algorithm that will generate triangles in order to keep track of road completeness.

Segment description

Each segment has its angle relative to x-axis with a range from 0 to 360 degrees. Each segment is described as two points with x and y coordinate each.

Current status

I have a road map that has two chains of segments: inner segment chain and outer segment chain (marked as black). It is guaranteed that these two chains of segments don’t intersect with each other. Finish line and starting line are marked as green segments and won’t be described further.

In order to keep track of road completeness (when a user drives a vehicle), I generated additional segments – checkpoints (marked as red) which later will be used as triangles. Checkpoints are generated from the inner segment’s first point. The checkpoint always has the beginning connected to the inner segment and the end to the outer segment. Please checkout the exemplary road map.

enter image description here

In the below images the red segments represent checkpoints (segments that have to be sorted). The blue line represents the x-axis. Black segments represent the inner and outer edges of the road. The purple arrow represents the direction of a user’s vehicle. The red numbers represent desired order of segments. Black numbers represent the order (index) of inner segments. It is good to notice that all the checkpoints have the same origin and the angle range is specified by two inner segments.

enter image description here

The biggest problem I encounter is the changing angle from 0 to 360 degrees. I already tried to measure angle difference and I’ve sorted angles from the smallest to the greatest but it only worked in some maps. I think that the order of the inner segments matter in this case.