0

Recently, I'm working on a programming assignment related to Geometric intersection. The problem is to count how many intersections can be formed with the following 4 elements:

  1. Segment; 2) ray; 3) line；4) circle;

The link to the problem: Portal . If you cannot access it, there is the printable PDF: Portal

I've figured out how to deal with line and ray, the way is visualized as the follows:

Visualized image of handling line and ray

In other words, we can preprocess them and treat them as special segments. But I have no idea of how to handle circles. The hint, Circle roads can be broken into a number of arcs, is still unclear to me.

Sneftel
  • 40,271
  • 12
  • 71
  • 104
fengkeyleaf
  • 1
  • Seems like a strange hint to me. The constraint should be achievable with a quadratic algorithm. I'd modify [this answer](https://stackoverflow.com/a/67117213/2144669) to count intersections. – David Eisenstat May 19 '21 at 11:28
  • Your question falls out of the scope of this site. We are not a homework factory. Write a program first. –  May 20 '21 at 07:42
  • @YvesDaoust I would like to write a program, but I don't know how to modify B.O. algorithm, a kind of algorithm handling segment intersections, to ideal with cycles. I figured out how to use it handle line and ray, but cycle yet. I am stuck with it now. – fengkeyleaf May 22 '21 at 12:53

1 Answers1

1

To intersect a circle with a line/ray/segment, you can move the circle to the origin and rotate so that the linear entity becomes horizontal at ordinate h.

Then the abscissas of the intersection with the line of support are given by ±√r²-h². You can easily check if these points belong to the useful part of the line.

enter image description here

  • Thanks for your idea! I'll take it into consideration as well. And I've came up with an idea of breaking a cycle into four quarters of arcs, and handle them in the same way as segments, but your proposal should a good way to check if a segment intersects with a cycle. – fengkeyleaf Jun 03 '21 at 12:57
  • @fengkeyleaf: splitting the circle in arcs will not help, on the opposite. Because an arc can anyway be intersected once or twice. –  Jun 03 '21 at 13:14