Как мне реализовать теорему о шнурках, чтобы найти области множественных выпуклых многоугольников, созданных из пересекающихся линий?
Я создаю фрагмент кода JavaScript, где необходимо идентифицировать каждый многоугольник, созданный из числа случайно сгенерированных пересекающихся линий. Следующий скриншот даст лучшее объяснение того, о чем я говорю:
Теперь мне нужно вычислить площадь каждого полигона и вернуть наибольшую площадь. Подход, который я использую, состоит в том, чтобы идентифицировать каждое пересечение (обозначенное красными точками) и рассматривать их как вершину любого полигона (ов), к которому они принадлежат. Если я могу каким-то образом определить, к какому полигону (ам) принадлежит каждая вершина / пересечение, то расположить вершины каждого полигона по часовой стрелке, тогда было бы просто применить теорему о шнурках, чтобы найти площадь каждого полигона.
Тем не менее, я боюсь, что я полностью потерян и попробовал различные (неудачные) методы для достижения этой цели. Каков наилучший способ составить список вершин по часовой стрелке для каждого многоугольника? Я работаю над тем, какие сегменты связаны с каждым конкретным перекрестком, и я думаю, что это шаг в правильном направлении, но я не знаю, куда идти дальше. Это требует какой-то векторной работы?
2 ответа
Я могу думать об одной возможности. Здесь я обозначил каждую из вершин.
Я предполагаю, что если вы знаете задействованные линии и их пересечения, вы можете найти все отрезки, которые пересекаются в определенной точке. Итак, давайте начнем с определенной точки, скажем, Kи направленный сегмент, IK, Теперь у нас есть четыре направленных сегмента, которые ведут с конца этого, KI, KJ, KL, а также KM, Нас интересуют только те два, которые ближе всего, но не на линии KI, Давайте сосредоточимся на KMхотя вы можете сделать то же самое с KJ,
(Обратите внимание, что если в точке пересекаются более двух линий, мы все равно можем найти две, которые находятся ближе всего к линии, обычно одна формирует положительный угол с начальным сегментом, а другая - отрицательную.)
Мы замечаем, что IKM положительный угол, а затем изучить сегменты, содержащие Mвыбирая тот, у которого наименьший положительный угол KM, в этом случае MF, сделайте это снова в F (хотя здесь есть только два варианта), чтобы получить FG, а потом GH, а потом HI, который завершает один многоугольник, шестиугольник IKMFGH,
Возвращаясь к нашему оригинальному сегменту IK, мы смотрим на наш другой маленький угол, IKJи выполните аналогичный процесс, чтобы найти треугольник IKJ, Теперь мы нашли все полигоны, содержащие IK,
Затем, конечно, вы делаете это снова, каждый другой сегмент. Вам нужно будет удалить дубликаты или быть умнее, если не будете продолжать анализировать путь, когда увидите, что он будет дубликатом. (Каждый угол будет содержать не более одного многоугольника, поэтому, если вы видите уже записанный угол, его можно пропустить.)
Это не будет работать, если ваши полигоны не были выпуклыми, но если они сделаны из линий, прорезанных через прямоугольник, я уверен, что они всегда будут выпуклыми.
На самом деле я не пытался это кодировать, но я уверен, что это сработает.
Два метода, которые я могу придумать, вероятно, не самые эффективные, но должны помочь:
Вы можете вычислить множество точек, которые составляют многоугольник, содержащий произвольную точку, нарисовав воображаемую линию от произвольной точки до каждой другой точки, те, которые рисуют линию, не пересекающую какие-либо линии в вашем изображении, являются вершинами, которые делают выпуклый многоугольник, который вам небезразличен. Проблема этого метода в том, что я не могу придумать какой-либо особенно хороший метод для надежного получения всех полигонов (поскольку вам достаточно только самой большой, возможно, случайной / периодической выборки?)
Для каждого возможного многоугольника проверьте, есть ли какой-либо отрезок, который лежит внутри этого многоугольника (отрезок, который делит пополам 2 ребра многоугольника), и если есть, удалите этот многоугольник из вашего набора. В конце вы должны остаться только с теми, кто вам небезразличен. Этот метод очень медленный, хотя. Если мои объяснения были неясны, я могу обновить с парой фотографий, чтобы помочь объяснить.
Надеюсь это поможет!