I have a collection of one or more line segments for which I know the (x,y) coordinates of the endpoints. The segments may or may not be parallel and may or may not intersect. Each segment endpoint will have a circle drawn and centered around it, and the two circles for any one segment will have the same radius and will have a positive separation (segment has positive length). Furthermore, any circle will have a radius of r or 2r. The result is a collection of circles that have a natural pairing according to segment and radius.

Although I need only work in 2D for what I need to calculate, in the real world the convex hull of the circle collection represents a horizontal surface of known height above the ground. Starting at the hull edge and moving upward and perpendicularly outward from the hull is a surface of known constant slope. (For a single pair of circles, for example, the two surfaces would look like a football stadium.) The hull of the circles can--and in practice often will--completely subsume one or more circles.

Now, I have a point of known coordinates, say (u,v), that is known to be on the edge or outside of the convex hull of the circles. What I need to determine is the perpendicular distance from the point (u, v) to the edge of the hull. With that distance I can easily calculate the height of the "football stadium" surface at the coordinates (u, v), which is my ultimate goal.

What I know:

  1. Coordinates of segment endpoints (i.e. circle centers), (x,y)
  2. Radii of the circles r or 2r
  3. Coordinates of the "test" point, (u, v)

How do I go about this calculation in a way that is efficient and applicable to all cases of one or more segments in any (2D) arrangement that might come along? (Segments, by the way, represent airport runways.) I have thousands of points to evaluate against the sloped surface, so I will be automating this.

(I apologize for the lack of mathematical formality. I have fair facility with reading and understanding formal mathematical presentation, but creating anything of the caliber I see here on the Math SE is not in my skill set ... nor is LaTeX sadly ... yet)

Thank you kindly for the help.

My further research has led to the Devillers and Golin 1995 paper:

Devillers, O., and M. J. Golin. 1995. Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. Information Processing Letters 56(3), 157-164.

The algorithm presented for the hull of a collection of circles is a great fit for the parameters that I know (as discussed above), and it will allow identification of the arcs (and segments) that are part of the hull. In general, I can see that my challenge is going to be coding all of this, but more specifically I need a clear data structure to store the arc/segment information. I eventually need to calculate the perpendicular distance of a point to the hull, my original question. I will "fess up" that I am a GIS Analyst and that I already have the hull polygon; I could easily do a geometry operation in a GIS and be done with it, but the result would only be approximate in that the polygon has nodes along the circular arc. I am comparing my thousands of points against other "polygons," too, and I am doing that purely mathematically. I need to be consistent. The hull of circles case that I describe here is just a particularly intractable one for me as a mathematics non-professional not particularly skilled in implementation of computational geometry algorithms.


The Devilliers and Golin (1995) paper is indeed what I was looking for, but I was just not up to the task of coding their algorithm. Hence, given the fact that I will in reality be dealing only with 14 circles at the very most, I chose to do a brute force method. For every possible pair of circles, I found the part of each circle "shadowed" by the other, as described by Devilliers and Golin. (The ends of each shadowed arc are the outer tangent points, of course.) After all pairs are evaluated, any unshadowed arcs are the circles' contribution to the hull, and their end points are the tangent points on the hull. From there, it is easy with vectors to establish where a test point is located in relation to the hull: adjacent to the a tangent line or adjacent to a circular arc. Then I can calculate a perpendicular or radial distance respectively.

I realize that, in general, this method is incredibly inefficient for any larger number of circles, but in my case of a small number of circles, it works quite quickly ... "it works" being admittedly the operative phrase.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.