If you haven't seen it, this might give you some leads.

For efficient implementations, your best bet is to seek out game writers and 3D collision detection algorithms.

Do you have any sample datasets?

I have been looking into 3D collision detection, but found that it mostly included using bounding boxes, which are not ideal for oddly shape molecules.

SVMs look very promising, as I only ever need to do the training case because I know which set my data points belong to.

As for data sets, they are merely several lists of the xyz coordinates of atoms in a molecule oriented in 3D.

        ...
44.886 -49.990 3.963
45.086 -50.645 1.973
45.120 -51.934 3.208
43.604 -51.123 2.800
        ...
[download]

I have been looking into 3D collision detection, but found that it mostly included using bounding boxes, which are not ideal for oddly shape molecules.

Yeah. Sorry about that. The only example I found, which you probably already saw, was more collision avoidance in footballing robots. And all the information I read on that was purely theoretical--no code available that I found. Indeed, pretty much everything I read about SVMs is that way; couched in terms and notations designed to impress peer review boards with little or no information or details on practical implementations.

In general with computation geometry algorithms, if it's useful and can be made fast, then the game writers are your best reference for practical implementations. And understandable descriptions. Either they haven't caught on to SVMs yet, or haven't found a way to make them work quickly enough for their needs.

However, don't be too ready to dismiss bounding. Calculating bounding spheres is well studied, and there are algorithms that give exact accuracy; or very fast approximations; or that can approximate fast and then refine incrementally to meet requirements.

And the nice thing about bounding spheres is that they allow your determination to be made very quickly in many cases--bounding sphere don't intersect--and then allow you to focus on a tiny subset of the points within each groups--perhaps just 1 each--to make the determination when they do intersect.

Regarding my request for a sample dataset--or preferably two sets; one with a clear separation plane and one without: it's just that it is an interesting problem (to me). And whilst I can generate test data for my explorations, it is always better to have real data. Invariably whatever you generate randomly omits some constraint or other that exists in the real problem space.

If the datasets are too large to post I'd gladly fetch them or receive them some other way. I don't need any identifying data, just the points themselves?

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP an inspiration; A true Folk's Guy

#!/usr/bin/perl

use strict;
use warnings;
use CPAN;

CPAN::Shell->force('install',

"Algorithm::Cluster",
"Algorithm::ClusterPoints",
"Algorithm::SVM",
"Algorithm::SVMLight",
"Bundle::Math",
"Geometry::Primitive",
"PDL",
"SOOT");
[download]

I will definitely have a look at those modules but I was hoping to try implementing something that is my own first for both the experience and freedom.

... how do you wanna place a line (or plane) between those two molecules?

    X  O       O
 
X       X  O
 
    X  O       O
[download]

or in math lingo: convex or concave hull?

How is the "occupied space" defined?

The molecules would be, ideally, convex hulls. I would define occupied space as the hull in the case. At the moment I would consider the case you presented as an overlap of the two molecules. I merely wish to be able to see if a line (plane) like this is doable

    x  |  o
  x   x|o   o
    x  | o o
[download]

IMHO¹ the surface of a convex hull already describes the (optimal) planes where all atoms of your molecule are on one side of the plane (or of course in the plane).

So your problem reduces to calculate the margins of your convex hull:

At least one edging plane should separate the atoms into distinct groups!

          |
   \      |
    x  /  o   o
  x   x   | o   
    x  \  o   o
   /      |
          |
[download]

Of course, when going into real world physics the distance between two molecules should be bigger than the distance between the atoms, to be considered different molecules. But this can be calculated with those surface planes by adding a tolerance.

IMHO those are too close

    x  |  o
  x   x|o   o
    x  | o o
[download]

I don't know if you need a simple or a fast algorithm, but in many cases you can shorten the cases by approximating a (minimal) sphere which includes all atoms of a molecule.

Only if those spheres (maybe widened by the mentioned minimal distance) intersect you will need to calculate the surfaces of the molecule.

And you will only need to calculate the surfaces close to this intersection.

IMHO this should be considerably fast and intuitive, for further optimization better rely on the WP article on Support vector machines BrowserUK was linking to.

Cheers Rolf

¹) prove should be trivial.

UPDATE: It should be mentioned that IMHO physics knows examples of molecules which are distinct but intersect from a mathematical point of view. Something called bucketball rings a bell for me...