Hi Jo,<br><br>I think Angle bisector approach is the simplest way for computing incenter of an irregular complex polygon. (but may be non-robust.)<br>The following steps is only my assumption.<br><br>1. compute orientation of polygon to know which side is inside.<br>
- GEOS/JTS "algorithm.CGAlgorithms.isCCW" method is useful.<br><br>2. compute angle bisector of every continuous three points in polygon as ray.<br> - JTS "geom.Triangle.angleBisector" method may be useful.<br>
<br>3. get intersection points of angle bisectors.<br> - 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.<br>
<br>4. exclude points that are outer of polygon.<br> - GEOS/JTS relate operation (like within/covers ..) is useful.<br><br>5. compute distance from every candidates of centres to polygon, and choose largest one.<br> - GEOS/JTS distance operation is useful.<br>
<br>Regards,<br><br>Sanak.<br><br><div class="gmail_quote">2009/6/29 Jo <span dir="ltr"><<a href="mailto:doublebyte@gmail.com" target="_blank">doublebyte@gmail.com</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<span style="border-collapse: collapse;"><div>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.</div>
<div>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</div><div>that fits inside the polygon.</div>
<div>And btw, is an irregular complex polygon...</div><div> cheers,</div><div> Jo</div>
</span></blockquote></div><br>