The idea of splitting point between sets SA and SB is not difficult, but I got confused because when I choose points for SA and use mean line for those, maybe some point from SB are closer to that line, but now it seems to me, that this is no problem at all…
Thanks a lot. I found bug in my calculus formula. Plus dividing by only one line will not work. It is evident for me now. It is great relief to find out where I was wrong.
Yep, sorting is to be used, however, it seems complexity of solving one case(using calculus) is large enough that it hides the complexity of sorting.
Not always result are intersecting lines, see result for my 2nd test case…
If the lines are not intersecting but parallel, the rest of the section, about two perpendicular lines that define the region closer to one line etc holds - with one modification: One of the two perpendicular lines lie far on the left, so that all points are on its right. The proof and everything is valid for that case as well.
Two consecutive projections only differ in two elements (a swap of two consecutive points), so maybe we can use only one sort and go clockwise, updating the sort order every time in O(1).