New answers tagged

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 ...
Pablo H's user avatar
  • 191
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$ ...
Discrete lizard's user avatar
  • 7,578
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 ...
HEKTO's user avatar
  • 3,060
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 ...
Yves Daoust's user avatar
  • 8,841

Top 50 recent answers are included