Вычислить пересечение нескольких 2D-фигур в Java

Question

Обратите внимание: Я не заинтересован в использовании каких-либо сторонних JAR или AWT в качестве части этого решения. Я делаю все, что в моих силах, чтобы сохранить зависимость от проекта, и я хотел бы сохранить его таким образом. И, если JRE поставляется с любыми классами, которые решают это для меня, меня все еще интересует пользовательское решение, чтобы я мог действительно понять математику, а не просто слепо сделать несколько вызовов API.

я иметь следующую структуру POJO для различных форм:

public class Coordinate { 
    private Double xVal; 
    private Double yVal; 

    // Constructors, getters/setters, etc. 

    public static Double distance(Coordinate c1, Coordinate c2) { 
     // Calculates the Cartesian distance between c1 and c2 using the standard 
     // distance formula. 
    } 
} 

public abstract class Shape { 
    // Some properties inherent to all 2D shapes. 

    public abstract Double calcArea(); 
    public abstract Double calcPerimeter(); 
} 

public class Rectangle extends Shape { 
    private Coordinate upperLeft; 
    private Coordinate upperRight; 
    private Coordinate lowerLeft; 
    private Coordinate lowerRight; 

    // Constructors, overrides, getters/setters, etc. 
} 

public class Circle extends Shape { 
    private Coordinate center; 
    private Double radius; 

    // Constructors, overrides, getters/setters, etc. 
} 

Теперь то, я будет дан List<Shape> (смешанный набор, содержащий 0+ Rectangle с и 0+ Circle S). Мне нужно, чтобы определить, есть ли какой-либо из форм в этом списке пересекаются друг с другом (истина или ложь):

public boolean intersectionsExist(List<Shape> shapes) { 
    // ??? 
} 

Я хотел бы реализовать лучшие практики здесь, так что я не знаю, есть ли уже какой-либо алгоритм для этого с (потенциально) десятками фигур. Все фрагменты кода обнаружения пересечений, которые я нашел на SO и в Интернете, были между двумя формами. Но что, если у меня есть 3 прямоугольника и 7 кругов в списке?!?

Мое мышления перебирать каждый Shape в списке, и сравнить его с любым другой Shape (отсюда решением квадратичной, который я не в восторге). Но таким образом я мог бы вернуть true в тот момент, когда я нахожу Shape, который пересекает с другим.

Что касается обнаружения фактического пересечения, мне интересно, есть ли что-нибудь, что я могу сделать, что касается этих фигур, таких как диаграмма Венна. Смысл, как-то определить, является ли одна форма перекрытием другой. Но как я мог определить «перекрытие», я понятия не имею.

Так несколько вопросов:

1. Существуют ли какие-либо стандартные алгоритмы там для обнаружения пересечений между 3+ форм? Если да, может кто-нибудь, пожалуйста, дайте мне некоторые ссылки/информацию о них?
2. Если ответ на № 1 выше «нет», то это мое квадратичное решение выше наилучшего пути (двухполюсный for -loops, сравнивающий каждый Shape друг с другом и возвращающий true, когда обнаружено одно пересечение)? Или есть лучший/более эффективный способ?
3. Самое главное: как определить фактические пересечения? Существуют ли стандартные алгоритмы для этого (ссылки?)? Может ли кто-нибудь представить пример кода (используя мои POJO выше) или даже дать простой пример псевдокода того, что я могу здесь сделать?

Заранее благодарен!

Answer 1

Существуют различные решения для обнаружения столкновений.Вы можете обрабатывать обнаружение в огромном массиве объектов, например, в современных играх и тысячах моделей, но вы всегда сравниваете столкновение по двум предметам за раз

Самый быстрый и простой в использовании код - использовать круги, которые охватывают ваши объекты (очень просто, если ваш объект является круглым) и используйте тест расстояния между ними. Если расстояние между центральными точками двух окружностей меньше их комбинированных радиусов, то они сталкиваются.

Этот параметр имеет некоторые недостатки, такие как круг на прямоугольном объекте, либо столкнется в некоторых областях, где прямоугольник не нарисован (если круг больше прямоугольника) или не будет сталкиваться в несколько раз должен (если круг меньше прямоугольника).

Некоторые другие вещи, на которые вы можете обратить внимание, - это коллизионные боксы с осевым или столкновением n-DOP, оба из которых несколько более математически интенсивные. Вот хороший general collisions tutorial

Если вы хотите получить чрезвычайно сложными и Mathy, вот метод, известный как SAT (Разделительный ось теорему) http://www.metanetsoftware.com/technique/tutorialA.html

Answer 2

Ваша проблема обычно называется Constructive Solid Geometry. Поиск Wikipedia и/или стандартная книга о компьютерной графике, но, пожалуйста, не ожидайте, что рабочий код об этом сложном материале будет готов к использованию.

Answer 3

Если вы заинтересованы в теории пересечений, есть анализ проблемы в статье Хазель и Добкина Принстона ^†. Документ слишком длинный, чтобы суммировать здесь, но он обеспечивает длительный пошаговый алгоритм с доказательствами. Вам все равно придется самому закодировать алгоритм. Тем не менее, OP сделал запросить ссылки и/или ссылки.

^{† Chazelle, B., and Daniel P. Dobkin. Intersection of Convex Objects in Two and Three Dimensions. Принстон, Нью-Джерси: Принстон У, кафедра компьютерных наук, 1986. Web.}