caioaao's blog

Line segment sorting
By caioaao, 10 years ago, In English

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!

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You need to implement a function that compares two line segments, according to the current angle you are looking at. This means you will be sweeping the line segments using an angle, centered at that origin point, inserting and removing segments accordingly. You can't sort them all at once without a reference, in this case an angle in respect to the origin (can you see why?). Once you know a line segment comes first, this ordering in the set will never change. I am not good with geometry, but it is something like:

struct Line
{
	// struct variables and other useful functions comes here...
	bool operator<(const Line& other) const
	{
		double da = distance_to_origin(current_angle);
		double db = other.distance_to_origin(current_angle);
		return da < db;
	}
};
→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    But wouldn't it result in precision errors? I was looking a way to sort them using only integer operations. To give you an idea of what I was thinking, here is what I managed to implement, but didn't work and I couldn't find out why.

    point origin;

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 b.p1 isn't in the sector, then b.p2 must be (as they share a common
    // angle interval). Then checks if b.p2 is at the same side as origin.
    return ccw(a.p1, a.p2, b.p2) !=  ccw(a.p1, a.p2, origin);
  }
}

    I use it in this set: set<line, bool(*)(line a, line b)> activeLines(cmpActive);

    Line segments are only added to this set if they share a common sector, and I do the sweep using only cross product and checking for quadrants (this way I'm implicitly sorting the points by angle, but without floating precision errors)

    If you'd like to see more details on my full implementation, here it is: http://pastebin.com/gQ8M9y18

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Here is a drawing to illustrate where I think a precision error would give a WA:

    Here the red dot is the origin. At angle= α , maybe a precision error would tell us the wrong line is closer. then, when the sweep hits the blue dot, if we ask if the first line on the set is between the red and blue dot, we'd get the wrong answer.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The input contains only integers, so I would say that precision errors here wouldn't be an issue (someone correct me if I am wrong..). I haven't deeply checked your code, but how do you deal with cases where the beginning of the segment is at angle 45 and the end at angle 315? For instance if the center is (0,0) and there is a wall at (1,1) and (1,-1).

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I add an extra event in (1,0) to state that the segment begins there. So in the sweep the order would be:

        • open segment at angle(1,0) — meaning it'll be added to the set
        • close segment at angle(1,1) — remove it from set
        • open segment at(1,-1) — add it again on set. I don't need to close it, just remember to clear the set later

        and even the input containing only integers, i think it could lead to floating point errors, as I'd be calculating angles, distance from line segment to point in given angle, etc

        → Reply