2 replies to this topic

[cesarone82]

Hi all,

I need an alghoritm which can slice a polygon into subpolygon, maybe a recursive one. I was initially thinking of using mesh subdivision, the problem is that each slice has properties depending on the distance from an axis, so that having triangles would increment considerabily the amount of entities (useless).

These are the steps:

1) define a cloud of points;
2) determine the convex hull (i use triangle library for this)
3) divide recursively the polygons (slice based on a line)

Here is a sketch example (attached)

Does anybody know a library, possibly c or c++ which can do this?

Attached Files

•  pslyce..jpg   99.32K   67 downloads

[cesarone82]

well sorry, this is not exaxtly the convex hull, but the problem is slicing.

[Momerath]

The source code for Doom has a good algorithm for slicing shapes. The goal of their algorithm, though, was to ensure that every point in a region is visible to every other point. Not sure if that helps you at all :)