Notice: this is a piece of a bigger problem I'm trying to solve, but I could figure the rest out, and I think this part would be a good resource for the community in general, as I couldn't find anywhere.
The problem: I have an origin point O and a set of several line segments that never crosses each other. I know the line segments have a common angle interval in which they all appear. This angle is measured according to a line parallel to X axis and that contains point O. I need to sort this set of line segments according to the distance from the origin point, meaning that in the angle interval that the line segments appear, if line A is always closer to the point O, A comes first in the set. This comparison must be made without floating point operations!
Here is a tiny (horribly made) pic to illustrate the problem:
The section between the dashed line is the region of interest. The expected result would be line 0 coming first and line 1 coming second.
Important notes:
- The line segments never crosses
- No three points are collinear (point O and the endings of the line segments)
I couldn't come up with anything that works, can anyone help me out?
If anyone is interested in the full problem, here is a link to it (though i UVa this sorting isn't necessary — weak test cases): UVa 12675 — Hide and seek
EDIT: I've managed to make it work! :D Here is the final comparison function:
inline bool cmpActive(line a, line b){
if(a == b) return false; // if lines are the same, ignore
// checks if b.p1 is in the sector defined by a.p1 and a.p2
if(ccw(origin, a.p1, b.p1) && !ccw(origin, a.p2, b.p1)){
// if it is, checks if b.p1 is on the same side of line a as origin
return ccw(a.p1, a.p2, b.p1) != ccw(a.p1, a.p2, origin);
}
else if(ccw(origin, a.p1, b.p2) && !ccw(origin, a.p2, b.p2)){
// if b.p1 isn't in the sector, but b.p2 is
return ccw(a.p1, a.p2, b.p2) != ccw(a.p1, a.p2, origin);
}
else{
// this was missing: when interval A is completely inside B, so we can
// choose any point of A we want
return ccw(b.p1, b.p2, a.p1) == ccw(b.p1, b.p2, origin);
}
}
In this pseudocode, ccw(A,B,C) refers to testing wether C is in clockwise direction from B, taking A as it's rotation center
I'd like to thank brunoja for the help he provided!