1

Given a list of coordinates (x, y) that form up polygons is there a specific algorithm/s that can be used to find the number of separate polygons "not colliding polygons" that these points create?

And if there is no algorithm/s what would be the most efficient way to calculate these separate polygons?

I have tried using SAT but the performance is bad, since i have to create each individual polygon and check it for collision against every other polygon.

To illustrate what i want to ultimately achieve, in the following picture you can see the polygons that i'd like to calculate/find which are in some cases comprised of connecting squares.

enter image description here

Also note that i actually start with x, y coordinates for the center of a square and based on a radius i calculate corner points, so i have access to both methods, but mainly opted for the corner points for SAT.

P.S. i'm doing this in lua, but would happily accept any code samples/solutions in other languages.

Amr Abed
  • 31
  • 1
  • 5
  • Can the squares overlap by more than just the edge? – ryanpattison Aug 18 '15 at 13:30
  • Yes squares can be interesicting by more than just the edge, and one square can be overlapping two or more different sqaures, but in these cases we are really only interested in the outline, so any points that are within an existing polygon can be discarded. – Amr Abed Aug 18 '15 at 13:40

2 Answers2

2

Fast sweep-line algorithm are described in these papers:

lhf
  • 70,581
  • 9
  • 108
  • 149
  • Thanks, I did some reading on this and i'm not sure i understand how this algorithm helps with my case, care to elaborate a bit? – Amr Abed Aug 18 '15 at 13:41
  • @AmrAbed, the number of separate polygons is the number of connected components. – lhf Aug 18 '15 at 16:09
0

Put all the edges of every polygon in a hash table with the edge as the key (specifically the key will be the two corner points which the edge connects, in sorted order) and the polygon identifier as the value. When adding an edge to the hash-table, just check if an identical edge already exists (same key). This would let you find the duplicate/shared edges.

gen-y-s
  • 871
  • 6
  • 12
  • 1
    Yes. But that doesn't work for the group of amber squares, where the bottom square has no common nodes with the top squares. (Maybe you could create a mesh of triangles and split them in such cases.) – M Oehm Aug 18 '15 at 07:33
  • In that case you would define an "equals" predicate method for the hash-table, which will return true if and only if the two edges overlap: http://stackoverflow.com/questions/17148839/overlapping-line-segments-in-2d-space – gen-y-s Aug 18 '15 at 08:04
  • I don't see how that should work. If you go away from discrete points, you can't use a hash table. – M Oehm Aug 18 '15 at 08:25
  • Actually, you would also have to write a custom hash function to make sure overlapping edges have the same hash code. A simple suggestion would be to compute the hash based on the (infinite) line on which the edge lies. The line can be characetrized by its angle with the x-axis and the x-coordinate where it crosses the x-axis. – gen-y-s Aug 18 '15 at 09:35
  • Good luck with that. (By your hash logic, axiliniear but otherwise unrelated lines such as the top lines of the green and blue squares above will have the same hash code. And horizontal lines don't intersect the x axis, unless they coincide with it.) – M Oehm Aug 18 '15 at 09:56
  • Well, I suggested hash table because I thought the problem was to find identical edges. But since we're now talking about partially overlapping edges (a relationship between edges, not a simple identity), it might be better to use a different data structure, which could implement the relation logic (for example, R-tree). Although the hash-table idea could still be made to work and give a satisfactory solution in most situations. – gen-y-s Aug 18 '15 at 10:12
  • I guess the term "not sharing any edges" in the original question is what cause the confusion, because it implies two polygons having the same edge, but the question is really to find polygons with partially overlapping edges. – gen-y-s Aug 18 '15 at 10:17
  • I think the hash-table approach is basically good, but the idea to make the hash table do the work of partial matching is not. You could create numbered nodes from the coordinates and merge identical nodes with a certain tolerance. When a node is on an existing line (again, within a certain tolerance), create a new node and split the adjacent polygon. That is: Make a triangle mesh of the polygons first, then use your approach. If the problem is big enough, you will need data structures that enable fast proximity searches, of course. – M Oehm Aug 18 '15 at 10:27
  • Yeah the main issue here is the polygons don't have unoform shapes, sorry if my wording was confusing but when i said "not sharing edges" i just meant i needed to find polygons that are not connected. – Amr Abed Aug 18 '15 at 11:38