PaperJS-based Minimum Convex Polygon


Even though I’m at home sick today (or maybe due to the boredom of it), I’ve been working on improving my PaperJS-based minimum convex polygon (MCP) script (now found here, previously found here). Now, the algorithm is as follows:

  1. Find the point that is the farthest right
  2. Draw a large circle that encompasses the entire possible field, centred on that point. My circle has a radius of 720px (the field is 500x500px). The circumference of the circle is split every 18px. When those vertices are connected to the centre, there are 252 spokes.
  3. Loop through the spokes, starting with the spoke pointing straight down and moving clockwise. Does the spoke pass through another point (within 5px)? No? Move to next spoke. Yes? Connect the circle centre on that point (a new boundary line of the MCP), move the circle and all spokes to that point. Continue with next spoke to find the next MCP boundary point.

This method isn’t perfect, but it works fairly well. Problems arise when two or more points fall within the tolerance of the spoke hittest (5px). But like I said, I’m sick, so instead of fixing it, I’m going to watch Community.

edit: I’m very grateful to SparkGeo’s lab, which finally clued me in to how to interact with a map underneath a canvas element. Hint: canvas CSS = “z-index: 1; pointer-events:none”


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s