Re: Intersect circle and irregular shape

Thanks a lot for your detailed response. However, tell me if I am
wrong, this type of approach would be pretty difficult to apply in a
situation like this:

http://bayimg.com/cAimkAAbn

In an ideal world, I would need something that could handle even more
complicated polygons.

GL

Roger Stafford wrote:
glaroc <glaroc@xxxxxxxxx> wrote in message <66c9ae27-c839-41e2-
a9a3-d5dcc7f311a7@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>...
Hi, I am looking for ways to calculate the percentage of the
circumference of a circle enclosed within an intersecting irregular
polygon. For example, if I have a circle centered within a triangle, I
want to know how much of the circumference of the circle is contained
within the triangle. This could be anywhere between 0 and 100. I know
I can do this in a topological GIS, but I really need Matlab for this.
I want to use this to build an edge correction program. I couldn't
find anything in the Matlab file central or anywhere else.

Thank you for any help you may provide,

GL
--------
Here's an outline of how I would tackle your problem, GL. First, find all the
points of intersection between the circle and the various line segments of the
polygon. Then sort such intersection points in accordance with the angles
they make with the circle's center. These points now divide up the circle into
non-overlapping arcs. Find the arc "midpoint" on the circle between each
pair of successive intersection points. Finally, use the function 'inpolygon' to
determine which of these midpoints lie inside the polygon. Each of the entire
circular arcs containing such midpoints must also lie within the polygon.
Then the sum of these "inside" arcs' angles divided by 2*pi times 100 gives
you the percentage you desire. I leave you to deal with the special case when
there are no intersection points.

Here is a procedure for finding the intersection between a circle having
radius r and center (a,b) with a line segment whose endpoints are (c,d) and
(e,f). Any point on the infinite line through these points has the parametric
representation

x = (c+e)/2+(c-e)/2*t
y = (d+f)/2+(d-f)/2*t

with parameter t. If t lies between -1 and +1, then such a point is actually
within the line segment. To also lie on the circle, we must have

(x-a)^2+(y-b)^2 = r^2

By substituting in the parametric expressions in t for x and y in this last
equality, we get a quadratic equation in t which we can use matlab's 'roots'
function to solve. This done as follows:

t = roots([(c-e)^2+(d-f)^2, ...
2*((c-e)*(c+e-2*a)+(d-f)*(d+f-2*b)), ...
(c+e-2*a)^2+(d+f-2*b)^2-4*r^2]);

where the three expressions show the derived coefficients of the above
quadratic. There will be either two, one, or no distinct real roots to this,
according as the circle intersects that many points of the infinite line. As
mentioned above, those that have a real t value between -1 and +1 yield the
points of intersection with the line segment, and their coordinates are
determined by substituting t into the above formulas for x and y.

Roger Stafford
.

Relevant Pages

  • Re: Intersect circle and irregular shape
    ... polygon. ... For example, if I have a circle centered within a triangle, I ... Then sort such intersection points in accordance with the angles ... circular arcs containing such midpoints must also lie within the polygon. ...
    (comp.soft-sys.matlab)
  • Re: Optimal distribution of points within complex polygons.
    ... few exceptional cases with self intersections). ... viusally by the radius of the circle that is around each sampling site) ... The sites need to lie within the polygon but I would also be interested ...
    (comp.graphics.algorithms)
  • Re: Intersect circle and irregular shape
    ... Joaquim, if I interpret Guillaume Jacquenot's m-file ... which would contain a quarter circle as approximated by ... The problem of finding the intersection between a line ... irregular polygon." ...
    (comp.soft-sys.matlab)
  • Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)
    ... >Maybe higher roots can be broken down into square and cube. ... They quit teaching square root by hand in the 1960s in the ... >of 180,000 sides containing the unit circle, each side is very ... >of the polygon are virtually indistinguishable. ...
    (comp.theory)
  • ANN: FastGEO Computational Geometry Library
    ... * 2D/3D Segment intersection point calculation ... * 2D/3D Triangle, quadix, rectangle, circle and polygon perimeter ... * Closest point on segment from a point ...
    (borland.public.delphi.thirdpartytools.general)