Search code examples
c++geometrycross-product

Dividing two sets of points using a straight line

Suppose I have two sets of points, A and B, in 2D space. I want to know if there exists a single straight line that will have all points of A on one side and all points of B on the other, and if possible, find one such line. I found this question while searching but it is more of a "line of best fit" problem.

Intuitively, I feel like it is a question regarding cross-products but I can't figure out how it can be done.

Solution

  • You could find the convex hull for each set of points, and then follow the procedure in this question to determine if they intersect (and return a dividing line if they don't):

    How do I determine if two convex polygons intersect?