0

I need to identify adjacent shapes in an SVG drawing where the definition of adjacent is: two shapes A and B are adjacent if more than one point on the path defining shape A is closer than e (an arbitrary threshold) to a point on shape B.

See image below - shape 1 is adjacent to shape 2, and shape 2 is adjacent to shape 3, while shapes 1 and 3 are not adjacent.

enter image description here

The image represents a tile, the production process of which does work if two adjacent shapes are made from the same color. For the curious, see the video for a look at the production process.

Short of coding things by hand, how can I check if two shapes are adjacent, so that I can ensure that (in an app) they won't be colored in the same way?

I have thought of 2 approaches:

  • enlarge the shapes by a certain amount (by offsetting them, for example) and then see if they overlap with each other
  • divide the image in a grid of small squares and check if any square contains more than shape

I expect that grid size or offset parameters will have to be set carefully to avoid that shapes 4 and 5 are identified as adjacent.

Is there a better approach than these two?

I plan to build this in SVG + javascript, using paper.js for calculating overlaps.

simone
  • 4,667
  • 4
  • 25
  • 47
  • You'll want to very ridigly define what you mean with "adjacent", first, because 4 is not adjacent to 5 in your image at all. It's "near" 5, but it's _adjacent_ to the element it's actually located in: all its edges touch that shape, not shape 5. Also, your post currently claims that "shape 1 is adjacent to shape 2" _and_ that "shapes 1 and 2 are not adjacent" so that's not helping anyone understand this problem description... – Mike 'Pomax' Kamermans Nov 20 '19 at 22:35
  • @Mike'Pomax'Kamermans - thanks, fixed the typo. My best shot at the definition is: two shapes A and B are adjacent if more than one point on the path defining shape A is closer than e (an arbitrary threshold) to a point on shape B. However, for the sake of speed, I was trying to avoid having to calculate all pairwise distances between points sampled on the two paths. BTW - thanks for the tutorials and library – simone Nov 20 '19 at 22:47
  • Please put that definition in your post, so that people understand what you've tried to formalize, so that you can implement that formal definition. As for doing that by hand: doesn't paper.js already have a distance function to give you the minimum distances between two arbitrary shapes? – Mike 'Pomax' Kamermans Nov 20 '19 at 22:48
  • @Mike'Pomax'Kamermans - done. paper.js has a function that returns the nearest point on a path to a specified point - not minimum distance between shapes – simone Nov 20 '19 at 22:57
  • ah, shame. Though iat this point you've effectively reduced your problem to https://stackoverflow.com/questions/32646551/calculate-minimum-distance-between-two-arbitrary-shape (sure, it's java, but a solution for java is trivially adapted to anything from C to Perl to JS) – Mike 'Pomax' Kamermans Nov 21 '19 at 04:16

0 Answers0