3
votes

Using Java, I would like to calculate the alpha shape: given a set of 2D points, I want to find a list of polygons with minimal area that contain all the points. Here is some more information. A pure Java solution would be ideal. Code that I can port from other languages to Java would be fine. I'd rather not use a native wrapper. An explanation of the algorithm that I could implement with reasonable effort would also be fine.

What I really need are the triangles that make up the alpha shape polygons, so extra credit for that.

2

2 Answers

6
votes

This page has a nice Java applet with GPL source that does what you want. There's also the full paper describing the algorithm further down.

It doesn't do the triangle tessellation part, but there are many available libraries for that once you have a polygon. If nothing else, openGl has an excellent tessellator you can use or pull from.

0
votes

I'm not sure if these are the applet and papers described by @Geobits, but there are an applet and some papers that can now be found at this link.

However, that's just the beginning of your problem. Most modern browsers won't support Java applets. This is due to stuff about NPAPI and security; for details, see e.g. the link preceding this sentence. This lack of default support happened around fall 2015.

Rather than detail the full solution, I suggest you visit Oracle's descripton of how to get applets to run. It shows how to enable Applets in Internet Explorer (IE), Firefox, and Safari (I have no idea about Microsoft Edge).

You can no longer even enable Java in Chrome. One work-around basically emulates IE in Chrome. It's described here.

Note that I tested this applet using the methods described on IE and Firefox, both run on Windows 10. I had to change the Java security settings as described in the next paragraph. For IE, the applet came up just fine. For Firefox, I had to click on the button that looks like a lego in the upper-left. Part of the applet worked, but I couldn't get it to allow me to insert points.

Believe it or not, that's still not the end of it. You'll also need change the Java security settings so that the site in question can run Java. Once again, Oracle has an article describing that. Look for the screenshot with the Exception Sites List section and, when you get to that point on your computer, press the Edit Site List button and follow the prompts. You want to add http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html to list list of excepted sites.

One other option is going to:

http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/

and downloading alpha.zip. You can also just go straight to the download link:

http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.zip

Navigate into the directory where you downloaded it, extract the contents, go to the new alpha directory, and run

appletviewer Alpha.html

You will, however, need to find an earlier version of Java - preferably Java 1.1, but I think anything before Java 5 will work.

Good luck getting it to run!


More info:

https://blog.mozilla.org/futurereleases/2015/10/08/npapi-plugins-in-firefox/

Mozilla intends to remove support for most NPAPI plugins in Firefox by the end of 2016. Firefox began this process several years ago with manual plugin activation, allowing users to activate plugins only when they were necessary. This decision mirrors actions by other modern browsers, such as Google Chrome and Microsoft Edge, which have already removed support for legacy plugins.

http://www.ghacks.net/2016/04/11/firefox-drm-and-the-end-of-npapi/

The most popular plugins currently supported are Adobe Flash and Java, but there are more plugins that Firefox may pick up to make their functionality available.

Google kicked NPAPI out in Chrome 45 when it stopped support for NPAPI, and Mozilla announced that it would end support as well.

Google's advantage over Mozilla is that Chrome ships with a version of Flash built-in to the browser which means that the most popular NPAPI plugin is still available in Chrome, albeit in a different form.

...

Up until now, Mozilla stated that support for NPAPI would end at the end of 2016 but did not reveal exactly when it would happen.

A post on Mozilla.dev.tech.plugins in February revealed updated plans. According to the information posted there, Mozilla plans to remove NPAPI support in Firefox 53 which will be out in April 2017.

The next Firefox ESR (Extended Support Release) version is 52 and will receive security updates for a year. By removing NPAPI in Firefox 53, the release after the ESR, users that need NPAPI support can continue to switch to Firefox ESR 52 and keep using NPAPI plugins until May 2018.

The main reason why Firefox 53 is picked is that Firefox 52 is a new ESR release. This means that anyone on ESR will be able to use NPAPI plugins until that version is no longer used and that is not before May 2018.

https://java.com/en/download/help/firefox_java.xml

https://support.mozilla.org/en-US/questions/975269

http://news.softpedia.com/news/flash-npapi-support-to-be-removed-in-firefox-53-503777.shtml