New answers tagged computational-geometry
1
Given a set of points in the plane all laying on the axis, find the number of right angled triangles
Here is a simpler solution if points lay only on the axis running in time $O(n^2)$. scroll down for a solution for the general case for any set of points in the plane.
Let us distinguish three case of triangles. the first is when the origin is a point of the triangle (and hence it must be the right angle). The second case is where two points lay on the $x$ ...
1
Addition of vectors is commutative, so the order of moves is irrelevant. For example:
$(0,2) + (3,1) + (2,-2) = (0,2) + (2,-2) + (3,1) = (3,1) + (0,2) + (2,-2) = (5,1)$
So a simple brute force method is to calculate the distance traveled for all subsets of the set of $n$ possible moves. There are $2^n$ such subsets, but you don't need to consider the empty ...
1
I would suggest that you don't calculate the distance between all pairs of points, but only between pairs of points that are nearest neighbors. You could store the points in some nearest-neighbor data structure, e.g., an octree, or even a fixed partitioning of space. Some data structures might allow for relatively rapid updates, so you could even update ...
2
If you choose a formula with parameter $t$ you'll get the $P_x$ value as a result of a number of operations - additions, multiplications and one division:
$$t = \frac{(x_1-x_3)(y_3-y_4)-(y_1-y_3)(x_3-x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)}$$
$$P_x = x_1 + t(x_2-x_1)$$
The number $x_2=72057594037954921$ contains 17 significant decimal digits - so it ...
Top 50 recent answers are included
