I have a around $1000$ points and $1000$ segments in the form of $(x_1, y_1, x_2, y_2)$ meaning the segment starts at coordinate $(x_1, y_1)$ and finishes at $(x_2, y_2)$. For each line i want to know how many points strictly left to $(x_1, y_1)$ make $< 90^\circ$ angle with line. See the picture below for more clarifications:
Is there any faster trick other than checking all the points?
asdf In this picture AB is my line and C, D, E, F, are the points. Points C, D, F make $< 90^\circ$ angle with $AB$, $E$ makes $> 90^\circ$ degree angle with AB and G make $< 90^\circ$ angle with AB, but it not strictly right to A. So my answer is 3 (C, D, & F).
Because you have many points to be classified against many line segments, there are certain shortcuts you can take. For example, let's consider a situation where the line segments are within a smaller bounding box than the points:
Above, the points are split into nine disjoint sets, based on their coordinates with respect to the line segment bounding box coordinates (in the image, I expanded the bounding box a bit, to make it easier to see). This is only done once, for the entire set of points and line segments.
Based on whether a line segment is mostly horizontal or mostly vertical (or diagonal), and in which direction, you can eliminate at least 1/9th of the points from consideration altogether.
Additionally, having the points in each part sorted by both $x$ and $y$ coordinates (that is, two separate arrays, for example), depending on the slope of the line segment with respect to the part, you can scan the points in order, with first "outside" point signaling the rest must be outside too. However, this adds considerable complexity and the overhead of sorting the points; it may not be useful enough in practice.
A better approach is to use a regular rectangular grid,
with each grid cell containing a separate (possibly empty) array of points within that cell.
(Note that it is common to consider the lower bound to be inclusive, but the upper bound exclusive. In C, this means you need to "increment" the bounding box upper bounds using
exclusive_upper = nextafter(inclusive_upper, HUGE_VAL). See man 3 nextafter for details.)A simple "line" routine can be used to check which cells intersect with the original line segment, as well as the lines perpendicular to it at the endpoints. The points in these grid cells must be completely checked. However, points in the cells inside these (the darker red shading in the image) are all guaranteed to be inside. Thus, most cells will not be needed to be checked at all, and most points can be discarded without any access, for each given line segment.
Of course, this is even more complex to implement, and the optimal grid (number of cells) is an open question, but I do believe this would yield the best results if the line segment and point distributions are completely unknown beforehand.