Den Polygonschwerpunkt von roten Linien in einem PNG-Bild mittels JavaScript rekonstruieren und die genauen Koordinaten ermitteln?
-
Hi, ich habe eine etwas ungewöhnliche Frage...
Ich habe eine Bildschirmaufnahme als .png-Bild von einer Landkarte. In dieser Bildschirmaufnahme befindet sich ein Polygon (konkav oder konvex...), welches mit roten Linien eingezeichnet wurde:
Beispiel:
https://postimg.cc/zy15wZZvWie kann ich nun am einfachsten in JavaScript: A den Schwerpunkt des Polygons einzeichnen, und B die (genauen) Koordinaten sowie Position (Longitude, Latitude) in der Karte dieses Punkts berechnen, sodass ich anschließend durch Hereinzoomen sehen kann, was dort genau ist?
Ich müsste vermutlich erst einmal die roten Linienverläufe erkennen, oder? Also Kanten, Ecken und so.
-
Ich frag' mal die KI, ich will aber auch keine Credits dafür ausgeben...
Eigentlich wollte ich von euch nur mal hören, ob mein Vorhaben unsinnig ist oder nicht...
Hintergrund: Manchmal kommen von der Nina-App Warnmeldungen... ein Brand, Rauch, whatever... aber die genaue Ursache wird nicht angegeben. Mithilfe der Karte und dem eingezeichneten Polygon möchte ich das herausfinden.
-
Moin, wieso sagt eigentlich keiner, dass der von mir gewählte Image-Hoster ultra-aggressive Werbung schaltet und sogar den Rechtsklick ersetzt? Geht ja gar nicht mehr...
Es hat mich in den Fingern gejuckt und ich habe nun doch noch die AI gefragt... auch, wenn es viele Credits kostete.
(Aber, machen wir es wie in der Politik, wenn das Geld knapp wird, drucken wir einfach Neues. 
(Sorry, das war etwas populistisch...))Die Methode getPolygon:
• erkennt rote Pixel und bestimmt die zusammenhängende Polygon-Komponente,
• identifiziert gerade rote Linien per Hough-Analyse,
• berechnet deren Schnittpunkte als Ecken,
• filtert Artefakte und sortiert die Eckpunkte deterministisch,
• gibt bei fehlenden oder unzureichenden Daten eine leere Liste zurück.import java.awt.Color; import java.awt.Graphics2D; import java.awt.geom.Point2D; import java.awt.image.BufferedImage; import java.io.File; import java.io.IOException; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Objects; import javax.imageio.ImageIO; public class MapPolygon { private static final int ANGLE_COUNT = 180; private static final double LINE_DISTANCE_TOLERANCE = 3.0; private static final double LINE_MERGE_DISTANCE = 10.0; private static final double LINE_MERGE_ANGLE = Math.toRadians(10); private static final double INTERSECTION_CLUSTER_DISTANCE = 10.0; private static final double SEGMENT_ENDPOINT_TOLERANCE = 1.0; private static final double PROJECTION_GAP_TOLERANCE = 4.0; private static final double COLLINEAR_DISTANCE_TOLERANCE = 3.0; private static final double COLLINEAR_ANGLE_TOLERANCE = Math.toRadians(12); private static final double COLLINEAR_MAX_SPAN_RATIO = 1.7; private static final double MINIMUM_EDGE_SUPPORT_RATIO = 0.5; public static void main(String[] args) throws IOException { BufferedImage image = ImageIO.read(new File("Screenshot-2026-09-15-233031.png")); List<Point2D> points = getPolygon(image); for (Point2D point : points) { System.out.println(point); drawPointWith10px(image, point, Color.BLUE); } List<Point2D> centers = calculatePolygonCenters(points); for (int i = 0; i < centers.size(); i++) { System.out.println(i + 1 + ". " + centers.get(i)); } drawPointWith10px(image, centers.get(0), Color.YELLOW); drawPointWith10px(image, centers.get(1), Color.MAGENTA); drawPointWith10px(image, centers.get(2), Color.RED); ImageIO.write(image, "PNG", new File("Screenshot-2026-09-15-233031-2.png")); } public static void drawPointWith10px(BufferedImage image, Point2D point, Color color) { Objects.requireNonNull(image, "image"); Objects.requireNonNull(point, "point"); final int diameter = 10; int x = (int) Math.round(point.getX()) - diameter / 2; int y = (int) Math.round(point.getY()) - diameter / 2; Graphics2D graphics = image.createGraphics(); try { graphics.setColor(color); graphics.fillOval(x, y, diameter, diameter); } finally { graphics.dispose(); } } public static List<Point2D> calculatePolygonCenters(List<Point2D> points) { Objects.requireNonNull(points, "points"); if (points.size() < 3) { throw new IllegalArgumentException("At least three points are required"); } double vertexX = 0; double vertexY = 0; double edgeX = 0; double edgeY = 0; double edgeLengthSum = 0; double areaTwice = 0; double centroidX = 0; double centroidY = 0; for (int index = 0; index < points.size(); index++) { Point2D current = Objects.requireNonNull(points.get(index), "points contains null"); Point2D next = Objects.requireNonNull(points.get((index + 1) % points.size()), "points contains null"); if (!Double.isFinite(current.getX()) || !Double.isFinite(current.getY()) || !Double.isFinite(next.getX()) || !Double.isFinite(next.getY())) { throw new IllegalArgumentException("Points must have finite coordinates"); } vertexX += current.getX(); vertexY += current.getY(); double deltaX = next.getX() - current.getX(); double deltaY = next.getY() - current.getY(); double edgeLength = Math.hypot(deltaX, deltaY); edgeLengthSum += edgeLength; edgeX += (current.getX() + next.getX()) * edgeLength / 2; edgeY += (current.getY() + next.getY()) * edgeLength / 2; double cross = current.getX() * next.getY() - next.getX() * current.getY(); areaTwice += cross; centroidX += (current.getX() + next.getX()) * cross; centroidY += (current.getY() + next.getY()) * cross; } Point2D.Double vertexCenter = new Point2D.Double(vertexX / points.size(), vertexY / points.size()); Point2D.Double edgeCenter = edgeLengthSum == 0 ? vertexCenter : new Point2D.Double(edgeX / edgeLengthSum, edgeY / edgeLengthSum); Point2D.Double areaCenter = Math.abs(areaTwice) < 1e-10 ? vertexCenter : new Point2D.Double(centroidX / (3 * areaTwice), centroidY / (3 * areaTwice)); return List.of(vertexCenter, edgeCenter, areaCenter); } public static List<Point2D> getPolygon(BufferedImage image) { Objects.requireNonNull(image, "image"); List<Point> redPixels = largestRedComponent(image); if (redPixels.size() < 3) { return Collections.emptyList(); } List<Line> lines = findLines(redPixels, image.getWidth(), image.getHeight()); List<Point2D.Double> corners = findIntersections(lines, image.getWidth(), image.getHeight()); if (corners.size() < 3) { corners = convexHull(redPixels); } sortAroundPolygon(corners); removeCollinearCorners(corners, redPixels); return new ArrayList<>(corners); } private static List<Point> largestRedComponent(BufferedImage image) { int width = image.getWidth(); int height = image.getHeight(); boolean[] red = new boolean[width * height]; boolean[] visited = new boolean[red.length]; for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { red[y * width + x] = isRed(image.getRGB(x, y)); } } List<Point> largest = Collections.emptyList(); int[] directions = {-1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1}; for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { int start = y * width + x; if (!red[start] || visited[start]) { continue; } List<Point> component = new ArrayList<>(); ArrayDeque<Integer> queue = new ArrayDeque<>(); queue.add(start); visited[start] = true; while (!queue.isEmpty()) { int index = queue.remove(); int pointY = index / width; int pointX = index % width; component.add(new Point(pointX, pointY)); for (int direction = 0; direction < directions.length; direction += 2) { int nextX = pointX + directions[direction]; int nextY = pointY + directions[direction + 1]; if (nextX < 0 || nextX >= width || nextY < 0 || nextY >= height) { continue; } int next = nextY * width + nextX; if (red[next] && !visited[next]) { visited[next] = true; queue.add(next); } } } if (component.size() > largest.size()) { largest = component; } } } return largest; } private static boolean isRed(int argb) { int alpha = (argb >>> 24) & 0xff; int red = (argb >>> 16) & 0xff; int green = (argb >>> 8) & 0xff; int blue = argb & 0xff; return alpha != 0 && red >= 100 && red - green >= 40 && red - blue >= 40 && red > green * 1.35 && red > blue * 1.35; } private static List<Line> findLines(List<Point> points, int width, int height) { int rhoLimit = (int) Math.ceil(Math.hypot(width - 1, height - 1)); int[][] accumulator = new int[ANGLE_COUNT][rhoLimit * 2 + 1]; double[] cos = new double[ANGLE_COUNT]; double[] sin = new double[ANGLE_COUNT]; for (int angle = 0; angle < ANGLE_COUNT; angle++) { double radians = Math.PI * angle / ANGLE_COUNT; cos[angle] = Math.cos(radians); sin[angle] = Math.sin(radians); } for (Point point : points) { for (int angle = 0; angle < ANGLE_COUNT; angle++) { int rho = (int) Math.round(point.x * cos[angle] + point.y * sin[angle]); accumulator[angle][rho + rhoLimit]++; } } int maximumSupport = 0; for (int[] angleAccumulator : accumulator) { for (int support : angleAccumulator) { maximumSupport = Math.max(maximumSupport, support); } } int minimumSupport = Math.max(4, (int) Math.ceil(maximumSupport * 0.10)); List<HoughPeak> peaks = new ArrayList<>(); for (int angle = 0; angle < ANGLE_COUNT; angle++) { for (int rhoIndex = 1; rhoIndex < accumulator[angle].length - 1; rhoIndex++) { int support = accumulator[angle][rhoIndex]; if (support < minimumSupport || support < accumulator[angle][rhoIndex - 1] || support < accumulator[angle][rhoIndex + 1]) { continue; } peaks.add(new HoughPeak(angle, rhoIndex - rhoLimit, support)); } } peaks.sort(Comparator.comparingInt(HoughPeak::support).reversed()); List<Line> lines = new ArrayList<>(); for (HoughPeak peak : peaks) { Line candidate = refineLine(new Line(Math.PI * peak.angle / ANGLE_COUNT, peak.rho, peak.support), points); if (candidate == null || candidate.maxProjection - candidate.minProjection < 4) { continue; } boolean duplicate = false; for (Line line : lines) { if (sameLine(candidate, line)) { duplicate = true; break; } } if (!duplicate) { lines.add(candidate); } if (lines.size() == 64) { break; } } return lines; } private static Line refineLine(Line initial, List<Point> points) { double cos = Math.cos(initial.theta); double sin = Math.sin(initial.theta); double meanX = 0; double meanY = 0; int count = 0; for (Point point : points) { if (Math.abs(point.x * cos + point.y * sin - initial.rho) <= LINE_DISTANCE_TOLERANCE) { meanX += point.x; meanY += point.y; count++; } } if (count < 3) { return null; } meanX /= count; meanY /= count; double xx = 0; double xy = 0; double yy = 0; for (Point point : points) { if (Math.abs(point.x * cos + point.y * sin - initial.rho) <= LINE_DISTANCE_TOLERANCE) { double dx = point.x - meanX; double dy = point.y - meanY; xx += dx * dx; xy += dx * dy; yy += dy * dy; } } double direction = 0.5 * Math.atan2(2 * xy, xx - yy); double theta = normalizeAngle(direction + Math.PI / 2); cos = Math.cos(theta); sin = Math.sin(theta); double rho = meanX * cos + meanY * sin; List<Double> projections = new ArrayList<>(); double residualSquared = 0; int refinedCount = 0; for (Point point : points) { double distance = point.x * cos + point.y * sin - rho; if (Math.abs(distance) <= LINE_DISTANCE_TOLERANCE) { residualSquared += distance * distance; refinedCount++; projections.add(-point.x * sin + point.y * cos); } } if (refinedCount < 3 || residualSquared / refinedCount > 2.25 || projections.isEmpty()) { return null; } projections.sort(Double::compareTo); int largestStart = 0; int largestEnd = 0; int clusterStart = 0; for (int index = 1; index < projections.size(); index++) { if (projections.get(index) - projections.get(index - 1) > PROJECTION_GAP_TOLERANCE) { if (index - 1 - clusterStart > largestEnd - largestStart) { largestStart = clusterStart; largestEnd = index - 1; } clusterStart = index; } } if (projections.size() - 1 - clusterStart > largestEnd - largestStart) { largestStart = clusterStart; largestEnd = projections.size() - 1; } double minProjection = projections.get(largestStart); double maxProjection = projections.get(largestEnd); return new Line(theta, rho, initial.support, minProjection, maxProjection); } private static boolean sameLine(Line first, Line second) { double orientation = Math.cos(first.theta - second.theta); if (Math.abs(orientation) < Math.cos(LINE_MERGE_ANGLE)) { return false; } double secondRho = orientation < 0 ? -second.rho : second.rho; return Math.abs(first.rho - secondRho) <= LINE_MERGE_DISTANCE; } private static List<Point2D.Double> findIntersections(List<Line> lines, int width, int height) { List<Point2D.Double> intersections = new ArrayList<>(); for (int first = 0; first < lines.size(); first++) { Line a = lines.get(first); double aCos = Math.cos(a.theta); double aSin = Math.sin(a.theta); for (int second = first + 1; second < lines.size(); second++) { Line b = lines.get(second); double bCos = Math.cos(b.theta); double bSin = Math.sin(b.theta); double determinant = aCos * bSin - aSin * bCos; if (Math.abs(determinant) < 0.1) { continue; } double x = (a.rho * bSin - aSin * b.rho) / determinant; double y = (aCos * b.rho - a.rho * bCos) / determinant; if (x < -LINE_DISTANCE_TOLERANCE || x > width - 1 + LINE_DISTANCE_TOLERANCE || y < -LINE_DISTANCE_TOLERANCE || y > height - 1 + LINE_DISTANCE_TOLERANCE || !onLineSegment(a, x, y) || !onLineSegment(b, x, y)) { continue; } addIntersection(intersections, new Point2D.Double(x, y)); } } return intersections; } private static boolean onLineSegment(Line line, double x, double y) { double projection = -x * Math.sin(line.theta) + y * Math.cos(line.theta); return projection >= line.minProjection - SEGMENT_ENDPOINT_TOLERANCE && projection <= line.maxProjection + SEGMENT_ENDPOINT_TOLERANCE; } private static void addIntersection(List<Point2D.Double> intersections, Point2D.Double point) { for (Point2D.Double existing : intersections) { if (existing.distance(point) <= INTERSECTION_CLUSTER_DISTANCE) { existing.setLocation((existing.x + point.x) / 2, (existing.y + point.y) / 2); return; } } intersections.add(point); } private static List<Point2D.Double> convexHull(List<Point> points) { List<Point2D.Double> sorted = new ArrayList<>(); for (Point point : points) { sorted.add(new Point2D.Double(point.x, point.y)); } sorted.sort( Comparator.comparingDouble((Point2D.Double point) -> point.x) .thenComparingDouble(point -> point.y)); List<Point2D.Double> hull = new ArrayList<>(); for (Point2D.Double point : sorted) { while (hull.size() >= 2 && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), point) <= 1) { hull.remove(hull.size() - 1); } hull.add(point); } int lowerSize = hull.size(); for (int index = sorted.size() - 2; index >= 0; index--) { Point2D.Double point = sorted.get(index); while (hull.size() > lowerSize && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), point) <= 1) { hull.remove(hull.size() - 1); } hull.add(point); } if (hull.size() > 1) { hull.remove(hull.size() - 1); } return hull; } private static double cross(Point2D.Double a, Point2D.Double b, Point2D.Double c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } private static void sortAroundPolygon(List<Point2D.Double> corners) { if (corners.isEmpty()) { return; } double centerX = 0; double centerY = 0; for (Point2D.Double corner : corners) { centerX += corner.x; centerY += corner.y; } final double averageX = centerX / corners.size(); final double averageY = centerY / corners.size(); corners.sort( Comparator.comparingDouble(corner -> Math.atan2(corner.y - averageY, corner.x - averageX))); int first = 0; for (int index = 1; index < corners.size(); index++) { Point2D.Double candidate = corners.get(index); Point2D.Double current = corners.get(first); if (candidate.y < current.y || (candidate.y == current.y && candidate.x < current.x)) { first = index; } } Collections.rotate(corners, -first); } private static void removeCollinearCorners(List<Point2D.Double> corners, List<Point> redPixels) { boolean removed; do { removed = false; if (corners.size() <= 3) { return; } int removableIndex = -1; double shortestSpan = Double.POSITIVE_INFINITY; for (int index = 0; index < corners.size(); index++) { Point2D.Double previous = corners.get((index + corners.size() - 1) % corners.size()); Point2D.Double current = corners.get(index); Point2D.Double next = corners.get((index + 1) % corners.size()); if (isCollinear(previous, current, next)) { double span = previous.distance(next); if (span < shortestSpan) { shortestSpan = span; removableIndex = index; } } double span = shortestCollinearSpan(corners, index, redPixels); if (span < shortestSpan) { shortestSpan = span; removableIndex = index; } } if (removableIndex >= 0) { corners.remove(removableIndex); removed = true; } } while (removed); } private static double shortestCollinearSpan( List<Point2D.Double> corners, int currentIndex, List<Point> redPixels) { Point2D.Double current = corners.get(currentIndex); if (isStrongCorner(current, corners, redPixels)) { return Double.POSITIVE_INFINITY; } double shortestSpan = Double.POSITIVE_INFINITY; for (int first = 0; first < corners.size(); first++) { if (first == currentIndex) { continue; } for (int second = first + 1; second < corners.size(); second++) { if (second == currentIndex) { continue; } if (isBetween(corners.get(first), current, corners.get(second)) && hasRedLineBetween(corners.get(first), corners.get(second), redPixels)) { shortestSpan = Math.min(shortestSpan, corners.get(first).distance(corners.get(second))); } } } return shortestSpan; } private static boolean isStrongCorner( Point2D.Double current, List<Point2D.Double> corners, List<Point> redPixels) { List<Point2D.Double> connectedCorners = new ArrayList<>(); for (Point2D.Double other : corners) { if (other != current && hasRedLineBetween(current, other, redPixels)) { connectedCorners.add(other); } } for (int first = 0; first < connectedCorners.size(); first++) { Point2D.Double a = connectedCorners.get(first); double firstX = a.x - current.x; double firstY = a.y - current.y; double firstLength = Math.hypot(firstX, firstY); for (int second = first + 1; second < connectedCorners.size(); second++) { Point2D.Double b = connectedCorners.get(second); double secondX = b.x - current.x; double secondY = b.y - current.y; double secondLength = Math.hypot(secondX, secondY); double oppositeAngle = Math.acos( Math.max( -1, Math.min( 1, -(firstX * secondX + firstY * secondY) / (firstLength * secondLength)))); if (oppositeAngle > COLLINEAR_ANGLE_TOLERANCE) { return true; } } } return false; } private static boolean isBetween( Point2D.Double first, Point2D.Double current, Point2D.Double second) { double directionX = second.x - first.x; double directionY = second.y - first.y; double lengthSquared = directionX * directionX + directionY * directionY; if (lengthSquared == 0) { return false; } double position = ((current.x - first.x) * directionX + (current.y - first.y) * directionY) / lengthSquared; if (position <= 0.1 || position >= 0.9) { return false; } double firstDistance = Math.hypot(current.x - first.x, current.y - first.y); double secondDistance = Math.hypot(current.x - second.x, current.y - second.y); if (Math.sqrt(lengthSquared) > COLLINEAR_MAX_SPAN_RATIO * Math.max(firstDistance, secondDistance)) { return false; } double distance = Math.abs(directionX * (current.y - first.y) - directionY * (current.x - first.x)) / Math.sqrt(lengthSquared); return distance <= COLLINEAR_DISTANCE_TOLERANCE; } private static boolean hasRedLineBetween( Point2D.Double first, Point2D.Double second, List<Point> redPixels) { double directionX = second.x - first.x; double directionY = second.y - first.y; double length = Math.hypot(directionX, directionY); if (length == 0) { return false; } int support = 0; double lengthSquared = length * length; for (Point redPixel : redPixels) { double position = ((redPixel.x - first.x) * directionX + (redPixel.y - first.y) * directionY) / lengthSquared; if (position < 0 || position > 1) { continue; } double distance = Math.abs(directionX * (redPixel.y - first.y) - directionY * (redPixel.x - first.x)) / length; if (distance <= LINE_DISTANCE_TOLERANCE) { support++; } } return support >= Math.max(5, length * MINIMUM_EDGE_SUPPORT_RATIO); } private static boolean isCollinear( Point2D.Double previous, Point2D.Double current, Point2D.Double next) { double firstX = current.x - previous.x; double firstY = current.y - previous.y; double secondX = next.x - current.x; double secondY = next.y - current.y; double firstLength = Math.hypot(firstX, firstY); double secondLength = Math.hypot(secondX, secondY); if (firstLength == 0 || secondLength == 0) { return true; } double dot = firstX * secondX + firstY * secondY; if (dot <= 0) { return false; } double turnAngle = Math.acos(Math.max(-1, Math.min(1, dot / (firstLength * secondLength)))); double distanceFromLine = Math.abs( (next.x - previous.x) * (current.y - previous.y) - (next.y - previous.y) * (current.x - previous.x)) / Math.hypot(next.x - previous.x, next.y - previous.y); return turnAngle <= COLLINEAR_ANGLE_TOLERANCE && distanceFromLine <= COLLINEAR_DISTANCE_TOLERANCE; } private record Point(int x, int y) {} private record HoughPeak(int angle, int rho, int support) {} private record Line( double theta, double rho, int support, double minProjection, double maxProjection) { private Line(double theta, double rho, int support) { this(theta, rho, support, 0, 0); } } private static double normalizeAngle(double angle) { while (angle < 0) { angle += Math.PI; } while (angle >= Math.PI) { angle -= Math.PI; } return angle; } }Vorherbild: https://www.directupload.eu/file/d/9413/ixn6jvbx_png.htm
Nachherbild: https://www.directupload.eu/file/d/9413/i5xy6a5p_png.htm
(Ja, ich weiß, der geometrische (Gelb) und der Kantenschwerpunkt (Magenta) liegen hier im Beispiel direkt übereinander.)
Die Adaption von Java nach JS erfordert jetzt ja nur noch ein wenig Transferleistung, und die Umrechnung in Koordinaten ist vermutlich auch nicht so schwer.