He tenido que hacer variaciones de esto en el pasado, por lo que despierta muchos recuerdos de los años setenta y ochenta.
Ahora, usted dice “mejorar un algoritmo” pero no especifica qué algoritmo está utilizando o en qué idioma está trabajando. Por lo tanto, comenzaré desde cero.
He pegado un par de enlaces a continuación que se relacionan con hacer esto, no solo con un polígono, sino con cualquier colección de puntos / vértices. Pero no estoy seguro si quieres una solución tan complicada. Tal vez solo esté buscando el centro de gravedad (enlace a continuación).
- Cómo traducir mis pensamientos en código
- ¿Qué es una explicación intuitiva de MapReduce?
- Cómo dominar las estructuras de datos y los algoritmos (DSA) para mejorar mis habilidades de resolución de problemas que eventualmente serán útiles en las entrevistas
- ¿Qué es el conocimiento estructurado?
- ¿Qué vas a aprender y en qué proyecto vas a trabajar este verano como principiante en programación?
Triangulación de Delaunay – Wikipedia
Diagrama de Voronoi – Wikipedia
Centro de masas – Wikipedia
O tal vez desee el punto interior más alejado de todos los vértices. Para obtener la última solución, hay varias formas. Uno se conoce como el algoritmo Saab, donde dibujas bisectrices para cada ángulo interior, incluso si ese ángulo es mayor de 180 grados. Si esas bisectrices se cruzan, deténgalas en esa intersección y dibuje una bisectriz de esas bisectrices. Para cualquier cadena cerrada (como un polígono), todas las bisectrices se encontrarán en un punto, el punto más alejado de todos los vértices. La matemática para esto se complica para algunos tipos de formas porque muchas de las bisectrices no serán líneas, sino parábolas u otras curvas. Eso no te afectará cuando uses solo un polígono. Aquí hay otra forma de hacer esto: encontrar un punto más alejado de $ k $ puntos en un polígono
O tal vez desee el punto interior más alejado de todos los lados. Este es el centro del círculo más grande que cabe en el polígono. La solución es iterativa y creo que es la única forma de hacerlo. Aquí hay una discusión al respecto en stackoverflow: círculo más grande dentro de un polígono no convexo
Buena suerte.
