ScratchData LogoScratchData
Back to gtoal's profile

Polygon filler by decomposition into quads

GTgtoal•Created March 6, 2015
Polygon filler by decomposition into quads
6
3
264 views
View on Scratch

Instructions

Click the green flag and move the vertices by dragging them with your mouse. Works for convex and concave but not self-intersecting polygons. Currently some self-intersecting shapes generate subdivisions that are not quads. This is fixable (by adding points to each line where any two lines intersect, using https://scratch.mit.edu/projects/51321032/ ), but for now only use this on polygons that are not self-intersecting.

Description

PianoApprentice did the hard work. I just tweaked it to show the axis-aligned quads that need to be drawn in order to fill it. (Also axis-aligned triangles, but those are just quads with either the upper two or lower two vertices on top of each other) A suitable quad filler can be found at http://scratch.mit.edu/projects/50085012/ TO DO: fix self-intersecting shapes; possibly optimize by removing unnecessary splits caused by concave shapes if that isn't too expensive to calculate. I've just now written a line intersection algorithm, which is what is needed for the self-intersection problem... http://scratch.mit.edu/projects/51321032/

Project Details

Project ID51071894
CreatedMarch 6, 2015
Last ModifiedAugust 16, 2015
SharedMarch 6, 2015
Visibilityvisible
CommentsAllowed

Remix Information

Parent ProjectView Parent
Root ProjectView Root