How to derive minimum bounding convex polygon?

chrisjj · Postby **chrisjj** » Tue Mar 05, 2013 11:00 pm

How may I automatically derive the minimum bounding convex polygon of an object?

E.g. the transparent blue object derived from the red object underneath, here:

And if Inkscape can't do this, can anyone suggest an SVG editor that can?

Thanks.

Lazur · Postby **Lazur** » Wed Mar 06, 2013 3:07 am

I was about to say that I don't know about any automatic way, but searching the "minimum bounding convex polygon of an object" of your question pointed here:
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00170000003q000000
where they posted python sources for that function of their business map program.

Code: Select all

# Name: MinimumBoundingGeometry.py
# Description: Use MinimumBoundingGeometry function to find an area 
#              for each multipoint input feature.
# Author: ESRI

# import system modules 
import arcpy
from arcpy import env

# Set environment settings
env.workspace = "C:/data"

# Create variables for the input and output feature classes
inFeatures = "treeclusters.shp"
outFeatureClass = "forests.shp"

# Use MinimumBoundingGeometry function to get a convex hull area
#         for each cluster of trees which are multipoint features
arcpy.MinimumBoundingGeometry_management(inFeatures, outFeatureClass, 
                                         "CONVEX_HULL", "NONE")

This seems to be a good material to write an extension that does automatically derive the minimum bounding convex polygon of a path.

chrisjj · Postby **chrisjj** » Wed Mar 06, 2013 3:22 am

Thanks L, but I think they have not provided the definition of the function.

ragstian · Postby **ragstian** » Wed Mar 06, 2013 7:09 am

Hi.

Have a search for; "convex hull python".
http://code.activestate.com/recipes/66527-finding-the-convex-hull-of-a-set-of-2d-points/
http://www.scipy.org/Cookbook/Finding_Convex_Hull
http://en.literateprograms.org/Quickhull_%28Python,_arrays%29

Start Coding - the race is on!

RGDS
Ragnar

chrisjj · Postby **chrisjj** » Wed Mar 06, 2013 7:39 am

ragstian wrote:Start Coding - the race is on!

Thanks. I'll camp by the finish line

ragstian · Postby **ragstian** » Thu Mar 07, 2013 6:24 am

Hi chrisjj

chrisjj wrote;

ragstian wrote:
Start Coding - the race is on!

Thanks. I'll camp by the finish line

Still camping?

Here are version 0.01 of my ConvexHull extension;
See atthed file; ConvexHull.zip
(Download the file and Unzip to inkscape/share/extension folder.)
The code is mostly "lifted" from other extensions -
(ExportXY - by Simarilius on this forum - and Eggbot Twist - by Daniel C. Newman).
Python Q_hull routine from here; https://github.com/flengyel/REST/blob/master/quickhull.py

Objects has to be paths, does not yet work on groups. Only path nodes are taken into consideration - will not work on circle outlines etc.
The returned object is simple with a stroke of one pixel and no fill.

Yellow + Pink --> Convex hull = Blue
(Blue fill added for clarity)

RGDS
Ragnar

~suv · Postby **~suv** » Thu Mar 07, 2013 8:01 pm

ragstian wrote:Objects has to be paths, does not yet work on groups. Only path nodes are taken into consideration - will not work on circle outlines etc.
The returned object is simple with a stroke of one pixel and no fill.

Nice :-)

A bonus feature would be to insert the resulting convex hull path into the current layer (append to current group (may be a layer or a regular group), or to the parent group (layer or regular) of the last selected object (in stack order)) - currently the path is generated outside the layer structure (in 'root').

ragstian · Postby **ragstian** » Fri Mar 08, 2013 4:13 am

Hi ~suv

~suv wrote;

A bonus feature would be to insert the resulting convex hull path into the current layer
(append to current group (may be a layer or a regular group), or to the parent group (layer or regular)
of the last selected object (in stack order)) - currently the path is generated outside the layer structure (in 'root').

Working on your suggestion - the learning curve writing extensions is steep!!

Thanks for the feedback - it's appreciated!

RGDS
Ragnar

chrisjj · Postby **chrisjj** » Wed Mar 20, 2013 4:32 am

Excellent - thanks Ragnar. It is working well here.

I neat addition would be the option to work separately on selected paths i.e. 1:1 . Then I could do 100 objects separately in one operation.

This is a read-only archive of the inkscapeforum.com site. You can search for info here or post new questions and comments at inkscape.org/forums

This is a read-only archive of the inkscapeforum.com site. This feature is no longer available.

InkscapeForum.com

How to derive minimum bounding convex polygon?

How to derive minimum bounding convex polygon?

Re: How to derive minimum bounding convex polygon?

Re: How to derive minimum bounding convex polygon?

Re: How to derive minimum bounding convex polygon?

Re: How to derive minimum bounding convex polygon?

Re: How to derive minimum bounding convex polygon?

Re: How to derive minimum bounding convex polygon?

Re: How to derive minimum bounding convex polygon?

Re: How to derive minimum bounding convex polygon?

Who is online