Рассчитать кривизну для 3 точек (х, у)
У меня есть двухмерное евклидово пространство. Три очка даны.
Например (p2 - средняя точка):
Point2D p1 = new Point2D.Double(177, 289);
Point2D p2 = new Point2D.Double(178, 290);
Point2D p3 = new Point2D.Double(178, 291);
Теперь я хочу вычислить кривизну для этих трех точек.
double curvature = calculateCurvature(p1, p2, p3);
Как это сделать? Есть ли существующий метод (нет внешних библиотек Java)?
- Кривизна: https://en.wikipedia.org/wiki/Curvature
- Кривизна Менгера: https://en.wikipedia.org/wiki/Menger_curvature
5 ответов
Решение
Для кривизны Менгера формула прямо здесь, в статье Википедии:
curvature = 4*triangleArea/(sideLength1*sideLength2*sideLength3)
Какой код вы пробовали именно?
Не должно быть слишком сложно рассчитать эти 4 значения, учитывая ваши 3 балла.
Вот несколько полезных методов:
/**
* Returns twice the signed area of the triangle a-b-c.
* @param a first point
* @param b second point
* @param c third point
* @return twice the signed area of the triangle a-b-c
*/
public static double area2(Point2D a, Point2D b, Point2D c) {
return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
/**
* Returns the Euclidean distance between this point and that point.
* @param that the other point
* @return the Euclidean distance between this point and that point
*/
public double distanceTo(Point2D that) {
double dx = this.x - that.x;
double dy = this.y - that.y;
return Math.sqrt(dx*dx + dy*dy);
}
Больше нечего делать. Предупреждение: area2 возвращает двойной знак со знаком, в зависимости от ориентации ваших точек (по часовой стрелке или против часовой стрелки).
Как уже указывал Эрик Думинил в своем ответе, вычисление
curvature = 4*triangleArea/(sideLength0*sideLength1*sideLength2)
Я потратил немного времени на создание этого интерактивного примера, который содержит computeCurvature метод, который выполняет все вычисления одновременно:
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
public class CurvatureFromThreePoints
{
public static void main(String[] args)
{
SwingUtilities.invokeLater(new Runnable()
{
@Override
public void run()
{
createAndShowGUI();
}
});
}
private static void createAndShowGUI()
{
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.getContentPane().add(new CurvatureFromThreePointsPanel());
f.setSize(800,800);
f.setLocationRelativeTo(null);
f.setVisible(true);
}
}
class CurvatureFromThreePointsPanel extends JPanel
implements MouseListener, MouseMotionListener
{
private final List<Point2D> pointList;
private Point2D draggedPoint;
public CurvatureFromThreePointsPanel()
{
this.pointList = new ArrayList<Point2D>();
pointList.add(new Point2D.Double(132,532));
pointList.add(new Point2D.Double(275,258));
pointList.add(new Point2D.Double(395,267));
addMouseListener(this);
addMouseMotionListener(this);
}
private static double computeCurvature(Point2D p0, Point2D p1, Point2D p2)
{
double dx1 = p1.getX() - p0.getX();
double dy1 = p1.getY() - p0.getY();
double dx2 = p2.getX() - p0.getX();
double dy2 = p2.getY() - p0.getY();
double area = dx1 * dy2 - dy1 * dx2;
double len0 = p0.distance(p1);
double len1 = p1.distance(p2);
double len2 = p2.distance(p0);
return 4 * area / (len0 * len1 * len2);
}
// Adapted from https://stackru.com/a/4103418
private static Point2D computeCircleCenter(
Point2D p0, Point2D p1, Point2D p2)
{
double x0 = p0.getX();
double y0 = p0.getY();
double x1 = p1.getX();
double y1 = p1.getY();
double x2 = p2.getX();
double y2 = p2.getY();
double offset = x1 * x1 + y1 * y1;
double bc = (x0 * x0 + y0 * y0 - offset) / 2.0;
double cd = (offset - x2 * x2 - y2 * y2) / 2.0;
double det = (x0 - x1) * (y1 - y2) - (x1 - x2) * (y0 - y1);
double invDet = 1 / det;
double cx = (bc * (y1 - y2) - cd * (y0 - y1)) * invDet;
double cy = (cd * (x0 - x1) - bc * (x1 - x2)) * invDet;
return new Point2D.Double(cx, cy);
}
@Override
protected void paintComponent(Graphics gr)
{
super.paintComponent(gr);
Graphics2D g = (Graphics2D)gr;
g.setColor(Color.RED);
for (Point2D p : pointList)
{
double r = 5;
g.draw(new Ellipse2D.Double(p.getX()-r, p.getY()-r, r+r, r+r));
}
g.setColor(Color.BLACK);
//g.draw(Paths.fromPoints(spline.getInterpolatedPoints(), false));
Point2D p0 = pointList.get(0);
Point2D p1 = pointList.get(1);
Point2D p2 = pointList.get(2);
double curvature = computeCurvature(p0, p1, p2);
g.drawString("Curvature: "+curvature, 10, 20);
Point2D center = computeCircleCenter(p0, p1, p2);
double radius = center.distance(p0);
g.draw(new Ellipse2D.Double(
center.getX() - radius, center.getY() - radius,
radius + radius, radius + radius));
}
@Override
public void mouseDragged(MouseEvent e)
{
if (draggedPoint != null)
{
draggedPoint.setLocation(e.getX(), e.getY());
repaint();
System.out.println("Points: ");
for (Point2D p : pointList)
{
System.out.println(" "+p);
}
}
}
@Override
public void mousePressed(MouseEvent e)
{
final double thresholdSquared = 10 * 10;
Point2D p = e.getPoint();
Point2D closestPoint = null;
double minDistanceSquared = Double.MAX_VALUE;
for (Point2D point : pointList)
{
double dd = point.distanceSq(p);
if (dd < thresholdSquared && dd < minDistanceSquared)
{
minDistanceSquared = dd;
closestPoint = point;
}
}
draggedPoint = closestPoint;
}
@Override
public void mouseReleased(MouseEvent e)
{
draggedPoint = null;
}
@Override
public void mouseMoved(MouseEvent e)
{
// Nothing to do here
}
@Override
public void mouseClicked(MouseEvent e)
{
// Nothing to do here
}
@Override
public void mouseEntered(MouseEvent e)
{
// Nothing to do here
}
@Override
public void mouseExited(MouseEvent e)
{
// Nothing to do here
}
}
Из вики, на которую вы ссылались, кривизна определяется как 
где A - площадь, окруженная треугольником, образованным тремя точками x, y и z (p1, p2, p3 в вашем случае) и |xy| это расстояние между точками х и у.
Переведите формулу в код, и все готово!
Если кто-то хочет это в питоне:
def getCurvature(x1, y1, x2, y2, x3, y3):
point1 = (x1, y1)
point2 = (x2, y2)
point3 = (x3, y3)
# Calculating length of all three sides
len_side_1 = round( math.dist(point1, point2), 2)
len_side_2 = round( math.dist(point2, point3), 2)
len_side_3 = round( math.dist(point1, point3), 2)
# sp is semi-perimeter
sp = (len_side_1 + len_side_2 + len_side_3) / 2
# Calculating area using Herons formula
area = math.sqrt(sp * (sp - len_side_1) * (sp - len_side_2) * (sp - len_side_3))
# Calculating curvature using Menger curvature formula
curvature = (4 * area) / (len_side_1 * len_side_2 * len_side_3)
return curvature
C/C++
// https://www.mathopenref.com/coordtrianglearea.html
float getAreaOfTriangle(Point2f A, Point2f B, Point2f C)
{
return fabs(
(A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) / 2);
}
float getDistFromPtToPt(Point2f pt1, Point2f pt2)
{
return sqrt((pt2.x - pt1.x) * (pt2.x - pt1.x) +
(pt2.y - pt1.y) * (pt2.y - pt1.y));
}
// https://en.wikipedia.org/wiki/Menger_curvature
float
getCurvatureUsingTriangle(Point2f pt1, Point2f pt2, Point2f pt3, bool bDebug)
{
float fAreaOfTriangle = getAreaOfTriangle(pt1, pt2, pt3);
float fDist12 = getDistFromPtToPt(pt1, pt2);
float fDist23 = getDistFromPtToPt(pt2, pt3);
float fDist13 = getDistFromPtToPt(pt1, pt3);
float fKappa = 4 * fAreaOfTriangle / (fDist12 * fDist23 * fDist13);
return fKappa;
}