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

Question

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:

2:

3:

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).

this may be somewhat related to your question: https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle — X39, Sep 20 '18 at 13:29
This is the [Separating Axis Theorem (SAT)](https://en.wikipedia.org/wiki/Hyperplane_separation_theorem) applied the the convex hulls of the two point-sets. — meowgoesthedog, Sep 20 '18 at 15:50

Dmitry Bychenko · Accepted Answer · 2018-09-20T19:52:49.437

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

score 1 · Answer 2 · answered Sep 20 '18 at 13:48

get the lowest current x, and lowest current y of on group. and get the highest... then compare the other group to see of there in between. if even one of the other dots is found between points (highx,highy) and (lowx,lowy) they are intermingled. if not they are seperated...

once you know they are seperated, draw a line from you lowest(x,y) to your highest(x,y) and transform that line to your origin point giving you two 'hemispheres'

note that this will only work if they are divided by a line, not an angle.

for angles

do a and y seperate once you have the lowest(or highest) x that the other group does not cross, then do the same for y. with these two coordinates and your origin you should be able to determine your angle.

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

2 Answers2