New answers tagged computational-geometry
0
votes
Queries to count points lying on arbitrary line
Depending on the size of N (the number of points) and M (the number of queries), it may be enough to precompute all the answers: there are no more than N*N possible lines. :-) You can represent all ...
8
votes
Accepted
Queries to count points lying on arbitrary line
Note that via point-line duality (i.e. mapping each point $(p_x,p_y)$ to the line $y=p_x x - p_y$ and each line $y=mx +c$ to the point $(m,-c)$), this problem is equivalent to: given a set $L$ of $n$ ...
0
votes
Accepted
Red-blue orthogonal line intersection algorithm
The ad-hoc algorithm for the problem with $m$ horizontal and $n$ vertical line segments might be the following one:
Step 1. Project beginning and ending points of all segments on the $OX$ axis and ...
0
votes
Accepted
Finding pixel closest (grid points) to rectilinear polygons
Hints:
Scan every red polygon and determine the cells it overlaps. Some are wholly overlapped, some partially. For the partial overlaps, you need to record the intersections between the polygon and ...
Top 50 recent answers are included
Related Tags
computational-geometry × 824algorithms × 443
graphs × 69
data-structures × 66
optimization × 64
polygons × 43
complexity-theory × 34
time-complexity × 31
graphics × 28
convex-hull × 27
reference-request × 25
computer-vision × 22
discrete-mathematics × 19
euclidean-distance × 18
image-processing × 17
search-algorithms × 15
linear-programming × 15
linear-algebra × 15
approximation × 14
voronoi-diagrams × 14
nearest-neighbour × 13
np-complete × 11
algorithm-analysis × 10
shortest-path × 10
clustering × 10