Ghoul Fool - 6 months ago 35

Javascript Question

I'm looking for an algorithm or tried & tested method for analyzing irregular polgygons and reducing them to primitives (squares, rectangles, trapeziums). A way of recurrsively looking over shapes to determine the best fit for regular polygons.

see image blow

The black shapes are the irregular polygons and the blue depicts the desired regualar, which fits inside. The left example should be straight forward but that's because it's a case of finding the a rectangle that can fit in the largest shape. The polygons will be of an undetermined size (but let's say they have less then 32 sides) What I'm hoping for is to be able to break up polys into several regualar ones - which is where I'm a little lost.

Sadly, I've no code at this point as I'm stuck to know the best way forward. The script will be done in pure JavasScript. This isn't homework :)

Answer

First of all, you need to check whether your polygon is convex or concave. If it is the latter, then you need to view it as several convex polygons "put together" and handle them separately. (It is easy to your mind to imagine a large pair of scissors which cuts the polygon into several smaller polygons). When this is done, you either have a single polygon, or several polygons.

For each polygon, calculate the gravity point of the polygon and (P(i), P((i + 1) mod n), G) will form a trivial form, a triangle. These triangles will solve your problem.

If you need shapes with four angles, then four consecutive points form a shape of four angles. But this approach might leave you with a smaller polygon with lesser number of angles in the middle of the main polygon, which will have to be handled.