Java: нахождение крайних вершин выпуклого многоугольника - PullRequest
Новая
       39

Java: нахождение крайних вершин выпуклого многоугольника

7 голосов
/ 02 апреля 2012

Исходное сообщение:

Я пытаюсь найти крайние вершины выпуклого многоугольника (относительно точки P вне многоугольника).Пока меня интересуют только прямоугольники (однако мне бы хотелось, чтобы алгоритм работал с любым выпуклым многоугольником).

Point Demonstration

Мой план состоит в том, чтобы построить линию извнешняя точка P до центральной точки C .Из этой справочной линии я построю линии от точки P до точек 1 , 2 , 3 и 4 .Поскольку точки 2 и 4 будут иметь самые большие (самые положительные) и самые маленькие (самые отрицательные) углы от базовой линии , они будут обозначены как крайние вершины .

Это лучший алгоритм для работы?Как один вычислить углы от опорного угла (желательно в Java)

Обновление для уточнения:

1040 *enter image description here 1043 * Я нарисовал линии ( справочная линия в красном).Как видите, линия от P до 2 создает наибольший угол с одной стороны от линии отсчета , тогда как линия от P до 4 создает наибольший угол другой стороны.Следовательно, это крайние вершины .

Ответы [ 3 ]

2 голосов
/ 02 апреля 2012

Это в значительной степени проблема выпуклой оболочки . Вы будете искать набор вершин (x 1 , x 2 ) вокруг многоугольника. Методология, которая будет применяться, называется «быстродействующей оболочкой», аналогичной быстрой сортировке (в которой мы делим нашу область точек каждый раз, когда проходим). Также можно предположить, что P может использоваться в качестве средней точки между произвольной начальной точкой и ее параллельной конечной точкой, поэтому вы получите выпуклую оболочку вокруг P .

Потребовалось бы некоторое время, чтобы создать надежную Java-версию (из моего случая), но я думаю, что статья в Википедии даст вам отличную отправную точку.

0 голосов
/ 17 апреля 2012

Я решил проблему следующим образом: 

            // code simplified for demonstration
            double angleBetweenVertices;
            double maxAngleBetweenVertices;
            vectorA.setStartingPoint(outerPoint);
            vectorA.setTerminationPoint(polygonCenter);
            vectorB.setStartingPoint(outerPount);

            // For each vertex, calculate the angle between the outer point, the polygon's center and the vertex
            for (Point2D.Double vertex : vertices) {    
                vectorB.setTerminationPoint(vertex);
                double angleBetweenVertices = 
                    Math.toDegrees(
                        Math.atan2(
                            (vectorA.perpDotProduct(vectorB)),
                            (vectorA.dotProduct(vectorB)) 
                        )
                    );

                // Update the min and Max
                if (angleBetweenVertices >= maxAngleBetweenVertices) {
                    maxVertex = vertex;
                    maxAngleBetweenVertices = angleBetweenVertices;
                } else if (angleBetweenVertices <= minAngleBetweenVertices) {
                    minVertex = vertex;
                    minAngleBetweenVertices = angleBetweenVertices;
                }
            }
0 голосов
/ 02 апреля 2012

Использование тригонометрии чрезвычайно медленно.Вы должны использовать другое сравнение углов.

Для угла между двумя плоскими векторами:

cos (OA, OB) = (OA x * OB x + OA y * OB y ) / кв.м. ((OA x 2 + OA y 2 ) * (OB x 2 + OB y 2 ))

Я думаюВы можете сравнить углы, имеющие косинусы.

...