Search code examples
c#algorithm2dcoordinatesangle

Check if two sets of points are in different hemispheres from a source point

I have a 2D plan with integer coordinates.

On this plan, there are many points, separated in three categories.

  • The "Source". There is only a single point that is the source.
  • The Nice Group, containing an unknown (but reasonable) number of points
  • The Evil Group, containing an unknown (but reasonable) number of points

What I am trying to do first of all is to figure out (yes/no) if the two groups are in separated hemispheres.

If you could draw a line through the Source (Blue in the images) so that all nice are on one side, and all evil are on the other, then they are considered in different hemispheres. If so much as one of either group can't be put on the same side as the rest, it's false.

The second step is to figure out the angle of this hemisphere. In the first example (below), I've drawn a 180 degrees angle (straight line), but I would like to calculate the most unbalanced angle (close to 0) that would allow separating the groups perfectly. The line then would be two half-lines starting at the source going to infinity. I want to know the smallest angle (so, logically, the biggest angle if you measure the other side) that keeps the first test as true

Examples:

1: enter image description here

2: enter image description here

3: enter image description here

Right now I am able, through code, to calculate the angle between every individual point and the source. I am stuck at figuring out how to test the "togetherness" of the groups, and most importantly, the absence of a member of the other group in between.

I am working in C#, but this question is really more about the algorithm (I can't think of a working one), so I will accept any answer that solves the problem in any (readable) language, including pseudo-code or straight up text explanation.

All of the points are, in context, complex objects that include a X and a Y coordinate. The other attributes are irrelevant to the question as they are already separated in the required groups (origin is alone and there are two lists for the rest).

Solution

  • You can sort and scan. Let's introduce polar coordinate system with its origin at the Origin and arbitrary axis.

    • Compute azimuth for each point (either nice or evil)
    • Order points by their azimuth, e.g.
    • Scan the sorted collection; if you have 2 or less transistion between nice to evil or evil to nice; return true, otherwise false

    E.g. (let azimuthes be in degrees)

       {nice,  12}
   {nice,  13}
   {nice,  15}
   {nice,  21} // nice to evil transition
   {evil,  47}
   {evil, 121}
   {evil, 133} // evil to nice transition
   {nice, 211}
   {nice, 354}

    We have two transitions, answer is true. 

       {nice,  12}
   {nice,  13}
   {nice,  15} // nice to evil transition
   {evil, 121}
   {evil, 349}

    One transition only, answer is yes

       {nice,  12}
   {nice,  13} // nice to evil transition
   {evil, 121} // evil to nice transition
   {nice,  15} // nice to evil transition
   {evil, 121} // evil to nice transition
   {nice, 349}

    Four transitions, points can't be separated, answer is false