Which sides of a triangle are visible to an observator?

Question

Working o 2-d plane.

Supposing that there is a observer standing on the origin (0, 0) looking to the first quadrant. If there is a triangle drawn on the first quadrant, what sides are visible to the observer?

My first strategy is to check for each segment of the triangle, get this middle point and intersect this segments with a line in the origin. Always the side that is visible, is reached first. But this method is very tricky to do.

I would appreciate if you help me to find a easy way to check this.

Edit about the original problem: sorry about more information. The problem give to me $n$ black points and $m$ white points $(3 \leq n,m \leq 100)$. For each of these black points, check how many triangles can be formed. For each of these triangles, count the number of white points are inside on each of them. There is a naive algorithm to do it but takes $O(n^4)$ and I found a $O(n^3)$ solution. So that why I am asking this.

Answer 1

Since you've included the “cross-product" tag, here's a way to do this with cross products:

Sort the vertices of the triangle in order of increasing angle. Slope will do since all of the points are in the first quadrant. Call these points, in order, $P_1$, $P_2$ and $P_3$. Side $P_1P_3$ is the only one visible if it is closer to the observer than $P_2$, otherwise it's the other two sides that are visible. This is equivalent to checking whether or not the intersection of $OP_2$ and $P_1P_3$ is closer to the origin than $P_2$.

In homogeneous coordinates, the line passing through two points can be represented by their cross product, and the intersection of two lines represented in this way is given by their cross product. So, compute $(P_1\times P_3)\times(P_2\times[0,0,1])$ in homogeneous coordinates and compare this to $P_2$. You'll likely need to normalize the result by dividing by the third coordinate. We're guaranteed that the lines do intersect, so this will be non-zero.

If two of the points are at the same angle, then you can immediately compare them to determine the one visible side without further ado.

Update: I thought of something even simpler that doesn't require the use of homogeneous coordinates. Once you have the vertices sorted by angle, you need only determine if this puts them in clockwise or counterclockwise order. You can do this by taking advantage of the fact that the direction of the cross product of two vectors reflects their relative orientation. So, compute $(P_1-P_2)\times(P_3-P_2)$. If this value (i.e., the last coordinate) is negative, then only side $P_1P_3$ is visible, otherwise it's the other two sides of the triangle.

Answer 2

For each of the vertices $V_i$, find the angle $OV_i$ makes with the $x$-axis. Compare them and you should be able to find the vertices that make the largest and the smallest angles respectively.

From the vertex that makes the largest angle, counting anti-clockwise the edges of the triangle until the vertex that makes the smallest angle, and these edge(s) are the ones visible.