[geos-devel] Re: Computational Geometry Problem

[Sanak]

Hi Jo,

I think Angle bisector approach is the simplest way for computing incenter
of an irregular complex polygon. (but may be non-robust.)
The following steps is only my assumption.

1. compute orientation of polygon to know which side is inside.
 - GEOS/JTS "algorithm.CGAlgorithms.isCCW" method is useful.

2. compute angle bisector of every continuous three points in polygon as
ray.
 - JTS "geom.Triangle.angleBisector" method may be useful.

3. get intersection points of angle bisectors.
 - Sorry, I couldn't find the method that compute intersection
points(noding) of rays(not line segments) in GEOS/JTS, but I think this
algorithm is not so difficult.

4. exclude points that are outer of polygon.
 - GEOS/JTS relate operation (like within/covers ..) is useful.

5. compute distance from every candidates of centres to polygon, and choose
largest one.
 - GEOS/JTS distance operation is useful.

Regards,

Sanak.

2009/6/29 Jo <doublebyte at gmail.com>

> You are totally right, and I can see in some cases, the algorithm is unable
> to find the right candidate to centre, searching only among the Voronoi
> vertices.
> Anybody has any suggestions for choosing the candidates of centres for the
> maximum "circumscribed circle"? It does not need to  touch all vertices, but
> it needs to be the largest circle
> that fits inside the polygon.
> And btw, is an irregular complex polygon...
>
>  cheers,
>
>          Jo
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20090630/1fa5adf8/attachment.html