Я работаю над небольшой библиотекой игровой геометрии, и среди множества других методов я хочу найти середину пересечения круга и прямоугольника. Однако мне сложно придумать для этого быстрый алгоритм. Кто-нибудь знает хороший алгоритм для этого?
Я готов пожертвовать идеальной точностью, если это означает, что алгоритм будет значительно быстрее.
Я представляю каждую форму в основном:
Круг:
- float x, y (в центре)
- поплавок r (радиус)
Прямоугольник:
- float x, y (в центре)
- float w, h (значения ширины и высоты, они представляют собой расстояние по осям x и y от центра до соответствующего края).
РЕДАКТИРОВАТЬ:
Поскольку, похоже, возникла путаница по поводу того, что я имею в виду под «средней точкой», позвольте мне уточнить:
Учитывая, что круг и прямоугольник пересекаются, существует область, созданная их перекрытием. Я хочу определить географический центр этой области (либо точно, либо определить приблизительно).
Пример: http://en.wikipedia.org/wiki/Centroid.
РЕДАКТИРОВАТЬ № 2:
Вы, ребята, поделились со мной некоторыми идеями, позвольте мне поработать над реализацией некоторых из них, и я вернусь к вам.
Заключительные мысли:
Я пометил ответ Гарета как принятый, потому что он дал мне идеи относительно того, что я в конечном итоге использовал, но моя окончательная реализация отличается от его, поэтому я объясню это здесь.
Я придумал два общих способа сделать это: один, который был бы полностью точным (но требовал более сложного программирования и большего количества математики), и другой, более простой / быстрый способ, который всегда был довольно близок. Я остановился на последнем, но вот два метода:
Метод 1. Фрагментация формы:
По сути, идея состоит в том, чтобы разбить перекрывающуюся область на отдельные сегменты, для которых можно легко вычислить их среднюю точку и площадь, а затем взять средневзвешенное значение для всего результата.
В показанном здесь примере есть три части: центральный прямоугольник, занимающий большую часть площади, и два изогнутых сегмента для краев круга.
Метод 2: интерполяция строк
Во-первых, вам нужно вычислить точку в прямоугольнике, которая будет базовым местоположением. Это должна быть точка, которую легко вычислить, и она должна совпадать. Для этой точки я использую среднее значение всех пересечений краев круга и прямоугольника (если пересечений краев не существует, я по умолчанию использую расположение круга, поскольку это означает, что одна форма содержится внутри другой).
Вычислите линию между центром круга и этой точкой. Затем вычислите сегмент, который находится в перекрывающейся области. Середина области берется за середину этого отрезка линии.
Этот метод неточен, но всегда создает точку внутри обоих объектов, а результирующая точка, как правило, находится близко к середине (так что обычному глазу она "выглядит" хорошо). Кроме того, это намного проще и быстрее, поэтому я пошел с этим.
