CODEWITHSUNDEEP
algorithmcomputational-geometry
fengkeyleaf
fengkeyleaf

Reputation: 1

How to handle circles in geometric intersection

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.

Upvotes: 0

Views: 102

Answers (1)

user1196549
user1196549

Reputation:

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

Upvotes: 1

Related Questions