TransWikia.com

Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree

Computer Science Asked by ThundeRat on October 21, 2021

I am curently working on automatic label placement, so for evaluating a model, one metric is to calculate the Area A:

A is the sum of every part of a rectangle covered by another. So if two rectangle overlap, A = 2 * Arectangle, if three rectangle overlap A = 3 * Arectangle, …

Because i am working in real time, i need to calculate this as fast as I can, so I went with a sweep line for the x-axis. But I don’t understand how can i use an interval or a segment Tree to calculate the length for the x point. So I wanted to know if there is a way to use one of these tree or if i am condamned to use another sweepline on the y axis.

Here is an example for the 1d problem:

enter image description here

Here the return value should be :
L = 2 * (8-5) + (8-7) + 2 * (10 – 8) + 2 * (18 – 17) = 6 + 1 + 4 + 2 = 13

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP