Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!k39g2000hsf.googlegroups.com!not-for-mail
From: glaroc <glaroc@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Intersect circle and irregular shape
Date: Wed, 9 Jan 2008 09:46:37 -0800 (PST)
Organization: http://groups.google.com
Lines: 68
Message-ID: <cfe96c89-937d-4cd8-be63-ed7ceb3607fa@k39g2000hsf.googlegroups.com>
References: <66c9ae27-c839-41e2-a9a3-d5dcc7f311a7@i12g2000prf.googlegroups.com> 
NNTP-Posting-Host: 142.157.84.29
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1199900799 27339 127.0.0.1 (9 Jan 2008 17:46:39 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Wed, 9 Jan 2008 17:46:39 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: k39g2000hsf.googlegroups.com; posting-host=142.157.84.29; 
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux x86_64; en-CA; rv:1.8.1.11) 
Xref: news.mathworks.com comp.soft-sys.matlab:445067


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@gmail.com> wrote in message <66c9ae27-c839-41e2-
> a9a3-d5dcc7f311a7@i12g2000prf.googlegroups.com>...
> > 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