Skip to content

Instantly share code, notes, and snippets.

@dyno
Last active October 7, 2023 16:56
Show Gist options
  • Save dyno/795e69d893ca8ac10f007511227e4371 to your computer and use it in GitHub Desktop.
Save dyno/795e69d893ca8ac10f007511227e4371 to your computer and use it in GitHub Desktop.
line sweep in 2 dimension
#!/usr/bin/env python3
"""
Each point is represented by [x, y], x and y both are floating points.
unit square: with edges either horizontal or vertical, side length 1
Input: n points Output: max number of points can be covered by a unit square
Example:
input:[[0.1,0.2], [0.5, 0.6], [100, 200], [0.9,0.8]]
Output: 3
"""
from itertools import accumulate, chain
from typing import List
# some reference https://www.niser.ac.in/~aritra/PlaneSweepAlgorithm.pdf
def line_sweep(xs: List[int]) -> int:
# basic line sweep algorithm
# event +1 at original x
# event -1 at x + 1.0
ys = sorted(chain.from_iterable([[(x, 1), (x + 1.0, -1)] for x in xs]))
return max(accumulate(y[1] for y in ys))
def main():
points = [
(0.1, 0.2),
(0.5, 0.6),
(0.9, 0.8),
(100, 200),
]
events = sorted(
chain.from_iterable((((p[0], p), 1), ((p[0] + 1, p), -1)) for p in points)
)
mx = 0
inflights = set()
# apply line sweep algorithm on xs.
for (x, p), delta in events:
print(((x, p), delta))
if delta == 1:
inflights.add(p)
# then apply the line sweep algorith again on ys in range.
mx = max(mx, line_sweep([p[1] for p in inflights]))
else:
inflights.remove(p)
print(mx)
if __name__ == "__main__":
main()
@dyno
Copy link
Author

dyno commented Oct 7, 2023

https://bubchi89v2.wordpress.com/2014/01/05/interval-tree-point-of-maximum-overlap/
the original problem statement in Introduction to Algorithm 4th edition

17-1 Point of maximum overlap
You wish to keep track of a point of maximum overlap in a set of intervals4a point with the largest number of intervals in the set that overlap it.
a. Show that there is always a point of maximum overlap that is an endpoint of one of the intervals.
b. Design a data structure that efûciently supports the operations INTERVAL- INSERT, INTERVAL-DELETE, and FIND-POM, which returns a point of max- imum overlap. (Hint: Keep a red-black tree of all the endpoints. Associate a value of with each left endpoint, and associate a value of with each right endpoint. Augment each node of the tree with some extra information to maintain the point of maximum overlap.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment