Combine Nearest Convex Polygons

Question

I have an array of pointclouds (a cluster of points that have been determined to be in their own region).

The goal is to combine these individual clusters that are either

i. Intersecting

ii. Within some minimum distance from eachother

Check ii makes this more difficult. In order to deal with these pointcloud's quickly, I am creating AABB (axis aligned bounding boxes which are aligned along the X axis).

My current method is to use some properties of the Separating Axis Theorem:

Create AABB for each pointcloud
For each AABB, check if they are overlapping by projecting these onto a random axis and then sorting these linear projections by where they fall on this line o(nlog(n)). I then walk through this list to check for intersections O(N) using the SAT. Most AABB's linear projections will not overlap and are therefore not intersecting, and the ones that do I can check manually (because no overlap in 1D guarantees no intersection, but the converse is not true).

The last part is where I am stuck. The above 1D projection was done to avoid O(n^2) pairwise checks for intersections. But in order to combine the convex polygons that are within a certain threshold but NOT intersecting, I can't see a way around an O(N^2) pairwise check.

Is there a way to construct some tree or graph to combine all convex polygons that are within a certain distance to eachother without checking each pairwise combination?

If use you use my steps from 1 & 2, you can assume the remaining pointclouds/AABB are NOT intersecting.

EDIT

A potential solution would be to add the threshold/2 to the AABB width and height, and check for intersections. If they intersect, then I can check for both actual intersections (which is fast for AABB), and the minimum distance between the two.

An axis aligned bounding box (alligned along the X axis). studiofreya.com/3d-math-and-physics/… — DaynaJuliana
I think your question sounds too fancy, which also implies confusing. Basically you are checking if regular boxes are too close to each others, but you have not defined boxes as individual points in cluster (pointcloud you said) or center of the cluster with its radius being the threshold in your question. Can you clarify the description of your problem? Nice job AABB:D — Mai
Yes. I am adding AABB (axis alligned bounding boxes) to these point clouds. I want to check for intersections, or if any box is within a minimum distance from another box. I can do the first part of this in nlogn. The 2nd part I cannot do without N^2 solution. I tried to make this more clear though ! — DaynaJuliana
Have a look at this. And if you are lazy like me you can use this. Also for a giggle you can look at this Thank you for the question I learnt a lot. GJ AABB. — Mai

DaynaJuliana DaynaJuliana · Accepted Answer · 2016-03-28T05:06:28

I ended up using the normal of my random axis, and checked for both overlaps in 1D in both directions which speed up my algorithm considerably (removed slowdown if there was clustering along one axis).

For the distance threshold, the minimum the AABB distance padding on all sides needed to guarantee an intersection was A/2. This captures all cases where the AABB are seperated only in the x or y direction ( the diagonal case requires A*sqrt(2)/4)

Combine Nearest Convex Polygons

2 Answers